046 특정 거리의 도시 찾기

첫번째 코드

 

BFS 문제와 그래프 그리는 것을 신경쓰면서 코드를 작성하자.

사실 이전에 푼 BFS 문제와 비슷하게 느껴졌다!

 

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

n, m, k, x = map(int, input().split())
A = [[] for _ in range(n+1)]
answer = []
visited = [-1] * (n+1)

for _ in range(m):
    s, e = map(int, input().split())
    A[s].append(e)

def BFS(x):
    queue = deque()
    queue.append(x)
    visited[x] += 1

    while queue:
        now = queue.popleft()
        for i in A[now]:
            if visited[i] == -1:
                visited[i] = visited[now] + 1
                queue.append(i)

BFS(x)

for i in range(n+1):
    if visited[i] == k:
        answer.append(i)

if not answer:
    print(-1)
else:
    answer.sort()
    for i in answer:
        print(i)

 

통과!

그래프를 그리는 연습을 조금 더 해봐야겠다.

또한 BFS와 DFS의 차이가 아직 명확하지 않다...

그래도 BFS코드와 익숙해지는 중!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/18352.%E2%80%85%ED%8A%B9%EC%A0%95%E2%80%85%EA%B1%B0%EB%A6%AC%EC%9D%98%E2%80%85%EB%8F%84%EC%8B%9C%E2%80%85%EC%B0%BE%EA%B8%B0

programmers/백준/Silver/18352. 특정 거리의 도시 찾기 at main · ornni/programmers