반응형
알고리즘 분류 : 다익스트라
빨간색(0), 분홍색(1), 주황색(2), 파란색(3), 보라색(4) 등 총 5가지 색의 타일이 있는 미로를 이동하면서 탈출해야 한다. 이미 방문했던 타일을 다시 방문할 수 있으므로, 일반적인 BFS로 최단 거리를 구하기는 까다롭다. 구현할 때, 보라색(4) 타일을 유의해야 한다.
- 빨간색(0) 타일로는 이동할 수 없다. 다음 이동에서 0번 타일을 보면 무시한다.
- 분홍색(1) 타일로는 이동할 수 있다. 평범한 이동을 하면 된다.
- 주황색(2) 타일로는 이동할 수 있으며, 이 타일을 밟으면 오렌지 냄새를 풍긴다. 냄새 상태를 True로 만든다.
- 파란색(3) 타일로는 냄새 상태가 True일 때에만 이동할 수 있다. 냄새 상태가 False라면 이동할 수 없다.
- 보라색(4) 타일에서는 보라색 타일로 왔던 방향으로 미끄러진다. 냄새 상태가 False가 된다.
- 미끄러질 때, 다음 타일이 보라색(4)이라면 계속 미끄러지며, 보라색이 아닌 다른 타일을 만나면 그 타일에서 멈춘다.
- 미끄러질 때, 다음 타일이 빨간색(0)이거나 파란색(3)이라면, 앞으로 나가지 못하고 그 자리에서 멈춘다.
- 방문 여부를 확인할 배열을 3차원으로 선언하고, 각 인덱스를 (X좌표, Y좌표, 냄새 상태)로 이용한다.
- (1, 1)부터 출발하여 (N, M)에 도착하면 이동 거리를 출력하고, 도착하지 못하면 -1을 출력한다.
C++ 소스코드
include <cstdio> #include <queue> using namespace std; struct maze { // d is distance, s is smell status. int x, y, s, d; bool operator < (const maze t) const { return d > t.d; } }; int n, m, ans; int a[1002][1002]; int dist[1002][1002][2]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; const int INF = 1e9; bool possible(int x, int y, int s) { if (x < 0 || x >= n || y < 0 || y >= m) return false; if (a[x][y] == 0) return false; if (a[x][y] == 3) return s == 1; return true; } void dijkstra() { priority_queue<maze> pq; pq.push({0, 0, 0, 0}); dist[0][0][0] = 0; while (!pq.empty()) { int x = pq.top().x, y = pq.top().y, s = pq.top().s, d = pq.top().d; pq.pop(); if (x == n-1 && y == m-1) { printf("%d\n", d); return; } for (int i=0; i<4; i++) { int nx = x+dx[i], ny = y+dy[i]; int ns = s, nd = d+1; if (!possible(nx, ny, ns)) continue; if (a[nx][ny] == 4) { while (possible(nx+dx[i], ny+dy[i], ns) && a[nx][ny] == 4) { nx += dx[i]; // Sliding ny += dy[i]; nd += 1; ns = 0; // Smell off } } if (a[nx][ny] == 2) ns = 1; // Smell on if (dist[nx][ny][ns] > nd) { dist[nx][ny][ns] = nd; pq.push({nx, ny, ns, nd}); } } } printf("-1\n"); } int main() { scanf("%d %d", &n, &m); for (int i=0; i<n; i++) { for (int j=0; j<m; j++) { scanf("%d", &a[i][j]); dist[i][j][0] = dist[i][j][1] = INF; } } dijkstra(); return 0; }
Python 3 소스코드
from sys import stdin from heapq import heappush, heappop input = stdin.readline INF = 1e9 n, m = map(int, input().split()) a = [list(map(int, input().split())) for _ in range(n)] dist = [[[INF]*2 for _ in range(m)] for _ in range(n)] dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1) def possible(x, y, s): if x < 0 or x >= n or y < 0 or y >= m: return False if a[x][y] == 0: return False elif a[x][y] == 3: return s == 1 else: return True def dijkstra(): pq = [] heappush(pq, (0, 0, 0, 0)) dist[0][0][0] = 0 while pq: d, x, y, s = heappop(pq) if x == n - 1 and y == m - 1: print(d) return for i in range(4): nx, ny = x+dx[i], y+dy[i] nd, ns = d+1, s if possible(nx, ny, ns) is False: continue if a[nx][ny] == 4: while possible(nx+dx[i], ny+dy[i], ns) and a[nx][ny] == 4: nx += dx[i] ny += dy[i] nd += 1 ns = 0 if a[nx][ny] == 2: ns = 1 if dist[nx][ny][ns] > nd: dist[nx][ny][ns] = nd heappush(pq, (nd, nx, ny, ns)) print(-1) dijkstra()
참고
반응형