백준 18352 특정 거리의 도시 찾기

백준 18352 특정 거리의 도시 찾기

자신 있게 풀었던 문제에서 메모리 초과가 나서 풀이와 비교하며 분석해 보았다.

import sys
sys.setrecursionlimit(10**6)
n, m, k, x= map(int, sys.stdin.readline().split()) 
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)

cnt = 0
visited = [0] * (n+1)

def bfs(x):
    for i in graph[x]:
        if visited[i] != 0:
            visited[i] = min(visited[x] + 1, visited[i])
        else:
            visited[i]= visited[x] + 1
        bfs(i)

bfs(x)

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

알고 보니 최단 거리는 무조건 bfs로 풀어야지! 하고 함수 이름도 bfs로 명해줬는데 풀이 방식을 dfs로 풀고 재귀 초과 조건까지 넣어줬다.. bfs 없는 bfs 함수 탄생..^^

하여 올바른 bfs로 수정해 주었다.

import sys
from collections import deque
n, m, k, x= map(int, sys.stdin.readline().split()) 
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)

def bfs(x):
    answer = []
    q = deque([x])
    visited = [0] * (n+1)

    while q:
        p = q.popleft()
        for i in graph[p]:
            if visited[i] == 0:
                visited[i]= visited[p] + 1
                q.append(i)
                if visited[i] == k and i != x:       # 순회 방지
                    answer.append(i)
    return answer

answer = bfs(x)

if answer == []:
    print(-1)
else:
    answer.sort()
    for a in answer:
        print(a)

마지막까지 순회하여 다시 시작 좌표로 돌아올 수 있다는 점을 간과하여 반례를 통해 알게 되고, 수정했더니 드디어 맞았습니다!!!

추가로, 틀린 덕분에 풀이와 비교하면서 알게 된 다익스트라 알고리즘에 대해서도 공부하게 되었다. 전부터 카카오 코테 연습문제를 통해 접하기만 하고 제대로 정리해 본 적이 없는 거 같아 마침 잘됬다 싶었다.

다익스트라 알고리즘

도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다.
원래는 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 고정하고 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다.
즉, 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다.

자, 개념은 이 정도로 하고, 이쯤에서 적용을 해봐야 개념이 더 잘 이해될 수 있을 것이다.

import heapq, sys
n, m, k, x= map(int, sys.stdin.readline().split()) 
graph = [[] for _ in range(n+1)]
distance = [int(1e9)] * (n+1)

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

def dijkstra(x):
    q = [] 						# heapq를 이용해 거리가 짧을수록 앞에 오는 큐(우선순위 큐)를 만든다.
    heapq.heappush(q, (0, x)) 	# 처음 자기 자신과의 거리는 0으로 설정
    distance[x] = 0
    while q: 					
        dist, now = heapq.heappop(q)
        if distance[now] < dist: continue	# 이미 저장된 거리 < 가야하는 곳의 거리 : skip
        for j in graph[now]:
            cost = dist + j[1] 				# 이전 거리 + 새 거리 
            if cost < distance[j[0]]:
                distance[j[0]] = cost
                heapq.heappush(q, (cost, j[0]))

dijkstra(x)
answer = []
for i in range(1, n+1):
    if distance[i] == k: 
        answer.append(i)

if len(answer) == 0: 
    print(-1)
else:
    for i in answer: 
        print(i)

해당 문제에서는 확실히 bfs 풀이에 비해 메모리와 시간을 좀 더 잡아먹었지만, 모든 거리의 길이가 1로 고정되지 않은 경우에 사용하면 보다 쓰임새 있을 것이다.

참고.
wiki 데이크스트라 알고리즘

동빈나 다익스트라(Dijkstra) 알고리즘