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

헌내기는 친구가 필요해 문제 바로 가기

풀이 날짜: 2026-01-18

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n,m = map(int, input().split())
graph = [list(input().strip()) for _ in range(n)]
visited = [[False]*m for _ in range(n)]

dx = [0,0,-1,1]
dy = [-1,1,0,0]

def dfs(x,y):
    global count
    stack = [(x,y)]
    visited[x][y] = True

    while stack:
        x,y = stack.pop()
        if graph[x][y] == 'P':
            count += 1

        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny]:
                if graph[nx][ny] != 'X':
                    visited[nx][ny] = True
                    stack.append((nx,ny))

count = 0

found = False
for i in range(n):
    for j in range(m):
        if graph[i][j] == 'I':
            dfs(i,j)
            found = True
            break
    if found:
        break

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

문제 접근

이 문제는 n x m 격자에서 시작 위치 I에서 출발해 상/하/좌/우로 이동하면서, 벽 X는 통과하지 못하고, 이동 가능한 모든 칸을 탐색한 뒤 만나는 사람 P의 수를 세는 문제다. 탐색을 끝냈을 때 P를 하나도 못 만나면 “TT”, 한 명이라도 만나면 그 숫자를 출력한다. 결국 “그래프 탐색(DFS/BFS)으로 연결된 영역을 전부 돌면서 조건에 맞는 칸을 카운트”하는 전형적인 문제다.

visited가 필요한 이유 (무한 루프 방지)

격자 탐색은 한 칸에서 네 방향으로 이동이 가능하므로, 방문 체크가 없으면 같은 칸을 계속 왕복하면서 무한 반복에 빠진다. 이를 막기 위해 visited[n][m]를 두고, 어떤 칸을 스택/큐에 넣는 순간(혹은 꺼내서 처리하는 순간) 방문 처리한다. 이 문제에서는 “한 번 방문한 칸은 다시 볼 필요가 없다”가 성립하므로, visited는 시간복잡도를 O(n*m)으로 제한하는 데 핵심 역할을 한다.

“I는 하나라서 찾으면 break” 최적화의 의미