[n18352] 특정 거리의 도시 찾기 in python

 

 

---

(처음 든 생각)

BFS 같다.. 느낌이

1번 도시에서 2번, 3번 도시를 가야하고?

2번 도시에서 갈 수 있는 곳이 있는지, 조건을 부합하는 지 확인한 뒤

3번 도시도 확인해야 하니까!!

 

---

(처음 푼 풀이) : BFS

 

처음에 이 문제도 EOFError를 사용해야 하는 줄 알고 좀 헤맸다.

문제 좀 잘 읽어볼 것..

 

BFS 알고리즘이니까, 큐를 이용해서 풀어야한다.

 

위 예제를 생각해보면,

k=2 이다. (거리정보)

1번 도시에서 갈 수 있는 도시는 2번, 3번

따라서 큐에 2번, 3번을 넣고 방문처리를 해준다.

이때 방문처리 리스트를 통해  답을 구할 것이다.

 

처음엔 set()을 이용했는데,

시간초과가 떠서 ㅠㅠ

 

popleft로 큐에서 데이터를 꺼내온다. (2번)

2번에서 갈 수 있는 도시는 3번, 4번

하지만 3번 도시는 이미 방문처리가 되어 있으므로

4번 도시만 큐에 append 한다.

 

큐에서 데이터를 꺼내온다 (3번)

3번은 이미 방문처리가 되어있으므로

아무런 작업을 하지 않는다.

 

큐에서 데이터를 꺼내온다 (4번)

4번 도시를 방문처리하고

 

큐가 비었으니 반복문을 종료한다.

 

 

import sys
from collections import deque

n, m, k, x = map(int, sys.stdin.readline().rstrip().split())
dic = [[] for _ in range(n + 1)]

for i in range(1, m + 1):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    dic[a].append(b)

queue = deque([x])
visited = [0 for _ in range(n + 1)]
visited[x] = 1
now = 0

while queue:
    node = queue.popleft()

    for i in dic[node]:
        if not visited[i]:
            queue.append(i)
            visited[i] = visited[node] + 1
        
for i in range(n + 1):
    if visited[i] == k + 1:
        print(i)
if k + 1 not in visited:
    print(-1)

---