[백준3184] / 양 - BFS

 

백준3184

 

 

푼 날짜 : 2024.10.27

푼 문제 : [3184] / 양

사용한 언어 : python

알고리즘 : BFS

 

 

접근 방식 :

BFS로 방문하지 않은 구간을 하나씩 탐색하며 양의 수와 늑대 수를 센다.

비교해서 많은 값들을 누적해서 계산해주었다!

 

 

코드 :

import sys
from collections import deque

R, C = map(int, sys.stdin.readline().split())
graph_ = []
for _ in range(R):
    row = list(sys.stdin.readline().rstrip())
    graph_.append(row)

visited = [[0 for _ in range(C)] for _ in range(R)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

sheep, wolf = 0, 0 # 양과 늑대 최종 수
def BFS(v):
    queue = deque([v])
    global sheep, wolf

	# 같은 공간에 있는 양과 늑대 카운트를 위함
    s_cnt, w_cnt = 0, 0
    # 시작 위치에 양이나 늑대가 있다면 일단 더해주고 시작
    if graph_[v[0]][v[1]] == 'k': s_cnt += 1
    elif graph_[v[0]][v[1]] == 'v': w_cnt += 1

    while queue:
        now = queue.popleft()

        for i in range(4):
            ny, nx = now[0]+dy[i], now[1]+dx[i]

            if 0<=ny<R and 0<=nx<C:
                if not visited[ny][nx] and graph_[ny][nx] != '#':
                    if graph_[ny][nx] == 'k': s_cnt += 1
                    elif graph_[ny][nx] == 'v': w_cnt += 1

                    visited[ny][nx] = 1
                    queue.append((ny, nx))
    
    # 양이 많다면 양 누적, 늑대가 많다면 늑대 누적
    if s_cnt > w_cnt: sheep += s_cnt
    else: wolf += w_cnt    


for i in range(R):
    for j in range(C):
        if not visited[i][j] and graph_[i][j] != '#':
            visited[i][j] = 1
            BFS((i, j))

print(sheep, wolf)

 

 

이번 문제는 생각보다 쉬웠다! 앞으로도 익숙해지게 더 열심히 풀어야지 :)