[이코테] DFS/BFS/ 특정 거리의 도시 찾기

📕 문제

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

 

 

📄 내가 생각한 풀이

BFS 사용,

💻 내 코드

visited 사용해서 다시 푸는데 오류

from collections import deque
import sys

# n,m,k,x = map(int, input().split())
n,m,k,x = map(int, sys.stdin.readline().split())


graph = [[]for _ in range(n+1)]

# print(graph)
# q는 출발도시
q = deque([x])

# set()으로 설정안하면 백준에서 오류
visited = set()

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

# print(graph)

# 최단거리 k인 도시 하나도 없으면 -1, 전체 -1로 초기화
distance = [-1]* (n+1)
# 출발도시 x에서 x로 가는 최단 거리는 항상 0
distance[x] = 0

# BFS수행


while q:
    now = q.popleft()
    # 현재 도시에서 이동할 수 있는 모든 도시 확인
    for next_node in graph[now]:
        # 아직 방문하지 않은 도시일 때 : -1
        if next_node not in visited:
            # 최단 거리 갱신

            distance[next_node] = distance[now]+1
            q.append(next_node)
            visited.add(next_node)


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

 

💻 이코테 답안

  from collections import deque

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

# print(graph)


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

# print(graph)

# 최단거리 k인 도시 하나도 없으면 -1, 전체 -1로 초기화
distance = [-1]* (n+1)
# 출발도시 x에서 x로 가는 최단 거리는 항상 0
distance[x] = 0

# BFS수행
# q는 출발도시
q = deque([x])


# 여기부터 이해 다시
while q:
    now = q.popleft()
    # 현재 도시에서 이동할 수 있는 모든 도시 확인
    for next_node in graph[now]:
        # 아직 방문하지 않은 도시일 때 : -1
        if distance[next_node] == -1:
            # 최단 거리 갱신
            distance[next_node] = distance[now]+1
            q.append(next_node)


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

if check == False:
    print(-1)

 

📁 참고자료

 

 

https://velog.io/@kyeun95/백준-18352번-특정-거리의-도시-찾기

[백준] 18352번 : 특정 거리의 도시 찾기

 

☺️ 새로 알게 된 지식