특정 거리의 도시 찾기 (DFS,BFS/백준 18352번)

특정 거리의 도시 찾기

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

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

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

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

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

 

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

 

입력 조건

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

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

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

 

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

 

출력 조건

X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.

이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.

 

입력

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

출력

4

 

 

---

풀이

풀이 아이디어 정리 : 먼저 도시의 개수가 n 이라는 것은 노드의 개수가 n개라는 것이다.

도로의 개수가 m개라는 것은 도로정보가 m개라는 듯이므로 정보를 받아올때 2개씩(이어진 노드정보) m줄을 받아와야한다는 뜻이다. 거리정보가 k라는 것은 최소거리가 k라는 것이므로 출발 노드 x로부터 최소거리를 노드의 값으로 변경시켜 그 값이 2인것들만 출력 조건에 따라 한줄에 하나씩 오름 차순으로 출력하면 된다.

 

순서

1. 먼저 n,m,k,x의 값을 받아온다.

2.2개 변수가 m줄인 2차원 리스트를 받아온다.

3.함수에 출발노드를 넣어 시작한다.

4.출발노드 주변에 연결된 노드의 값을 1로 바꾼다.

5.1로 바꾼 노드들을 모두 큐에 넣고 그와 연결된 노드들 중 이미 1인 노드를 제외한 노드의 값을 2로 바꾼다.

#즉 bfs를 사용할 것이니 deque메소드를 선언해줘야한다.

6.2로 바꾼 노드들을 모두 큐에 넣는다.

7.큐의 값을 리스트로 바꾼다.

8.리스트에 들어간 값을 한 줄에 하나씩 오름차순으로 출력한다.

 

풀이 시간 : 30분

내 풀이 시간: 1시간

문제점:

• 헷갈리는 문법요소가 많아서 찾아보다보니 늦었다..ㅠ 그래도 헷갈리는것들은 다 블로그에 정리해두었으니 다음엔 더 빨리 풀 수 있을 것같다.
• 코드에서 답은 맞게 나오는데 이상하게 백준에서 여러번 시간제한이 걸렸었다. 나중에 보니 이건 내가 인접 행렬과 인접리스트의 차이를 제대로 이해 하지 못한 것에서 발생한 문제였다. 나는 단순히 인접행렬 = 모든 노선 정보를 입력한 것, 인접리스트 = 이어지 노선의 정보만 입력한 것이라고 이해하고 있었는데 더 정확하게는  아래 처럼 graph[a]만 넣어도 연결 노선들이 쏟아지는 형태였다..!  sys부터 여러가지 고쳤는데 이것때문이었다니...ㅠㅜ 그래도 개념을 더 잘 이해하고 넘어가는 것 같아 뿌듯하다.

graph[a].append(b)

 

---

코드

내가 제작한 코드

import sys
from collections import deque

#입력 받아오기
input = sys.stdin.readline
n,m,k,x = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split(' '))
    graph[a].append(b)

#최초값 x를 넣은 큐와 각 노드들의 최단거리응 넣을 리스트 선언
queue = deque([x])
data = [-1]*(n+1)
data[x] = 0

#큐가 빌때까지(모든 노드에 최단거리 부여하기)
while queue:
    #큐 가장 왼쪽을 nx에 빼오기
    nx = queue.popleft()
    for i in graph[nx]:
        #출발노드가 nx와 같을때
        if data[i]==-1:
            #방문하지않은 노드일경우 그리고 출발노드가 아닌경우
            #최단거리 부여(출발노드의 값+1)
            data[i] = data[nx] + 1
            #같은 최단거리를 가진 것들이 큐에 들어감
            queue.append(i)

    
if k in data:
    for i in range (1,n+1):
        if data[i] == k:
            print(i)
else:
    print(-1)