어제 있었던 일이다. 기록을 위해 남겨놓는다.
어제 배운 개념은 플로이드-워셜이었고 그 날의 심화과제는 3개였는데 그 중에 유달리 눈길을 끄는 문제가 있었다.
녹색 옷을 입은 애가 젤다지? 라는 문제였다!
로미섬과 코르그의 숲을 돌파하고 신수 4마리를 구출해낸 사람으로써 꼭 풀어야 하는 문제였다... 2시간을 들여 개념을 간신히 이해했는데...! 나는 문제를 풀어보고 시작했어야 했다.
문제
젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!
젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.
하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.
링크가 잃을 수밖에 없는 최소 금액은 얼마일까?
풀이!
내가 좋아하는 2d 맵에서 캐릭터 움직이기 문제였다!
노트에다가 방향키코드 복붙이라고 적고
도착해야 할 지점을 그리고
입력 출력값을 보는데 사각형 맵이 어디서 많이 본 맵이었다.
어제 다익스트라 배우면서 푼 화성탐사 문제와 비슷하네 라고 생각하며 파일에 들어가서 화성탐사를 복붙해놓고 풀어볼까... 했는데 어디서 많이 본 수열이었다!
이코테 책 389페이지의 입력예시에 써 있는 것과 완전 똑같은 입력값이었다!
아니 출력도 똑같잖아! 문제 너무 대충이다!
이건 어제 튜터님과 함께 푼
이코테 화성탐사 코드
import sys
import heapq
INFi = int(1e9)
def mars(graph):
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
N = len(graph)
dist = [[INFi] * N for _ in range(N)]
q = []
dist[0][0] = graph[0][0]
heapq.heappush(q, (graph[0][0], 0, 0))
# 누적비용, row, col
while q:
acc, r, c = heapq.heappop(q)
if dist[r][c] < acc:
continue
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < N and 0 <= nc < N:
cost = dist[r][c] + graph[nr][nc]
if cost < dist[nr][nc]:
dist[nr][nc] = cost
heapq.heappush(q, (cost, nr, nc))
return dist[N - 1][N - 1]
with open('testcase_mars.txt') as f:
sys.stdin = f
data = sys.stdin.readline
T = int(data())
for _ in range(T):
N = int(data())
graph = [list(map(int, data().split())) for _ in range(N)]
print(mars(graph))사이트에 안올라와 있었기 때문에, 테스트케이스 하나만 인풋해서 풀어야 했던 문제라 특히 기억에 남았었는데! 오늘의 젤다를 망쳐버릴 줄이야... 허탈해졌다...
기운이 빠져서 대충 인풋테이블만 cave로 바꿔주고 블로그에서 출력필터만 찾아 붙여넣어서 제출했다ㅠㅠ
백준 젤다 코드
젤다는 화성으로 떠났습니다.
import heapq
import sys
INFi = int(1e9)
data = sys.stdin.readline
def zelda():
dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]
N = int(data())
if N == 0:
return -1
cave = [list(map(int, data().split())) for _ in range(N)]
dist = [[INFi] * N for _ in range(N)]
q = []
dist[0][0] = cave[0][0]
heapq.heappush(q, (cave[0][0], 0, 0))
# 누적비용, row, col
while q:
acc, r, c = heapq.heappop(q)
if dist[r][c] < acc:
continue
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if 0 <= nr < N and 0 <= nc < N:
cost = dist[r][c] + cave[nr][nc]
if cost < dist[nr][nc]:
dist[nr][nc] = cost
heapq.heappush(q, (cost, nr, nc))
return dist[N - 1][N - 1]
i = 1 # 출력필터
while True:
answer = zelda()
if answer == -1:
break
else:
print("Problem {}: {}".format(i, answer))
i += 1
배운 점
그래서 어제는 허무하게 지나갔지만 오늘 마지막 알고리즘 강의를 들으면서 이걸 정리해둬야겠다고 생각했다. 모든 문제가 이것처럼 이름만 바꾼건 아니겠지만 문제의 유형과 구조를 파악하고 비교하는 습관을 들여야겠다는거!
튜터님의 말씀처럼 개념을 기억해뒀다가 나중에 키워드 위주로 공부하면 된다! 정리해둘거만 잘 정리해두고 세 달 뒤에 보자 알고리즘!
