[백준/BOJ] - 3187번 python 풀이 - dfs

---

울타리 탐색 -> 양,늑대,빈공간 색출 아이디어가 떠오르지 않음

→  2중 반복문을 돌릴 때 울타리가 나올 경우 방문하지 않게끔 설정하자

 

임시 양, 늑대 수를 저장하는 변수와 최종 양, 늑대수를 저장하는 변수를 따로 설정해두자.

---

import sys
sys.setrecursionlimit(1000000)
R,C = map(int,input().split()) #세로 가로
arr = [list(input()) for _ in range(R)]
ok = [[False] * C for _ in range(R)]
dx,dy = (-1,1,0,0), (0,0,-1,1)
v_cnt = 0 #탐색하는 동안의 늑대 수
k_cnt = 0 #탐색하는 동안의 양 수
sheep = 0 #최종 양 수
wolf = 0  #최종 늑대 수
def dfs(x,y):
    ok[x][y] = True
    for i in range(4):
        rx = dx[i] + x
        ry = dy[i] + y
        if (0<=rx<R) and (0<=ry<C) and not ok[rx][ry]:
            if arr[rx][ry] != '#': #울타리가 아니다
                if arr[rx][ry] == 'v': #늑대
                    global v_cnt
                    v_cnt+=1
                elif arr[rx][ry] == 'k':#양
                    global k_cnt
                    k_cnt+=1                    
                dfs(rx,ry)

for i in range(R):
    for j in range(C):
        if not ok[i][j] and arr[i][j] != '#': #false && 울타리가 아닌 경우
            if arr[i][j] == 'v':
                v_cnt+=1
            elif arr[i][j] == 'k':
                k_cnt+=1

            dfs(i,j)

            if v_cnt >= k_cnt: #늑대가 더 많은 경우
                wolf += v_cnt #wolf <- 최종 늑대 수
            else:
                sheep += k_cnt #sheep <- 최종 양 수
            v_cnt,k_cnt = 0,0 #한번 탐색이 끝나면 0,0으로 초기화
print(sheep,wolf)