개발하는데 다 이유가 있겠지

2178. 미로탐색

• BFS(Breadth First Search, 너비 우선 탐색)으로 해결
• 시작점을 1로 두고 기존값을 더해가면서 최단 거리 계산 

import sys
from collections import deque

input = sys.stdin.readline

y, x = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(y)]
for i in range(y):
    for j in range(x):
        if graph[i][j] == 1:
            graph[i][j] = 0
        else:
            graph[i][j] = -1

visited = [[0] * x for _ in range(y)]
deq = deque()
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)


def bfs(graph):
    visited[0][0] = 1
    deq.appendleft((0, 0))
    graph[0][0] = 1

    while deq:
        a, b = deq.pop()
        for i in range(4):
            nx = b + dx[i]
            ny = a + dy[i]
            if y > ny >= 0 and x > nx >= 0:
                if graph[ny][nx] == 0 and visited[ny][nx] == 0:
                    visited[ny][nx] = 1
                    graph[ny][nx] = graph[a][b] + 1
                    deq.appendleft((ny, nx))


bfs(graph)
print(graph[y - 1][x - 1])

---

1916. 최소비용

• 다익스트라(Dijkstra) 알고리즘을 사용
• 시작점을 제외한 모든 목적지까지의 거리(비용)을 무한대로 초기화
• 비용이 최소값보다 클 때 갱신되지 않도록 조건 설정
• 우선순위 큐(heapq)로 구현

import heapq
import sys

input = sys.stdin.readline

n = int(input())
m = int(input())
# 도시 생성
cities = [[] for _ in range(n)]
INF = float("inf")
for i in range(m):
    a, b, c = map(int, input().split())
    # (비용, 목적지)형태로 저장
    cities[a-1].append((c, b-1))
d, e = map(int, input().split())
dist = [INF for _ in range(n)]
visited = [False for _ in range(n)]
dist[d-1] = 0
pq = []
# 시작점 지정
heapq.heappush(pq, (0, d-1))  # 거리가 아닌 비용을 기준으로 힙에 추가
while pq:
    cur_dist, cur_destination = heapq.heappop(pq)
    if visited[cur_destination]:
        continue
    visited[cur_destination] = True
    # 도착지에 도달하면 종료
    if cur_destination == e - 1:
        break
    for next_dist, next_city in cities[cur_destination]:
        if dist[next_city] > cur_dist + next_dist:
            dist[next_city] = cur_dist + next_dist
            heapq.heappush(pq, (dist[next_city], next_city))

print(dist[e-1])

---

18352. 특정 거리의 도시 찾기

• 다익스트라(Dijkstra) 알고리즘을 사용
• 시작점을 제외한 모든 목적지까지의 거리(비용)을 무한대로 초기화
• 비용이 최소값보다 클 때 갱신되지 않도록 조건 설정
• 비용이 모두 1이기 때문에 우선순위 큐에는 목적지만 설정

import heapq
import sys

input = sys.stdin.readline

n, m, k, x = map(int, input().split())
arr = [[] for _ in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    # 비용과 목적지
    arr[a].append(b)
INF = float("inf")
dist = [INF for _ in range(n + 1)]
dist[x] = 0
pq = []


def dijkstra(start):
    heapq.heappush(pq, (dist[start], start))

    while pq:
        cur_cost, cur_destination = heapq.heappop(pq)
        if dist[cur_destination] < cur_cost:
            continue
        for next in arr[cur_destination]:
            if dist[next] > cur_cost + 1:
                dist[next] = cur_cost + +1
                heapq.heappush(pq, (dist[next], next))


dijkstra(x)
for i in range(len(dist)):
    if dist[i] == k:
        print(i, end="\n")

if k not in dist:
    print(-1)