1. boj.kr/18352 - 특정 거리의 도시 찾기

Untitled

BFS 풀이

# boj.kr/18352
import sys
from collections import deque

N, M, K, X = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
distance = [0] * (N+1)
visited = [False] * (N+1)
answer = []

for _ in range(M):
    s, d = map(int, sys.stdin.readline().split())
    graph[s].append(d)

def bfs(graph, start, visited):
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True
    # 큐가 빌 때까지 반복
    while queue:
        v = queue.popleft()
        if distance[v] == K:
            answer.append(v)

        # 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                distance[i] = distance[v] + 1

bfs(graph, X, visited)
print('\\n'.join(map(str, sorted(answer))) if answer else -1)

다익스트라 풀이

# boj.kr/18352
import sys
import heapq

N, M, K, X = map(int, sys.stdin.readline().split())
graph = {i: [] for i in range(1, N+1)}
answer = []

for _ in range(M):
    s, d = map(int, sys.stdin.readline().split())
    graph[s].append((d, 1))

def dijkstra(graph, start):
    heap = [(0, start)]
    visited = set()
    while heap:
        (cost, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        if cost == K: # K만큼 이동했을 때 추가
            answer.append(u)
        for v, c in graph[u]:
            if v in visited:
                continue
            next_item = cost + c
            heapq.heappush(heap, (next_item, v))

dijkstra(graph, X)
print('\\n'.join(map(str, sorted(answer))) if answer else -1)

2. boj.kr/14463 - 지름길

Untitled

다익스트라 풀이

# boj.kr/1446
import sys
import heapq

N, D = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(D+1)]
for i in range(D+1):
    graph[i].append((i+1, 1)) # 한칸 이동, 이동비용 1

for _ in range(N):
    start, end, cost = list(map(int, sys.stdin.readline().split()))
    if end <= D:
        graph[start].append((end, cost))

def dijkstra(graph, start, end):
    heap = [(0, start)]
    visited = set()
    while heap:
        (cost, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        if u == end:
            return cost
        for v, c in graph[u]:
            if v in visited:
                continue
            next_item = cost + c
            heapq.heappush(heap, (next_item, v))

print(dijkstra(graph, 0, D))

3. network-delay-time

Untitled

설명

예시