코딩: 말하기 듣기 쓰기-7

이 문제드을 풀기에 앞서, 나는 중요한 주제를 배웠다. 바로 최단경로에 대한 문제였다. 최단경로를 풀기위해서는 노드, 엣지, 그리고 거리를 이용하여 어떻게 목표하는 경로를 최단으로 갈 수 있을까를 고민하여야한다. 그러기 위해서 여러가지 알고리즘이 있지만, 다익스트라 와 플로이드-워셜 알고리즘에 대해 배웠다.
다익스트라: 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘.
플로이드-워셜: 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
이 두문제는 각각 이 방식으로 풀었다.

화성탐사

By 이것이 코딩테스트다, 나동빈, 39번문제, 388쪽.
화성 탐사 기계가 존재하는 공간은 N x N 2차원 공간이며 각각의 칸을 지나기 위한 비용이 존재한다. 가장 왼쪽 칸에서 가장 오른쪽 아래 칸인 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다.

문제보자마자 드는 생각은...최단경로를 찾아줘야 하는 것을 깨달았다. 그리고 2번째로, 2차원 배열을 써야한다는 생각 입력. 지나기 위한 비용은 거리라는것을 깨달아버렸고. 이건 무조건 다익스트라를 써야한다. 맞나요? 우선 이렇게 생각하고 접근했다. 그리고, 상하좌우로 왔다갔다 할 수 있다는 것을 생각해보면, 네비게이션모드를 사용해야한다. 상하좌우 한칸씩 검사하는 것을 나는 이렇게 부른다. 아무튼 이렇게 접근을 하고 풀었다. 다익스트라 구현포맷 소환해서 풀었다.

'''
input:
3
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
output: 20 19 36
'''

import heapq
import sys
input = sys.stdin.readline

INF = int(1e9)

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


for T in range(int(input())):
    N = int(input())
    graph = []
    for i in range(N):
        graph.append(list(map(int, input().split())))
    distance = [[INF] * N for _ in range(N)]

    x, y = 0, 0
    q = [(graph[x][y], x, y)]
    distance[x][y] = graph[x][y]


    while q:
        dist, x, y = heapq.heappop(q)
        if distance[x][y] < dist:
            continue
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            cost = dist + graph[nx][ny]
            if cost < distance[nx][ny]:
                distance[nx][ny] = cost
                heapq.heappush(q, (cost, nx, ny))
    print(distance[N-1][N-1])

힙을 쓰는 이유는 최저거리를 위해서이다. 힙은 구조상 부모노드가 자식노드보다 작아야한다. 그렇기때문에, 최저인 것이 제일 앞으로 오고, pop을 하게된다면 제일먼저 나온다. 그렇기때문에 힙을 통해서 최단경로를 찾기 좋은 것이다. 그리고, 항상 기존에 있던 경로와 새로 가본 경로중, 값을 잘 비교해서 최단경로를 저장해주어야한다.

운동

https://www.acmicpc.net/problem/1956
백준 1956번, 운동 문제
V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.
당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시오. 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다.

문제를 보자마자, 모든 지점에 대해서 각각 최단경로가 어떻게 되는지 계산해봐야한다. 즉, 플로이드-워셜 알고리즘을 사용하여야한다. 그리고, 사이클임을 주의하여야한다. 사이클이라는 것은 갔다가 다시 돌아온다는 뜻이다. 즉 각 노드간의 방향이 갔다가 오는 것을 찾고, 그것의 거리에 대한 합을 찾아야 한다는 것이다. 나는 이 문제를 풀때 사이클을 생략하고 풀어서 이상하게 풀게되었다. 플로이드-워셜 접근은 맞았으나...아쉬웠다.

import sys

input = sys.stdin.readline

V, E = map(int, sys.stdin.readline().split())
INF = int(1e9)
graph = [[INF] * (V + 1) for _ in range(V + 1)]
# print(graph)
for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = c
# print(graph)

for k in range(1, V + 1):
    for i in range(1, V + 1):
        for j in range(1, V + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

answer = INF
for i in range(1, V + 1):
    answer = min(answer, graph[i][i]) #사이클이니까 i로한다
if answer == INF:
    print(-1)
else:
    print(answer)

3중 for문을 써야한다....시간복잡도가 무려...어마어마하다. 아무튼 그러고난후 마지막 answer부분을 처리하는것에서 미숙하여, 해결하지 못했다. 사이클이니까 갔다가 다시 오는 방향으로 코드를 짜려면 graph[i][i]로 설정해 주어야 하지만, 그것을 생각하지 못했다.