[백준-실버2] 3184번 양(DFS, 파이썬)

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

3184번: 양

 

<내 코드>

- 문제에서 #(울타리)는 이동하거나 넘어 갈 수 없어서 is_move배열에 움직일 수 있는 원소를 넣었다.

- visited 배열을 통해 방문처리를 하면서 중복을 방지함

- dfs 함수에서 아직 방문하지 않았고, 이동 가능한 경우에 양과 늑대의 수를 세어주고, 상하좌우로 dfs호출하여 그래프를 탐색한다.

- 메인 부분에서 dfs함수가 True를 리턴했을 때 양과 늑대의 수를 파악하여 result 배열에 넣어주고 다시 0으로 초기화한다.

import sys
sys.setrecursionlimit(10**9)
#입력
n,m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(input()))
visited = [[False]*m for _ in range(n)]
is_move = ['.', 'o', 'v']
def dfs(x,y):
    global wolf
    global sheep
    #영역 파악
    if x>=n or x<0 or y>=m or y<0:
        return False

    if visited[x][y] == False and graph[x][y] in is_move:#아직 방문 안했고 이동가능
        visited[x][y] = True#방문처리
        if graph[x][y] == 'o':#양이라면
            sheep+=1
        elif graph[x][y] =='v':#늑대라면
            wolf +=1
        dfs(x,y+1)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x-1,y)
        return True
    return False

wolf =0
sheep = 0
result = [0,0] #양, 늑대
for i in range(n):
    for j in range(m):
        if dfs(i,j) == True:
            if sheep > wolf:
                wolf = 0
                result[0] += sheep
                result[1] += wolf
            else:
                sheep = 0
                result[0] += sheep
                result[1] += wolf
                
            sheep = 0
            wolf = 0
            
for r in result:
    print(r, end = ' ')