[BOJ] 18325. 특정 거리의 도시 찾기

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

18352번: 특정 거리의 도시 찾기

 

1. 해결 방법

"""
1. 아이디어
- a와 b로 이루어진 1차원 배열 m개, 방문 기록을 판단할 수 있는 1차원 배열 n+1개, 거리 값을 삽입시킨 1차원 배열 n+1개
- 시작지점 x부터 시작해서 BFS로 돌면서 이동거리 +1

2. 시간복잡도
- O(V + E)
- V : 300000
- E : 1000000

3. 자료구조
- Queue
"""

 

 

2. 정답 코드

입력 예제(1)

4 4 2 1
1 2
1 3
2 3
2 4

출력 예제(1)

4

 

입력 예제(2)

4 3 2 1
1 2
1 3
1 4

출력 예제(2)

-1

 

입력 예제(3)

4 4 1 1
1 2
1 3
2 3
2 4

출력 예제(3)

2
3

 

코드

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

n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n + 1)]
# 방문 기록
chk = [False] * (n + 1)
# 이동거리 배열
distance = [0] * (n + 1)
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

# 결과
result = []

# bfs
def bfs(start):
    q = deque()
    q.append(start)
    chk[start] = True

    while q:
        now = q.popleft()
        for i in graph[now]:
            if chk[i] == False:
                chk[i] = True
                distance[i] = distance[now] + 1
                q.append(i)
                if distance[i] == k:
                    result.append(i)

# main
bfs(x)
if len(result) == 0:
    print(-1)
else:
    result.sort()
    for j in result:
        print(j)

아직 아이디어가 바로바로 떠오르지 않아서 조금 해맸던 문제이다. 
무엇보다도 문제 독해 능력이 부족했던 것 같고, 어떻게 해결할 것인지에 대한 아이디어가 떠오르지 않았다.

for문에서 bfs함수에 사용했던 i 변수와 함수 밖에서도 사용했더니 틀렸다고 나왔다. 변수 잘 바꿔주자...