[백준] 21736번 - 헌내기는 친구가 필요해 | 파이썬

SangJin Ham·2023년 8월 22일

BFS 백준 시뮬레이션 알고리즘

백준

목록 보기

44/51

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

시간제한 : 1초
메모리 제한 : 1024MB

문제

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를 출력한다.

예제 입력 1

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1

코드

import sys
from collections import deque

# N, M 입력
N, M = map(int, sys.stdin.readline().strip().split())

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
ch = [[0] * M for _ in range(N)]

campus = []
Q = deque()

# 캠퍼스 정보
for i in range(N):
  # 캠퍼스 정보의 첫 번째 행 입력
  campus.append(list(map(str, sys.stdin.readline().strip())))

  for j in range(len(campus[i])):
    # 그 행에 도연이가 있냐 ?
    if campus[i][j] == 'I':
      # 도연이의 위치 큐에 삽입
      Q.append([i, j])
      ch[i][j] = 1

answer = 0

# 큐가 비었을 때까지 반복
while Q:
  # 현재 큐의 길이만큼 좌표들 다 꺼내기
  for _ in range(len(Q)):
    # 좌표 하나 꺼내기
    r, c = Q.popleft()
    
    # 상우하좌 좌표 이동
    for i in range(4):
      nr, nc = r + dr[i], c + dc[i]

      # 캠퍼스 밖으로 벗어나지 않고,
      # 방문했던 위치가 아니며,
      # 벽이 아닌 경우에만 이동
      if 0 <= nr < N and 0 <= nc < M and ch[nr][nc] == 0 and campus[nr][nc] != 'X':
        # 사람을 만났다면
        if campus[nr][nc] == 'P':
          # 만난 사람의 수 + 1
          answer += 1

        # 방문했다고 표시
        ch[nr][nc] = 1
        # 해당 좌표 큐에 삽입
        Q.append([nr, nc])

# 만난 사람의 수가 1명 이상인 경우
if answer:
  # 사람의 수 출력
  print(answer)

# 만난 사람의 수가 0명인 경우
else:
  # TT 출력
  print('TT')

풀이

시간 : 852ms
메모리 : 40872KB

해당 문제는 아래 문제들과 같이 BFS와 시뮬레이션 알고리즘을 이용해 풀이하면 된다.
1. 14940번 - 쉬운 최단거리
2. 7576번 - 토마토

BFS 알고리즘 부분을 돌리기 전에 변수 초기화 및 설정을 하자.

N, M입력
다른 위치로 접근하기 위한 dr, dc 정의
해당 위치에 방문했는지 확인할 수 있는 ch 리스트 생성
캠퍼스 정보 campus 리스트를 생성해 각 행의 정보를 입력
- 입력받을 때 도연이의 위치(I)를 찾아 큐에 삽입해 시작 위치로 설정

이제 BFS 알고리즘을 돌려보자
while문은 더이상 방문할 위치가 없을 때까지 반복한다.
for문은 현재 현재 큐에 삽입되어 있는 위치들만큼 반복한다.
for문이 시작되면 위치 하나를 꺼내 r와 c에 좌표를 저장한다.
그리고 상우하좌 방향으로 이동할 좌표 nr, nc를 정의한다.
이때, 캠퍼스 밖으로 벗어나지 않고, 벽이 아니고, 방문하지 않은 위치인 경우에만 campus[nr, nc]로 이동한다.
그렇게 이동한 좌표 campus[nr][nc]에 만약 사람(P)을 만났다면 answer += 1를 해준다.
그리고 방문했다는 표시로 ch[nr][nc] = 1를 해주고, 해당 좌표를 큐에 삽입한다.