Algorithm

백준 21736번: 헌내기는 친구가 필요해 (S2) - Python 풀이

서서리 2025. 6. 29. 16:35
SMALL

문제 설명

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

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

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

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

입력

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

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

출력

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

예제 입력 1

3 5
OOOPO
OIOOX
OOOXP

예제 출력 1

1

예제 입력 2

3 3
IOX
OXP
XPP

예제 출력 2

TT

풀이 과정

I의 위치에서 탐색을 시작하고, 상하좌우 방향으로 이동할 수 있습니다. O 또는 P가 적힌 위치로는 이동 가능하지만, X가 적힌 곳으로는 이동할 수 없습니다.

결국 I에서 O와 P로 이동하면서 P가 나올 때마다 카운트 하면 되는 문제입니다. 그래프 탐색 DFS, BFS 뭐든 상관없는데 저는 BFS를 사용했습니다.

처음 I가 위치한 (x,y) 좌표를 큐에 넣고 탐색을 시작합니다.

정답 코드

from collections import deque
# 입력
N, M = map(int, input().split())
grid = [[] for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
answer = 0

# I의 행과 열을 저장할 변수
row, col = 0, 0
for i in range(N):
    grid[i] = list(input())
    try:
        # I가 있는 위치의 행과 열 값을 저장
        col = grid[i].index('I')
        row = i
    except:
        continue

# I가 있는 위치는 방문 처리
visited[row][col] = True
# I가 있는 위치를 큐에 넣음
queue = deque([(row, col)])
# 상하좌우 이동 벡터
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 너비 우선 탐색
def BFS(queue):
    global answer
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 꺼낸 값 x,y
        x, y = queue.popleft()
        # x,y의 위치에서 상하좌우 4방향으로 이동
        for d in range(4):
            # 새 좌표 설정
            nx = x + dx[d]
            ny = y + dy[d]
            # 해당 좌표가 유효 범위 내에 있고, 아직 방문하지 않았던 곳이고, O 또는 P가 적혀 있다면
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] and grid[nx][ny] != 'X':
                # 큐에 추가
                queue.append((nx, ny))
                # 방문 처리
                visited[nx][ny] = True
                # 이동한 위치가 P면
                if grid[nx][ny] == 'P':
                    # 카운트 증가
                    answer += 1

# 너비 우선 탐색 실행
BFS(queue)
if answer == 0:
    # 0개면 TT 출력
    print("TT")
else:
    print(answer)

이상입니다.

LIST