헌내기는 친구가 필요해_21736

박상민·2024년 5월 24일

백준

목록 보기

25/36

문제

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

도연이가 다니는 대학의 캠퍼스는
$N \times 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를 출력한다.

예제 입력 1

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1

예제 입력 2

3 3
IOX
OXP
XPP

예제 출력 2

TT

문제 이해

도연이(I)가 상하좌우로 움직이며 P를 얼만큼 만나는지 출력하고 아니면 TT를 출력하는 문제

도연이의 위치(좌표값)를 정의하고 이동방향을 정의해 상,하,좌,우 이동하며 범위 내에 있고 방문한 곳은 1 아닌 곳은 0으로 처리하며 P를 찾을 수 있음

문제 분석

캠퍼스의 크기: N × M
캠퍼스 정보: 'O'는 빈 공간, 'X'는 벽, 'I'는 도연이의 위치, 'P'는 사람

도연이는 상하좌우로 이동할 수 있으며, 벽을 넘을 수 없. 도연이가 움직일 수 있는 모든 방향을 탐색하면서 사람(P)을 찾을 수 있다.

자료구조 선택

따라서 이 문제는 그래프 탐색 문제로 볼 수 있다. 이때 너비 우선 탐색(BFS)을 사용하는 것이 적합합니다. BFS는 시작점에서 가까운 노드부터 차례로 탐색하므로 최단 경로를 찾는 문제에 적합합니다.

BFS를 선택한 이유?

도연이가 만날 수 있는 사람의 수를 탐색하는 과정에서, BFS는 도연이가 상하좌우로 이동하는 과정에서의 최단 경로를 탐색하게 되므로 자연스럽게 최단 거리 내에 있는 사람들을 먼저 탐색하는 것이 유리

BFS는 특정 거리 내에 있는 모든 노드를 탐색하는 데 효율적. 도연이가 이동할 수 있는 모든 경로를 동일한 깊이로 탐색하므로 포괄적으로 탐색 가능

이러한 이유로 BFS를 해당 문제 풀이의 자료구조로 선택하였다.

BFS는 기본적으로 큐(queue)를 사용하여 현재 노드에서 인접한 노드들을 먼저 탐색하고, 그 다음 인접한 노드들의 인접 노드들을 차례로 탐색할 수 있다.

캠퍼스 정보 저장을 위한 2차원 리스트 (board)
방문 여부를 기록하기 위한 2차원 리스트 (ch)
도연이의 위치를 저장하고 탐색을 위한 큐 (q)

알고리즘 설계

입력을 받아 캠퍼스 정보를 저장
도연이의 초기 위치를 큐에 삽입하고 방문 배열을 초기화
큐에서 좌표를 하나씩 꺼내어 상하좌우로 이동할 수 있는지 확인
이동 가능한 좌표가 벽이 아니고 방문하지 않은 곳이라면 큐에 삽입하고 방문 체크
만약 사람이 있는 좌표라면 사람 수를 증가
BFS 탐색이 끝난 후, 만약 만난 사람이 없다면 "TT"를 출력하고, 그렇지 않으면 사람 수를 출력

코드

#21736.py
from collections import deque
import sys

N, M = map(int, sys.stdin.readline().split())

board = [list(sys.stdin.readline().rstrip()) for _ in range(N)]

# 초기화
ch = [[0]*M for _ in range(N)] # 방문 배열 초기화 방문하지 않은 곳은 0, 방문한 곳은 1로 만들기 위함
dx = [-1, 1, 0, 0] # 좌표 이동 ( 좌, 우 )
dy = [0, 0, -1, 1] # 좌표 이동 ( 상, 하 )
q = deque() # 도연이의 위치를 담을 데크

# 도연이의 위치 정의
for i in range(N):
    for j in range(M):
        if board[i][j] == 'I':
            #도연이의 위치 큐에 삽입
            q.append([i, j])
            ch[i][j] = 1 # 도연이의 위치 방문 체크 

# 만난 사람 
per = 0

# bfs 탐색
while q:
    for _ in range(len(q)):
        # 좌표 하나 꺼내기
        x, y = q.popleft()
        # 상하좌우 탐색
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            # 범위 내에 있고, 벽이 아니고, 방문하지 않았다면
            if 0 <= nx < N and 0 <= ny < M and board[nx][ny] != 'X' and not ch[nx][ny]: # 방문하지 않은 곳이라면
                if board[nx][ny] == 'P':
                    per += 1
                q.append([nx, ny])
                ch[nx][ny] = 1

if per == 0:
    print("TT")
else:
    print(per)