[Python] 백준 3184번 양 풀이

나의 풀이

---

마당을 탐색하면서 양, 늑대의 개수를 파악해야 한다. 탐색할 때 연결된 곳을 한번에 방문해야하기 때문에 BFS를 사용했다.

방문 중 만나는 양, 늑대의 수를 따로 변수에 저장해서 관리했다!

from collections import deque
import sys

# BFS 및 방문 처리
# 늑대 vs 양 개수 파악

def bfs(graph, start, visited):
    # 방문할 곳 등록
    queue = deque([start])
    x, y = start
    visited[x][y] = True
    # 늑대, 양 개수 확인
    wolf = 1 if graph[x][y] == "v" else 0 
    sheep = 1 if graph[x][y] == "o" else 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 맵 안나가고, 울타리가 아닌 경우
            if 0 <= nx < len(graph) and 0 <= ny < len(graph[0]) and graph[nx][ny] != "#":
                # 아직 방문하지 않은 경우
                if visited[nx][ny] == False:
                    # 방문 처리
                    visited[nx][ny] = True
                    queue.append([nx, ny])
                    if graph[nx][ny] == "o":
                        sheep += 1
                    elif graph[nx][ny] == "v":
                        wolf += 1
    # 늑대, 양 수 반환
    return wolf, sheep



def main():
    row, col = map(int, sys.stdin.readline().split())
    graph = [list(input()) for _ in range(row)]
    visited = [[False for _ in range(col)] for _ in range(row)]
    wolf_sum, sheep_sum = 0, 0
    for i in range(row):
        for j in range(col):
            # 울타리 X + 방문 X인 경우 방문
            if graph[i][j] != "#" and visited[i][j] == False:
                start = [i, j]
                wolf, sheep = bfs(graph, start, visited)
                # 늑대 양-수 확인
                if wolf >= sheep:
                    wolf_sum += wolf
                else:
                    sheep_sum += sheep
    print(sheep_sum, wolf_sum)




if __name__ == "__main__":
    main()