[백준] 21736번 헌내기는 친구가 필요해 [Python] - 그래프 이론

 

$N \times M$ 크기이며 캠퍼스에서 

O는 빈 공간, X는 벽, I는 도연이, P는 사람으로 주어질 때,

상하좌우로만 이동가능한 도연이가 몇 명의 사람을 만날 수 있을까?

 

문제

2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 싶다. 

도연이가 다니는 대학의 캠퍼스는 $N \times M$ 크기이며 캠퍼스에서 이동하는 방법은 벽이 아닌 상하좌우로 이동하는 것이다. 예를 들어, 도연이가 $(x, y)$에 있다면 이동할 수 있는 곳은 $(x+1, y)$, $(x, y+1)$, $(x-1, y)$, $(x, y-1)$이다. 단, 캠퍼스의 밖으로 이동할 수는 없다.

불쌍한 도연이를 위하여 캠퍼스에서 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성해보자.

입력

첫째 줄에는 캠퍼스의 크기를 나타내는 두 정수 $N$ $( 1 \leq N \leq 600)$, $M$ $( 1 \leq M \leq 600)$이 주어진다.

둘째 줄부터 $N$개의 줄에는 캠퍼스의 정보들이 주어진다. O는 빈 공간, X는 벽, I는 도연이, P는 사람이다. I가 한 번만 주어짐이 보장된다.

출력

첫째 줄에 도연이가 만날 수 있는 사람의 수를 출력한다. 단, 아무도 만나지 못한 경우 TT를 출력한다.

 

재귀함수로 구현한 깊이 우선 탐색 $($DFS$)$

 

코드는 시작 지점 'I'에서 출발하여 'X'로 표시된 벽과 이미 방문한 지점을 피하면서 'P'를 찾는 것을 수행합니다.

이때 'P'를 찾을 때마다 카운트를 증가시키고, 최종적으로 'P'를 찾은 횟수를 출력합니다.
방문한 지점은 방문 여부를 체크하며 재귀 호출을 통해 깊이 우선 탐색을 수행합니다.

import sys
sys.setrecursionlimit(10**6)
def f(i, j, A, v, N, M):
    c = 0
    if A[i][j] == 'P':		# 'P'를 찾으면 카운트를 증가
        c += 1
    # 캠퍼스 내에서 벽(X)이 아니고, 방문한 적 없는 곳을 방문하고, 재귀 호출합니다.
    if j<M-1 and A[i][j+1] != 'X' and not v[i][j+1]:
        v[i][j+1] = True
        c += f(i, j+1, A, v, N, M)
    if j>0 and A[i][j-1] != 'X' and not v[i][j-1]:
        v[i][j-1] = True
        c += f(i, j-1, A, v, N, M)
    if i<N-1 and A[i+1][j] != 'X' and not v[i+1][j]:
        v[i+1][j] = True
        c += f(i+1, j, A, v, N, M)
    if i>0 and A[i-1][j] != 'X' and not v[i-1][j]:
        v[i-1][j] = True
        c += f(i-1, j, A, v, N, M)
    return c
def m():
    N, M = map(int, sys.stdin.readline().split())
    A = []
    v = [[False] * M for _ in range(N)]
    for i in range(N):
        li = list(sys.stdin.readline().rstrip())
        A.append(li)			# 캠퍼스 맵
        if 'I' in li:
            x, y = (i, li.index('I'))	# 도연이 위치
    v[x][y] = True
    n = f(x, y, A, v, N, M)
    print(n if n else 'TT')
if __name__=="__main__":
    m()

 

큐를 사용한 너비 우선 탐색 $($BFS$)$

탐색할 지점을 큐에 삽입해가면서 상하좌우로 이동하면서 각 방향으로 진행 가능한 경우에만 탐색을 진행합니다.

이때 'P'를 찾을 때마다 카운트를 증가시키고, 최종적으로 'P'를 찾은 횟수를 출력합니다.

벽('X')이나 이미 방문한 지점은 피하고, 방문한 지점은 방문 여부를 체크하며 큐에 삽입하여 계속해서 탐색을 진행합니다. 

import sys
from collections import deque
def f(x, y, A, N, M):
    d = ((0, 1), (0, -1), (1, 0), (-1, 0))	# 상하좌우
    v = [[False] * M for _ in range(N)]
    v[x][y] = True
    c = 0
    queue = deque([(x, y)])
    
    while queue:
        i, j = queue.popleft()
        for dx, dy in d:
            ni, nj = i + dx, j + dy		# 상하좌우로 이동한 지점
            
            # 캠퍼스 내, 벽이 아닌, 방문한 적 없는 경우
            if 0 > ni or ni >= N or 0 > nj or nj >= M: continue
            if v[ni][nj]: continue
            if A[ni][nj] == 'X': continue
            
            if A[ni][nj] == 'P': c += 1 # 사람이면 c +1
            v[ni][nj] = True		# 방문 표시
            queue.append((ni, nj))		# 방문 지점을 큐에 삽입
            
    if c: print(c)
    else: print('TT')

def m():
    N, M = map(int, sys.stdin.readline().split())
    A = []
    for i in range(N):
        li = list(sys.stdin.readline().rstrip())
        A.append(li)
        if 'I' in li:
            x, y = (i, li.index('I'))
    f(x, y, A, N, M)
    
if __name__ == "__main__":
    m()

 

예제 입력 1 

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1 

1

예제 입력 2 

3 3
IOX
OXP
XPP

예제 출력 2 

TT