[Python/BOJ] 21736. 헌내기는 친구가 필요해

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

21736번: 헌내기는 친구가 필요해

문제

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

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

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

입력

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

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

출력

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

풀이

Code

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
campus = [list(map(str, input().rstrip())) for _ in range(n)]
ans = 0
# 1. 도연이의 위치 인덱스 구하기
for i in range(n) :
    for j in range(m) :
        if campus[i][j] == 'I' : x, y = i, j; break
    else : continue
    break
# 2. 방문 여부 리스트 생성
visited = [[False] * m for _ in range(n)]
# 3. 큐에 도연이 위치 삽입
queue = deque()
queue.append((x, y))
# 4. 방문 처리
visited[x][y] = True
# 5.
while queue :
    # 5-1. 큐에서 위치 인덱스 반환
    x, y = queue.popleft()
    for dir_x, dir_y in [(-1, 0), (1, 0), (0, -1), (0, 1)] :
        nx, ny = x + dir_x, y + dir_y
        # 예외처리
        if nx < 0 or nx >= n or ny < 0 or ny >= m : continue
        # 다음 위치에 방문하지 않고 벽이 아닌 경우
        if not visited[nx][ny] and campus[nx][ny] != 'X':
            # 방문 처리
            visited[nx][ny] = True
            # 다음 위치가 사람일 경우 카운트
            if campus[nx][ny] == 'P' : ans += 1
            # 큐에 다음 위치 삽입
            queue.append((nx, ny))
# 6. 결과 출력
print(ans) if ans else print('TT')