BOJ 3184 - 양

문제

백준 온라인 저지 - 3184번

풀이 과정

BFS 탐색을 통해 모든 영역을 탐색해준 뒤 늑대의 수와 양의 수를 파악하는 문제입니다.
저는 늑대의 위치에서부터 BFS 탐색을 수행했지만
그냥 아직 방문하지 않은 빈칸에서부터 BFS 탐색을 시작해도 상관없을 것 같습니다.

코드

import sys
from collections import deque


R, C = list(map(int, sys.stdin.readline().split()))
board = []
wolves = []
sheep = []
for r in range(R):
    line = list(sys.stdin.readline()[:-1])
    board.append(line)

    for c in range(C):
        if line[c] == 'v':
            wolves.append([r, c])
        if line[c] == 'o':
            sheep.append([r, c])


visit = [[False] * C for _ in range(R)]
dx = [0 ,0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(start):
    w_c = 1
    s_c = 0

    q = deque()
    q.append([start[0], start[1]])
    visit[start[0]][start[1]] = True

    while q:
        x, y = q.popleft()

        for i in range(4):
            next_x, next_y = x + dx[i], y + dy[i]

            if 0 <= next_x < R and 0 <= next_y < C:
                if board[next_x][next_y] != '#' and not visit[next_x][next_y]:
                    visit[next_x][next_y] = True
                    q.append([next_x, next_y])
                    if board[next_x][next_y] == 'v':
                        w_c += 1
                    if board[next_x][next_y] == 'o':
                        s_c += 1

    return w_c, s_c


def solution():
    init_wolf = len(wolves)
    init_sheep = len(sheep)
    for wolf in wolves:
        if not visit[wolf[0]][wolf[1]]:
            w_c, s_c = bfs(wolf)
            if w_c < s_c:
                init_wolf -= w_c
            else:
                init_sheep -= s_c

    print(init_sheep, init_wolf)


solution()