[BOJ] Python 백준 특정 거리의 도시 찾기(18352)

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

 

 

bfs로 푸는 최단거리 문제이다. bfs로 방문하며, 이전 방문값에 +1한 값을 더하여 최종적으로 X에서 출발했을때, 거리가 K인 값을 찾는 문제이다.

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

N, M, K, X = map(int,input().split())
s = [[] for _ in range(N+1)]
visited = [-1] * (N+1)

for _ in range(M):
    u,v = map(int,input().split())
    s[u].append(v)

def dfs(n,v):

    if n > K:
        return

    for i in s[v]:
        if visited[i] != 0:
            visited[i] = min(visited[i], n)
        else:
            visited[i] = n
        dfs(n+1,i)

def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v] = 0

    while queue:
        x = queue.popleft()

        for i in s[x]:
            if visited[i] < 0:
                visited[i] = visited[x] + 1
                queue.append(i)
#dfs(1,X)
bfs(X)
chk = False
for i in range(1,N+1):
    if visited[i] == K:
        print(i)
        chk = True

if not chk:
    print(-1)

 

회고.

dfs로도 풀 수 있을 것이라 생각했으나 역시 시간이 부족했다. dfs는 깊이를 통한 방문값 갱신을 시도했고, K가 넘어갈 시에 return하도록 가지치기도 해주었지만 55%에서 시간초과가 났다.

 

또한, bfs로 풀려고 할때, visited 배열을 0부터 시작하는 과정 때문에 조건문에서

if visited[i] < 1:

 

위처럼 사용했고 이때문에 80%에서 시작점과 방문하지 않은것과의 차이가 존재하지 않아 틀렸던 것 같다