백준 22255번 호석사우루스

1. 문제 설명

문제 링크

호석사우루스는 융통성 없이 정해진 규칙을 활용해 움직인다.
규칙은 아래와 같다.

1. 3K번째는 상, 하, 좌, 우 중 한 곳으로 이동한다.
2. 3K+1번째는 상, 하 중 한 곳으로 이동한다
3. 3K+2번째는 좌, 우 중 한 곳으로 이동한다.
4. 이동하려는 곳에 벽이 있으면 이동할 수 없다.
5. 첫번째로 이동하는 것은 1(3K+1)번째 이동이다

이 때 미궁의 각 칸마다 충격량이 주어질 것이며, 호석사우르스는 해당 칸에 들어가게 되면 충격량을 받게 된다.
호석사우르스가 받는 충격량의 총량을 최소한으로 하는 방법을 찾아 최소 충격량을 구하는 문제이다.

2. 코드

import sys
from heapq import heappush, heappop

INF = sys.maxsize
input = sys.stdin.readline

class Solution():
    def __init__(self):
        self.N = list(map(int, input().split()))
        self.position = list(map(int, input().split()))
        self.queue = []
        self.maps = [list(map(int, input().split())) for _ in range(self.N[0])]
        self.dis = [[[INF] * 3 for _ in range(self.N[1])] for _ in range(self.N[0])]
        self.dx = [1, -1, 0, 0]
        self.dy = [0, 0, -1, 1]

    def cal(self, nx, ny, dist, c):
        if 0 <= nx < self.N[0] and 0 <= ny < self.N[1] and not self.maps[nx][ny] == -1:
            cost = dist + self.maps[nx][ny]

            if cost < self.dis[nx][ny][(c + 1) % 3]:
                self.dis[nx][ny][(c + 1) % 3] = cost
                heappush(self.queue, (cost, c + 1, nx, ny))

    def dijstra(self):
        heappush(self.queue, (0, 1, self.position[0] - 1, self.position[1] - 1))
        self.dis[self.position[0] - 1][self.position[1] - 1][1] = 0

        while self.queue:
            dist, c, x, y = heappop(self.queue)

            if x == (self.position[2] - 1) and y == (self.position[3] - 1):
                return dist

            if not c % 3:
                for i in range(4):
                    nx = x + self.dx[i]
                    ny = y + self.dy[i]

                    self.cal(nx, ny, dist, c)

            elif c % 3 == 1:
                for i in range(2):
                    nx = x + self.dx[i]
                    ny = y + self.dy[i]

                    self.cal(nx, ny, dist, c)
            else:
                for i in range(2, 4):
                    nx = x + self.dx[i]
                    ny = y + self.dy[i]

                    self.cal(nx, ny, dist, c)
        return -1

answer = Solution()
print(answer.dijstra())

 

3. 회고

Q. 문제를 보고 든 생각

• 일반적인 다익스트라 + BFS 문제였다면 최소비용을 계산하는 배열은 2중 배열이면 되었을 것이다.
• 하지만 이 문제는 이동 경우의수를 3가지로 나누었기 때문에 3중 배열로 풀어내야한다.
• 이동할 시점에서 다음의 이동 경우의수를 고려하며 이동해야 한다. (문제의 핵심!!)

4. 고쳐야 할점

파이썬 클래스로 풀어본것은 처음이라 많이 미흡한점이 많습니다.. 이해부탁드립니다.