[Python] 헌내기는 친구가 필요해 (백준 21736번 파이썬)

 

예제 입력 1

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1

1

예제 입력 2

3 3
IOX
OXP
XPP

예제 출력 2

TT

 

문제 이해

- 도연이가 학교 안에서 사람을 몇 명 만날 수 있는지를 구하는 문제입니다.

- X는 벽, O는 빈 공간, I는 도연이, P는 사람이며, 상하좌우로 이동합니다.

 

문제 풀이

- 단순한 BFS문제입니다. 캠퍼스의 정보를 받아오는 동시에 도연이의 현재 위치를 좌표로 받아 저장합니다.

- 해당 좌표로부터 BFS를 수행하며, P(사람)을 만날때마다 count를 +1 합니다.

- 만약 아무도 만나지 못했다면 TT를 출력하면 됩니다.

 

코드

#백준 21736 헌내기는 친구가 필요해
# o : 빈 공간
# x : 벽
# I : 도연
# P : 사람. 몇명의 사람을 만날 수 있는지 출력.
from collections import deque
n,m = map(int, input().split())
graph = []
for i in range(n):
    ipt = list(input())
    graph.append(ipt)
    for j in range(len(ipt)):
        if ipt[j] == 'I':
            doyean = [i,j] #도연이 좌표

visited = [[False]*m for _ in range(n)]
count = 0 #사람을 만난 횟수
q=deque()
x, y = doyean
visited[x][y] = True
q.append(doyean)

while q:
    x,y = q.popleft()
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < n and 0<= ny < m:
            if visited[nx][ny] == False and graph[nx][ny]!='X':
                visited[nx][ny] = True
                q.append((nx,ny))
                if graph[nx][ny]=='P': #사람 만나면 +1
                    count += 1

answer = 'TT' if count==0 else count
print(answer)