(백준) 18352번: 특정 거리의 도시 찾기 - 파이썬 풀이 (BFS, 그래프)

<포스팅 요약>

1. 문제풀러가기

2. 문제 해결 코드

3. 로직 분석

---

1. 문제풀러가기

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

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

 

문제 요약:

- X(시작지점)도시 부터 K만큼 이동해서 갈 수 있는 도시 출력.

- 중요포인트 : 오름차순 정렬!

 

예) 

N=4, M=4, K=2, X=1일 때

도시는 1~4까지 있음 => N=4

주어진 도로의 개수는 4개 => M=4

최단 거리가 2 이어야됨 => K=2

시작 도시는 1 => X=1

 

예제 입력	예제 출력
4 4 2 1 1 2 1 3 2 3 2 4	4

1부터 4까지 이동할 때 최단거리가 2임  (1 => 2 => 4)

1부터 3까지 이동할 때의 최단거리는 1임 (1=>3) ,

** 1=>2=>3이렇게 갈 수 있지만 "최단거리"는 (1=>3) 1이므로 탈락!!

그래서 도시 4까지 갈대 최단거리가 2이므로, 4출력

---

2. 문제 해결 코드

코드 (성공)

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

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
#도로의 정보 담아주기


res = []
def bfs(x):
    queue = deque([x])
    visited[x] = 1
    #방문한 것을 체크해주기 위해 1부터 시작
    
    while queue:
        y = queue.popleft()
        if visited[y] == k+1:
        	#방문 체크를 위해 1부터 시작하여 
            #카운트한 거리가 1이 더 더하여짐
            res.append(y)
            continue
        for i in graph[y]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = visited[y]+1
                


bfs(x)
if len(res) == 0:
    print(-1)
else:
    res.sort()
    #오름차순 정렬
    
    for i in res:
        print(i)

 

처음에 바보같이 오름차순을 안해줬었음.. ㅠ 

---

3. 로직분석

그래프와 BFS 알고리즘을 사용하여 접근했다.

- graph리스트에 도로의 정보를 담아준다.

- visited[x] = 1을 한 이유는 방문한 것을 체크해 주기 위해서다.

*(도로정보에 1=>3, 3=>4, 4=>1이 있을 수 있으므로 시작지점도 방문체크를 해줘야 한다.

1=>1의 최단 거리는 0이다. )

- visited[i] = 0은 아직 방문하지 않았으며, x도시부터의 최단거리가 계산되지 않은 도시들 이므로 , 

queue.append(i)를 통해 queue에 추가해주고, visited[y]+1을 통해 최단 거리 계산을 해준다.

- 시작이 0부터 하는것이 아니라 1부터 하므로 , 최단거리 체크시 k가아닌 k+1로 체크해준다.

- 최단거리가 k+1과 일치하는 것들만 res리스트에 담아준다

- res에 아무것도 들어있지 않으면 -1을, 정보가 들어있으면 오름차순으로 정렬후 출력해준다.