[Algorithm] [백준] 3184 - 양 (BFS)

## 백준 3184 양
# BFS

import sys
input = sys.stdin.readline
from collections import deque

# BFS
def BFS(x, y):
    global o, v
    visited[x][y] = 1
    queue = deque()
    queue.append([x, y])
    oo = 0  # 한 울타리 내 양의 수
    vv = 0  # 한 울타리 내 늑대의 수
    if graph[x][y] == 'o': oo += 1
    elif graph[x][y] == 'v': vv += 1
    while queue:
        a, b = queue.popleft()
        for i in range(4):
            xx = a + dx[i]
            yy = b + dy[i]
            if 0 <= xx < r and 0 <= yy < c and visited[xx][yy] == 0 and graph[xx][yy] != '#':  # xx->r 이고 yy->c 인 것 주의!
                queue.append([xx, yy])
                visited[xx][yy] = 1
                if graph[xx][yy] == 'o':
                    oo += 1
                elif graph[xx][yy] == 'v':
                    vv += 1

    # oo와 vv는 지역변수라서 BFS 함수 내에서 비교 실행
    if oo and vv:  # oo와 vv 둘 다 0이 아니여야 비교 실행
        if oo > vv:
            v -= vv
        else:
            o -= oo


r, c = map(int, input().split()) # 마당의 행과 열

graph = [[0]*c for _ in range(r)]
visited = [[0]*c for _ in range(r)]
for i in range(r):
    lst = sys.stdin.readline().rstrip()
    for index, j in enumerate(lst):
        graph[i][index] = j

# 전체 양과 늑대 수 구하기
o = 0
v = 0
for i in range(r):
    for j in range(c):
        if graph[i][j] == 'o':
            o += 1
        elif graph[i][j] == 'v':
            v += 1

# 방향 확인용 좌표 dx, dy
# 좌/우/상/하
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

# 한 울타리를 만나면(=o나 v를 만나면) BFS 호출
for i in range(r):
    for j in range(c):
        if (graph[i][j] == 'o' or graph[i][j] == 'v') and visited[i][j] == 0:
            BFS(i, j)

print(o, v)

전에 풀었던 <단지번호붙이기> 문제처럼 생각하면 안된다.

<단지번호붙이기> 문제는 한 단지가 시작되는 집에 좌표가 찍히면, 그 집에 연결된 다른 집들을 파고 들어야 했다. 즉, DFS 였다!

하지만 이 <양> 문제는 울타리 내의 모든 좌표를 다 돌아야 한다. 특정한 좌표 값만 따라가지 않는다, 파고들지 않는다? 라고 이해할 수도 있을 것 같다. 즉, BFS 이다!

'o'과 'v'를 만나면 한 울타리 내에서의 수를 구해야 한다. (oo, vv 변수로 사용)
한 울타리 내에서 oo와 vv를 구했으면, 수를 비교하고 전체 수를 나타내는 o과 v 변수에 반영한다.

💡 울타리 내의 좌표들만 들를 수 있는 방법

-> BFS 내에서 방향 좌표로 상하좌우를 돌 때, 그 좌표 값이 '#' 이면 들르지 않는다. 따라서 시작 좌표의 주변 모든 값을 너비 탐색으로 돌지만, '#'를 만나면 그 좌표는 들르지 않기 때문에 '#' 내부의 좌표들만 들를 수 있게 된다.