백준 - 18352번(다익스트라, BFS)

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

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

import sys
from collections import deque

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

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

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

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

def bfs(s):
    ans = []
    q = deque([[s,0]])
    check[s] = True
    while q:
        n, dist = q.popleft()
        for i in arr[n]:
            if check[i] == False:
                check[i] = True
                if dist+1 < k:
                    q.append([i,dist+1])
                elif dist+1 == k:
                    ans.append(i)

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

bfs(x)

실버 난이도의 다익스트라 문제이지만 생각을 깊게 하지 않으면 메모리초과와 시간초과로 고생한다.

첫번째로 최단거리가 k와 동일한 원소들을 출력해주면 된다.

해당 문제에서 간선들의 특징은 단방향, 가중치가 1씩만 증가 한다는 것이다.

즉 단방향으로 연결된 간선이 있는데 현재 좌표가 이전 좌표보다 가중치가 1큰것이다.

따라서 따로 가중치를 저장하는 배열을 만들지 않아도 된다.

단방향 간선이기에 arr[a].append(b) 이런식으로 배열을 만들어 준다.

bfs를 실행할때 각 좌표와 해당 좌표의 가중치 값을 같이 비교하면 된다.

가중치가 1씩 증가한다는 의미는 최초방문 즉 check[i]==False일때가 최초방문이고 무조건 최단 거리라는 뜻이다.

check 배열을 통해서 방문처리를 한다. 첫방문에 dist의 값이 k와 같으면 조건에 맞는 정답이 된다. 이를 출력해주면 끝.

 

처음에는 각 좌표마다 가중치를 배열에 저장하려 했지만 주어진 n과 m의 범위가 워낙 커서 이렇게하면 메모리초과가 난다. 주의하자.