[dfs/bfs]특정 거리의 도시 찾기

문제요약

1~N번까지의 도시와 M개의 단방향 도로가 존재
모든 도로의 거리는 1
특정 도시 X에서 출발하여 도달할 수 있는 모든 도시 중 최단 거리가 K인 모든 도시의 번호를 출력하라
(없으면 -1 출력)

 

입출력 예시

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

4

 

정답

from collections import deque
# ======== [ 1 ] ==========
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)
    
# ======== [ 2 ] ==========
# Q1. -1로 초기화 하는 이유 and n+1개만큼 만드는 이유는 ? 
distance = [-1] * (n+1)
# Q2. 출발 도시까지의 거리를 0으로 설정?
distance[x] = 0


# ======== [ 3 ] ==========
# Q3. x로 초기화 하는 이유?
q = deque([x])

while q:
    now = q.popleft()
    # Q4. 왜 graph[now]까지 반복문을 돌리는지?
    for i in graph[now]: 
        if distance[i] == -1:
            distance[i] = distance[now]+1
            q.append(i)

# ======== [ 4 ] ==========
check = False 
for i in range(1,n+1):
    if distance[i] == k:
        print(i)
        check = True
if check == False:
    print(-1)

 

 

풀이

사실 문제만 30분 보다가 답지를 봤는데도 모르겠어서 다시 정리하는 것임..

처음 답지를 보면서 공부할 때 이해가 안되던 부분을 Q1~Q4로 체크해두고

정리하면서 나름대로 답을 찾다보니 아주 조금 dfs에 대해 이해가 되었다..!

 

 

 

# ======== [ 1. 입력 ] ==========

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)

도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호를 담은 변수를 입력받음

그리고 graph라는 이름의 list를 만들어서

graph[a]에는 도시번호, graph[a][]에는 a도시와 연결된 도시번호를 입력받음

(이 때, 도시는 1번부터 시작하기 때문에 graph[0]은 사용하지 않고 graph[1] ~ graph[n]까지 입력받게 될 것임

 

 

# ======== [ 2. 변수 선언 및 초기화 ] ==========

# Q1. -1로 초기화 하는 이유 and n+1개만큼 만드는 이유는 ? 
distance = [-1] * (n+1)
# Q2. 출발 도시까지의 거리를 0으로 설정?
distance[x] = 0

 

Q1-1. -1로 초기화 하는 이유 

A1-1. 사실 -1 이 아니어도 됨

어차피 중요한 것은 출발도시에서 출발도시까지의 거리를 0으로 초기화 해두는 것과 그 다음 도시를 방문할 때 +1씩 거리를 추가하는 것임

-1은 그냥 방문하지 않은 도시임을 확인하기 위한 용도이며

-1가 아닌 -2, -3 같은걸로 초기화 해도 문제는 없지만 가독성을 위해서인 듯 하다

 

 

Q1-2. n+1개만큼 만드는 이유는 ?       

A1-2. distance[x]는 출발도시에서 x번 도시까지의 최단거리를 담은 리스트임

도시번호를 1~N까지 넘버링하기 때문에 마지막 출력시 for문을 돌릴 때 range(1:n+1)의 범위로 설정함

도시의 개수는 N개이고 [0]인덱스는 사용하지 않기 때문에 and n+1개를 만들어야 n번째 인덱스를 사용할 수 있어서.

 

Q2. 출발 도시까지의 거리를 0으로 설정?

A2. Q1-1과 연결됨.

출발 도시까지의 거리를 0으로 초기화하고 그 다음 도시를 방문할 때마다 이전에 방문하지 않은 도시일 때 +1 시키면 최단거리를 구할 수 있기 때문에.

 

 

 

# ======== [ 3. bfs 수행 ] ==========

# Q3. x로 초기화 하는 이유?
q = deque([x])

while q:
    now = q.popleft()
    # Q4. 왜 graph[now]까지 반복문을 돌리는지?
    for i in graph[now]: 
        if distance[i] == -1:
            distance[i] = distance[now]+1
            q.append(i)

 

Q3. x(출발도시번호)로 초기화 하는 이유?

deque에 처음 출발도시번호를 넣고 연결된 다른 도시(i)를 찾은 후(처음 방문한) 

다시 그 도시(i)로부터 연결된 도시들을 찾게 됨. 

 

 

ex) 1 -> 2-> 3으로 간다고 가정하면

distance = [[-1], [-1],[-1],[-1],[-1]]

deque에 출발도시번호 1을 담아서 초기화

 

Q4. 왜 graph[now]까지 반복문을 돌리는지? 

now = 현재 deque에 있는 요소 = 출발도시

입력단계에서 graph[1]에 도시번호 1번에서 갈 수 있는 도시들을 넣어놨음 

graph[1]의 요소 하나하나씩 돌면서 같은 인덱스의 distance[i]의 값을 확인

 

주어진 입출력 예시에 의하면 graph[1] = [2,3] 일것이므로 

처음 distance[2] 의 값을 확인함

-> distance[2] == -1 이니까 조건 만족 

-> distance[2] = distance[1]+1 : 

-> q.append(2)를 통해 deque에 2 넣음

 

같은 인덱스의 distance의 값이 -1이라면 방문하지 않은 것이므로 

distance[now] > distance[1](1에서 1까지 가는 최단거리)

현재의 거리를 나타내는 distance[now] 에 1을 더함(각 노드간 거리는 1이라는 문제 조건)

 

방문하지 않은 도시(i)를 방문했다면 그 도시에서 갈 수 있는 모든 도시를 다시 확인하게 되는데

그걸 deque에 도시번호(i)를 넣고 다시 while문을 돌리는 방식으로 진행하게 됨

 

만약 graph[now] 를 돌면서 (== now번 도시에서 갈 수 있는 도시들 중)

distance[i]에 -1이없다면 (방문할 수 있는 곳이 더이상 없다면)

deque에 더이상 추가할 수 없기 때문에 while문이 끝나게 됨

 

결국 처음 deque에 넣은 출발도시부터 시작해서 출발도시와 연결된 모든 도시들까지의 거리가 distance에 담기게 됨

 

 

 

# ======== [ 4. 출력 ] ==========

check = False 
for i in range(1,n+1):
    if distance[i] == k:
        print(i)
        check = True
if check == False:
    print(-1)

 

while문을 돌면서 distance[i] 리스트는 출발도시에서 i번째 도시까지의 최단거리를 담고 있을 것임

for문으로 distance에 있는 최단거리가 k인 도시번호(i)를 출력.

 

최단거리가 k인 도시가 하나라도 있는지 여부를 판단하기 위해 check 변수 사용

하나라도 있으면 if문 내에서 true로 바꾸기, 없다면 그대로 false일 것이고

for문을 돌고 나서도 check가 false라면 -1 출력

 

 

 

 

 

참조

- 이것이 취업을 위한 코딩테스트다. with 파이썬