99클럽 코테 스터디 10일차 TIL / BFS(너비 우선 탐색)

✏️ 문제

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

 

어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.

이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.

예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.

 

이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S2

✅ 소요 시간: 14분 49초

✅ 권장 시간: 1시간

 

💡 풀이

1) 문제 유형 파악

입출력 예시와 '최단 거리' 키워드를 보고 BFS 문제라는 것을 알 수 있었다. 9일차에 푼 문제와 비슷한 유형인 것 같아 푸는 데 어려움은 없었다.

 

2) 아이디어 흐름

BFS 구현은 지금까지 푼 문제들과 큰 차이가 없기 때문에 생략하고 출력 조건을 처리하는 부분에 대해서 정리해보려고 한다.

 

① 최단 거리 K인 도시가 하나라도 있는지 체크하기 위한 flag 변수 사용

최단 거리가 K인 도시가 아예 없으면 -1을 출력하고 그렇지 않으면 도시 번호를 오름차순으로 출력해야 하는 것이 문제에서 요구한 조건이다.

 

flag = False로 두고 visited 리스트를 돌면서 값이 K+1인 요소가 있으면 flag = True로 바꾼 후 break로 for문을 탈출한다. visited 리스트를 다 돌았는데도 flag가 False라면 정답은 -1이 되고  flag가 True면 visited 리스트를 한 번 더 돌면서 값이 K+1인 요소의 인덱스를 출력하면 된다.

 

② ⚠️ 오름차순의 함정 조심 ⚠️

처음에 코드를 제출했을 때 채점이 아주 조금 진행되다가 갑자기 틀렸습니다가 떴다. 로직 잘못된 부분이 없는데? 하던 중에 '오름차순'에서 깨달음을 얻다..!

 

# 틀린 코드
if not flag:
    print(-1)
else:
    for i, val in enumerate(sorted(visited)):
        if val == K+1:
            print(i)

 

문제에서 오름차순으로 출력하라길래 습관적으로 sorted를 적용하고 인덱스를 출력했다.

 

...생각해보니까 K=2, visited=[0, 2, 3, 2]라고 할 때 답은 2인데 정렬을 하고 나면 [0, 2, 2, 3]으로 기존 순서가 깨지게 되어 잘못된 인덱스를 출력하게 되는 게 오답의 원인이었다.

 

3) 구현

import sys

from collections import deque

input = sys.stdin.readline

N, M, K, X = map(int, input().split())

country = {k: [] for k in range(1, N+1)}

for _ in range(M):
    A, B = map(int, input().split())
    
    country[A].append(B)

queue = deque([X])

visited = [0]*(N+1)

visited[X] = 1

while queue:
    city = queue.popleft()
    
    for node in country[city]:
        if visited[node] == 0:
            visited[node] = visited[city]+1
            
            queue.append(node)

flag = False

for dist in visited:
    if dist == K+1:
        flag = True
        break
    
if not flag:
    print(-1)
else:
    for i, val in enumerate(visited):
        if val == K+1:
            print(i)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 없음

❗ 배운 점

• 경우에 따라서는 조금만 유연하게 사고한다면 sort 메서드, sorted 함수를 쓰지 않고도 정렬된 값을 출력할 수 있다 😎