[Baekjoon] 21736 [헌내기는 친구가 필요해] 입맛대로 문제풀이

카테고리

• 그래프 탐색 (BFS, DFS)

전형적인 그래프 탐색 문제인 “헌내기는 친구가 필요해” 문제입니다. 이 문제는 대표적인 BFS로 풀 수 있는 문제 중 하나라고 생각해서, BFS로 문제를 풀었습니다. (DFS로 푼 버전은 추후 업로드 예정...)

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

graphs = []
n, m = map(int, input().split())

# 그래프 만들기
for _ in range(n):
    maps = input().rstrip()
    infos = [char for char in maps]
    graphs.append(infos)
# start point
for i in range(n):
    for j in range(m):
        if graphs[i][j] == 'I':
            sx, sy = j, i

# O : 빈공간, X : 벽, I : 도연, P : 사람
# bfs로 접근하는 것이 맞지 않을까...
def bfs(start_x, start_y):
    meet_count = 0
    ny = [-1, 1, 0, 0]
    nx = [0, 0, -1, 1]
    queue = deque()
    queue.append((start_y, start_x))
    visited = set()
    visited.add((start_y, start_x))

    while queue:
        y, x = queue.popleft()
        # 순회
        for i in range(4):
            new_x = x + nx[i]
            new_y = y + ny[i]

            if 0 <= new_y < n and 0 <= new_x < m:
                if (new_y, new_x) not in visited and graphs[new_y][new_x]!='X':
                    visited.add((new_y, new_x))
                    if graphs[new_y][new_x] == 'P':
                        meet_count += 1
                    queue.append((new_y, new_x))

    return meet_count

result = bfs(sx, sy)
if result == 0:
    print('TT')
else:
    print(result)
    

이 문제는 시작점을 찾아, 벽(X)를 제외한 모든 공간을 탐색하며, 만날 수 있는 사람(P)의 수를 계산하는 문제입니다. 이 문제에서는 좌표들을 그래프로 만들어 풀 수 있고, 막힌 부분을 제외하고 방문할 수 있는 모든 케이스를 빠짐없이 방문해야 하는 문제라고 인식하여, BFS로 접근했습니다.

다음과 같은 경우를 이제 2차원으로 나타내서 문제를 푸는 방식이라고 이해하시면 됩니다.

OOOPO
OIOOX
OOOXP

또한, 전형적으로 BFS라는 문제를 어떻게 접근할지 알 수 있다면, 어렵지 않게 접근할 수 있는 문제라고 생각합니다. 저는 실제로, 한두칸씩 이동하는 시나리오라면, BFS로 접근하는 방법을 사용합니다. BFS에 대해 헷갈리시거나, 점검을 원하신다면, 다음 경로에서 보실 수 있습니다.

queue와 방문 여부를 확인하는 visited 변수를 만들었고, 전형적인 BFS 문제처럼, 조건부로 계속 순회하는 코드로 작성했습니다.

탐색 로직은 크게 다음과 같이 정리했습니다.

1. 그래프를 입력하고, I의 위치를 찾는다.
2. 시작 지점부터 visited에 표시하고, 방문 여부를 확인한다.
3. I의 위치 (예시의 경우 (1,1))에서 시작해 BFS를 수행한다.
   • 탐색 범위는 다음과 같이 한정한다 : 현재 좌표가 그래프의 범위를 벗어나지 않고, 벽(X)가 아니여야 한다.
   • 방문하지 않은 지점이여야 한다. (이미 방문을 했다면, visited에 변화를 주지 않는다) -> 간단하게 말하면, 중복되지 않아야 한다로 생각하시면 됩니다. (방문했다면 skip~)
   • 벽(X)가 아니라면, 방문처리 후 큐에 넣는다. 그리고, 여기서 만약 현재 방문한 칸이 P라면 만난 사람 횟수(P, 코드상에서는 meet_count)를 +1한다.
4. 탐색이 끝난 뒤 결과를 출력한다.
   • 만난 사람이 한 명도 없다면 (meet_count == 0)이라면, ‘TT’를 출력한다.
   • 한명이라도 만난 사람이 있다면, 만난 횟수를 출력한다.

다음의 방법으로 진행할 때 시간복잡도는 $O(N*M)$이 발생합니다.

아마 이 문제의 경우, BFS에 대해 아직 개념이 부족하거나(대표적으로 저…) 그래프 탐색을 잘 이해하지 못한다면 어려울 수 있지만, 이 개념만 알고있다면, 바로 머릿속에 BFS가 떠오를 것입니다.