본문 바로가기

Programming/BOJ

BOJ 11965 · Bessie's Dream


알고리즘 분류 : 다익스트라  


빨간색(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()




참고



태그