이코테 - 화성탐사

문제 출처

이것이 취업을 위한 코딩 테스트다 - p.388 화성탐사

---

문제설명/풀이

- 문제

당신은 화성 탐사 기계를 개발하는 프로그래머다. 그런데 화성은 에너지 공급원을 찾기가 힘들다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다.

화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재한다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하라. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

 

a. 입력 조건

• 첫째 줄에 테스트 케이스의 수 T(1 <= T <= 10)가 주어진다.
• 매 테스트 케이스의 첫째 줄에는 탐사 공간의 크기를 의미하는 정수 N이 주어진다.
  • 2 <= N <= 125
• 이어서 N개의 줄에 걸쳐 각 칸의 비용이 주어지며 공백으로 구분한다.
  • 0 <= 각 칸의 비용 <= 9

c. 출력 조건

• 각 테스트 케이스마다 [0][0]의 위치에서 [N - 1][N - 1]의 위치로 이동하는 최소 비용을 한 줄에 하나씩 출력한다

d. test case

입력:

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

출력:

20
19
36

 

우선은 가중그래프의 최단거리문제 + 여러개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 경우이므로 일반적으로 다익스트라 방법을 사용하여야 한다. 하지만, 내가 알고 있던 다익스트라는 일반적으로 n*n map( 2차원배열)입력이 아니라, (노드, 노드, 비용)의 입력을 받았기 때문에, bfs 같은 느낌으로도 풀 수 있지 않을까 하는 생각이 들었다.

 

bfs의 정의:

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

 

내가 생각한 알고리즘의 핵심은 비용값의 갱신과 갱신된 노드의 queue 추가이다.

 

1. 다음 노드가 한번도 방문하지 않았다면,

이전 노드까지의 비용 누적합 + 이전 노드에서 다음 노드로 가는 비용이 다음 노드값의 비용 누적합이고,

다음 노드를 queue에 추가해준다

 

2. 다음 노드가 방문된 적이 있다면,

다음 노드까지의 누적합과 이전 노드까지의 비용 누적합 + 이전 노드에서 다음 노드로 가는 비용을 비교하여,

새로운 경로의 누적합이 작은 경우 다음노드의 누적합을 갱신해주고,

다음 노드를 queue에 추가해준다

 

다음과 같은 지도가 있다고 하자

map:

1	4
5	7

1-5-7 경로를 따라 간 경우의 누적합:

1	4는 방문 x
6	13

* 비용이 7인 노드에 처음 방문했으므로 비교 없이 누적합을 넣어준다

 

1-5-7 경로를 따라 간 경우를 누적합으로 갱신한 후(비용이 7인 노드가 1번 이상 방문된 후)

1-4-7 경로를 따라 간 경우의 누적합

1	5
5는 방문 x	12

*비용이 7인 노드가 1번 이상 방문되었으므로, 원래의 누적합인 13과 새로운 경로를 통해 생긴 누적합인 12를 비교하여 

더 작은 값으로 갱신한다

 

코드:

import sys
from collections import deque



test = int(input()) # 테스트 케이스의 수
start_time = datetime.datetime.now()  # 시작 시간 저장
for i in range(test):
    m = int(input()) # 맵의 한 변의 길이

    mars_map = [[0 for i in range(m)]for i in range(m)] # 원본 비용 배열
    mars_accumulate_map = [[0 for i in range(m)]for i in range(m)] # 누적 비용 배열
    mars_visit_map = [[0 for i in range(m)]for i in range(m)] # 첫 방문 배열(처음으로 방문된 배열인지 아닌지 기록)

    # 이동 비용 값 넣어주기
    for i in range(m):
        tmp = list(map(int,sys.stdin.readline().split()))
        mars_map[i] = [x for x in tmp]




    # 초기설정
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]

    start = (0,0) # 시작노드
    mars_visit_map[0][0] = 1 # 시작노드는 첫 방문처리
    mars_accumulate_map[0][0] = mars_map[0][0] # 시작 노드 비용 갱신


    q = deque()
    q.append(start)

    while(q):
        x,y = q.popleft() # 현재 좌표
        now = mars_accumulate_map[y][x]# 현재 노드까지 도닫하는데 걸린 최소비용

        for i in range(4):
            # 이동 좌표들
            nx = x + dx[i]
            ny = y + dy[i]

            # 맵 안에 잇는 좌표인지 확인
            if(0<=nx<m and 0<=ny<m):
                # 첫 방문일 경우
                if(mars_visit_map[ny][nx] == 0):
                    # 이동해서 온 경로가 유일하므로, 여기까지 도닫하는데 걸리 노드비용 무조건 계산
                    mars_accumulate_map[ny][nx] = mars_map[ny][nx] + now
                    mars_visit_map[ny][nx] = 1 # 현재 노드 첫 방문처리
                    q.append((nx,ny))
                else:
                    # 이동해서 온 경로가 유일하지 않으므로 어떤 경로가 최소 값인지 계산
                    old = mars_accumulate_map[ny][nx] # 이전 경로로의 비용값
                    new = mars_map[ny][nx] + now  # 새로운 경로로의 비용값
                    if( old > new ):
                        mars_accumulate_map[ny][nx] = new
                        q.append((nx,ny))

    print(mars_accumulate_map[m-1][m-1])

테스트 케이스가 적어서 완벽한 정답인지는 모르겠지만, 테스트 케이스는 통과한다.

* bfs 아이디어를 차용하긴 했지만, 방문한 노드를 다시한번 방문할 수 있다는 점에서 완벽히 bfs의 정의에 맞는지는 모르겠다

 

---

다익스트라 알고리즘

 

-간단한 다익스트라 알고리즘:

현재 노드에서 연결된 처리되지 않은 노드들을 모두 찾아 가중치를 갱신한다 O(V)->

처리되지 않은 노드들 중 거리 비용이 가장 짧은 노드를 선택해 다음 노드로 처리한다O(V)

O(V^2)

*처리된 노드: 노드에 연결된 간선을 모두 체크하여 최소 거리 비용이 보장되는 노드

 

-갱신된 다익스트라 알고리즘

현재 노드에서 연결된 처리되지 않은 노드들을 모두 찾아 가중치를 갱신한다 O(v)->

가중치가 갱신된 경우( 다음 노드의 후보가 된다 )

힙 자료구조를 통해 비용이 가장 짧은 노드를 선택하여 다음 노드로 처리한다O(logV)

O(VlogV)

*힙 자료구조의 특성상 비용 갱신이 안되면 처리된 노드라고 생각할 수 있다. == 방문배열이 필요없다

 

갱신된 다익스트라 vanilla 코드:

import collections
import heapq
INF = int(1e9)

n,m = map(int, input().split()) # n: 노드의 개수, m: 간선의 개수
start = int(input())
graph = collections.defaultdict(list) # 노드의 연결 정보 (현재노드: (다음노드 , 비용))
dist = [INF] * (n+1)

for _ in range(m):
	a,b,c = map(int, input.split())
    graph[a].append((b,c))

Q = []
heapq.heappush(Q,(0,start)) # heap 초기 설정
while Q:
    cost,now = heapq.heappop(Q) # 비용에 대한 최소힙

    # 갱신이 안된 경우 -> 처리된 배열이다라고 생각
    if dist[now] < cost:
        continue

    for i in graph[now]:
        cost = cost + i[1] # 새로운 비용
        # 새로운 비용이 현 비용보다 작다면
        if cost <dist[i[0]]:
            dist[i[0]] = cost # 비용 갱신
            heapq.heappush(Q,(cost, i[0])) #힙에 추가가 된다

갱신된 다익스트라 dist 사용, 처리된 배열만 가져오는 코드:

import collections
import heapq

n, m = map(int, input().split())
start = int(input())
graph = collections.defaultdict(list)
dist = collections.defaultdict(int)
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))

Q = []
heapq.heappush(Q, (0, start))
while Q:
    time, node = heapq.heappop(Q)
    # 처리되지 않은 배열은 힙에서 정렬될 뿐 비용 갱신 x
    if node not in dist:
        dist[node] = time # 처리된 배열만 dist에 넣는다
        for v, w in graph[node]:  #갈 수 있는 경로를 다 찾아보기
            alt = time + w   # 다음 node에 해당하는 time을 update
            heapq.heappush(Q, (alt, v)). # Q에 (updated time, 다음 node)
print(dist)

=>  if node not in dist: 이 코드 때문에

if cost <dist[i[0]]: 조건을 사용하는 vanilla 다익스트라에 비해 heap에 추가되는 (비용, 노드)가 많아진다

대신 처리된 노드 외에는 비용 갱신을 하지 않는다.

---

다익스트라로 풀기

# 배열에 최소비용을 계속 갱신하야 heap에 넣을지 비교하는 다익스트라
import heapq

for t in range(int(input())):
    # 탐사 공간
    n = int(input())
    # 탐사 공간에 대한 비용
    graph = []

    for i in range(n):
        graph.append(list(map(int, input().split())))
    # 다익스트라를 위한 q
    q = []
    heapq.heappush(q, (graph[0][0], 0, 0))
    # 상하좌우 탐색을 위한 ds
    ds = ((0, 1), (0, -1), (1, 0), (-1, 0))

    distance = [[1e9] * n for _ in range(n)]
    distance[0][0] = graph[0][0]

    while q:
        dist, x, y = heapq.heappop(q)

        if distance[x][y] < dist:
            continue

        for d in ds:
            dx = x + d[0]
            dy = y + d[1]

            if 0 <= dx and dx < n and 0 <= dy and dy < n:
                cost = dist + graph[dx][dy]

                if cost < distance[dx][dy]:
                    distance[dx][dy] = cost
                    heapq.heappush(q, (cost, dx, dy))

    print(distance[n-1][n-1])

# 힙에 다 넣는 다익스트라
import heapq
import collections

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

for tc in range(int(input())):
    n = int(input())
		# graph에는 각각의 칸을 지나기 위한 비용을 넣어줌 {(x, y): cost}
    graph = collections.defaultdict(int) 
		# dist는 (0, 0)에서 특정좌표까지 도달할 때의 cost를 넣어줌 {(x, y): cost}
    dist = collections.defaultdict(int)
    for i in range(n):
        lst = list(map(int, input().split()))
        for j in range(n):
            graph[(i, j)] = lst[j]
    q = [(graph[(0, 0)], 0, 0)] # cost, x좌표, y좌표
    while q:
        cost, x, y = heapq.heappop(q)
        if (x, y) not in dist:
            dist[(x, y)] = cost
            for i in range(4):  # 갈 수 있는 경로를 다 찾아보기
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < n: # 다음 노드가 가능한 노드인지 확인
                    tmp = graph[(nx, ny)] + cost   # 다음 노드에 해당하는 cost를 update
                    heapq.heappush(q, (tmp, nx, ny)) # q에 (updated cost, x좌표, y좌표)
    print(dist[(n - 1, n - 1)])

---

성능

100*100짜리 map으로 성능테스트한 결과:

bfs 개념 문제풀이 코드: 0.140337 sec,

최소비용 갱신/비교 다익스트라: 0.046576sec, 

힙에 모두 넣는 다익스트라: 0.077854sec

 

힙에서 최소비용 노드를 뺄때마다 최소비용 배열을 갱신하여 힙에 넣는 노드를 줄이는 것이 더 효율적이다.