[BaekJoon] "DFS/BFS" - 백준 3187번 문제 : 양치기 꿍

[문제 설명]

https://www.acmicpc.net/problem/3187

3187번: 양치기 꿍

 양치기 꿍은 늑대들을 양들이 있는 울타리 안에 마구 집어넣어 양들을 잡아먹게 함

근데 양들은 보통 양들이 아님

같은 울타리 영역 안의 양들의 숫자가 늑대의 숫자보다 더 많을 경우, 늑대가 전부 잡아 먹힘

물론 그 외의 경우는 양이 전부 잡아 먹힘

빈 공간을 '.'으로 나타내고 울타리를 '#', 늑대를 'v', 양을 'k'라고 나타낸다면 

몇 마리의 양과 늑대가 살아남을지 계산

양과 늑대는 대각선으로 이동 불가능

 

[해결 로직]

- 일단은 BFS로 풀었음 (네방향 탐색할땐 거의 BFS로 푸는게 나은듯함)

- 입력된 맵에서 늑대 또는 양을 발견할 경우, BFS 탐색

- 이때, 양 또는 늑대의 수를 카운팅해야함. 그리고, 양 또는 늑대가 있던 자리에 울타리를 쳐줌으로써, 다음 번 탐색 시 탐색 하지 않도록 함

- 다른 양 또는 늑대 발견 시 수를 카운팅 해주고, 울타리 설치함

- 이렇게 계속해서 반복하면 전체 맵에서 한 울타리로 쳐진 무리 발견 시, 늑대와 양의 숫자를 카운팅 가능

- 그리고, 숫자 비교해서 둘 중 누가 얼마나 살아남는지 체크

 

[Solution 코드]

from collections import deque
n, m = map(int, input().split())
ary = []

for i in range(n):
    ary.append(list(map(str, input())))

dx = [0, 0, 1, -1]  ## 동, 서, 남, 북
dy = [1, -1, 0, 0]


def bfs(graph, x, y):

    q = deque()
    q.append((x,y))

    k_cnt, v_cnt = 0,0

    if graph[x][y] == 'k':
        k_cnt += 1
    elif graph[x][y] == 'v':
        v_cnt += 1

    ary[x][y] = '#'

    while q:

        nx, ny = q.popleft()

        for i in range(len(dx)):
            cx = nx + dx[i]
            cy = ny + dy[i]

            if cx < 0 or cx >=n or cy < 0 or cy >= m:
                continue

            if ary[cx][cy] == '#': ## 울타리라도 패스
                continue
            else:
                if ary[cx][cy] == 'k':
                    k_cnt += 1

                elif ary[cx][cy] == 'v':
                    v_cnt += 1

                ary[cx][cy] = '#'  ## 울타리 설치함
                q.append((cx, cy))

    if k_cnt > v_cnt: # 양이 늑대보다 많을 경우, 늑대가 전부 잡아먹힘
        v_cnt = 0
    else:
        k_cnt = 0

    return k_cnt, v_cnt

fin_k, fin_v = 0,0
for i in range(n):
    for j in range(m):
        if (ary[i][j] == 'k') or (ary[i][j] == 'v'):
            k_cnt, v_cnt = bfs(ary, i, j)
            fin_k += k_cnt
            fin_v += v_cnt

print(fin_k, fin_v)