백준[ 21736 | Python ] 헌내기는 친구가 필요해

문제

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

풀이

deque를 통해서 현재 노드로 부터 해당 너비를 탐색했던 BFS와는 다르게 재귀나 stack을 통해 깊이를 탐색한다.

해당 문제에서는 재귀를 통헤서 해결하는데, 현재 탐색하는 노드가 원하는 조건에 맞다면(현재 문제에서는 벽이 아닌 경우) 위치를 옮겨, 옮겨진 노드가 조건에 맞는지 탐색하면 된다.

또한 도연이가 움직인다는 조건에 맞추어 도연이의 위치를 미리 파악하여 움직여야 한다는 것도 잊지 않아야한다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n,m = list(map(int,input().split()))
board = []
target = []
dx, dy = [-1,1,0,0],[0,0,-1,1]
for i in range(n):
    col = list(input().rstrip())
    for c in range(len(col)):
        if col[c] == "I":
            target = [i,c]
    board.append(col)
        
visited = [[0]*m for _ in range(n)]
dx, dy = [-1,1,0,0],[0,0,-1,1]

cnt = 0
def dfs(x,y):
    global cnt
    if 0<=x<n and 0<=y<m and not visited[x][y]:
        visited[x][y] = 1
        if board[x][y] == 'P':
            cnt+=1
        for i in range(4):
            nx, ny = x + dx[i],y + dy[i]
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
                if board[nx][ny] != 'X':
                    dfs(nx,ny)
            
dfs(target[0],target[1])

if not cnt:
    print("TT")
else:
    print(cnt)

생각 & 정리

이전에는 너무도 다르고 어렵다고 생각한 DFS와 BFS 문제가 BFS문제를 반복적으로 해결하고 난 뒤 다시보니 크게 다르지 않았다. 또 같은 문제를 가지고 BFS, DFS 두가지 방법으로 풀 수 있는 이유 또한 새삼 느끼게 되었다.