240410 [BOJ/백준] 18352. 특정 거리의 도시 찾기

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

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

---

나의 코드

1. 조건(최소거리=k)에 맞을 때 빈 리스트에 해당 노드 추가하기

import sys
from collections import deque

n, m, k, x = map(int, sys.stdin.readline().split())
adjl = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    adjl[i].append(j)

q = deque()
q.append(x)
visited[x] = 1
ans = []
while q:
    x = q.popleft()
    if visited[x] > k+1:
        break

    for w in adjl[x]:
        if visited[w] == 0:
            visited[w] = visited[x] + 1
            q.append(w)
            if visited[w] == k+1:
                ans.append(w)

if len(ans) == 0:
    print(-1)
else:
    ans.sort()
    for k in ans:
        print(k)

 

2. 최소거리 다 구하고 한 번 다 돌면서 해당 노드 추가(sort 필요없음) 

import sys
from collections import deque

n, m, k, x = map(int, sys.stdin.readline().split())
adjl = [[] for _ in range(n+1)]
visited = [0] * (n+1)
for _ in range(m):
    i, j = map(int, sys.stdin.readline().split())
    adjl[i].append(j)

q = deque()
q.append(x)
visited[x] = 1
while q:
    x = q.popleft()
    if visited[x] > k+1:
        break

    for w in adjl[x]:
        if visited[w] == 0:
            visited[w] = visited[x] + 1
            q.append(w)

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

if len(ans) == 0:
    print(-1)
else:
    for k in ans:
        print(k)

 

결과

---

이게 이렇게 시도를 많이 해야 될 문제가 아닌데...? 제일 처음에는 DFS로 거리계산했더니 최저거리를 못구해서 BFS로 거리계산을 했다. 그래서 결과는 빨리 나왔지만 시간초과.. readline하고 내용구성을 조금씩 달리했지만 중요한 핵심인 가지치기를 안해서 계속 시간초과가 됐다. 그래서 틀린 테스트케이스까지 못갔고 가지치기를 했더니 내 코드는 틀린 코드였다. 틀린 이유는 처음 시작하는 노드는 최저거리가 0이니까 방문표시를 안해줬는데 그게 다른 곳을 돌고 오면서 꼬일 수 있겠더라...ㅜㅜ 그걸 고치고 바로 성공! 이제 방문표시는 무조건 할거다!!!

(+ 해당 조건에 맞을 때 바로 리스트에 넣고 정렬을 하는게 빠를지, 최소거리 다 구하고 앞에서부터 돌면서 최소거리에 해당하는 노드를 리스트에 넣는게 빠를지 궁금해서 넣어봤는데 조건에 맞을 때 리스트에 넣는게 빨랐다. 56ms가 유의미한 차이인지는 모른다...ㅎㅎㅎ)