BOJ 1445 · 일요일 아침의 데이트

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

S부터 출발해서 F에 도착할 때까지, 쓰레기를 최소로 지나면서, 쓰레기의 옆을 최소로 지나는 방법을 찾는 문제다. 두 가지의 우선순위 조건 때문에, 다익스트라 알고리즘을 사용하는 것이 좋다. 

• 다익스트라를 이용하기 위해, 입력으로 주어지는 문자열 맵에 상응하는 인접 행렬을 만든다.
• 쓰레기가 있는 칸 'g'는 2500으로 두고, g에 인접한 4칸은 1로 둔다. 나머지 칸은 0으로 둔다.
• 맵이 최대 50*50으로 주어지기 때문에, 쓰레기 칸('g')에 넉넉하게 큰 값을 주는 것이 좋다. 예를 들어, 쓰레기 칸에 3을 주면 쓰레기 옆 칸을 3번 이동한 것과 구분할 수 없기 때문이다.
• 정답은 dist 배열에 있으며, 2500으로 나눈 몫이 쓰레기를 지난 횟수이며, 2500으로 나눈 나머지가 쓰레기 옆을 지난 횟수이다.

---

C++ 소스코드

#include <cstdio>
#include <queue>
using namespace std;

struct forest {
    int d, x, y;
    bool operator < (const forest t) const { return d > t.d; }
};

int n, m;
int a[50][50];
char b[50][50];
int dist[50][50];
priority_queue<forest> q;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int G = 2500;

bool out(int x, int y) {
    return x < 0 || x >= n || y < 0 || y >= m;
}

void dijkstra() {
    while (!q.empty()) {
        int d = q.top().d, x = q.top().x, y = q.top().y; q.pop();
        if (b[x][y] == 'F') {
            printf("%d %d\n", dist[x][y]/G, dist[x][y]%G);
            return;
        }
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (out(nx, ny)) continue;
            int nd = d+a[nx][ny];
            if (dist[nx][ny] > nd) {
                dist[nx][ny] = nd;
                q.push({nd, nx, ny});
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i=0; i<n; i++) scanf("%s", b[i]);
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            dist[i][j] = 1e9;
            if (b[i][j] == 'S') {
                q.push({0, i, j});
                dist[i][j] = 0;
            } else if (b[i][j] == 'g') {
                a[i][j] = G;
                for (int k=0; k<4; k++) {
                    int ni = i+dx[k], nj = j+dy[k];
                    if (!out(ni, nj) && b[ni][nj] == '.') a[ni][nj] = 1;
                }
            }
        }
    }
    dijkstra();
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from heapq import heappush, heappop
input = stdin.readline

n, m = map(int, input().split())
b = [list(input().strip()) for _ in range(n)]
a = [[0]*m for _ in range(n)]
dist = [[1e9]*m for _ in range(n)]
dx, dy, G = (-1, 0, 1, 0), (0, 1, 0, -1), 2500
q = []

def out(x, y):
    return x < 0 or x >= n or y < 0 or y >= m

def dijkstra():
    while q:
        d, x, y = heappop(q)
        if b[x][y] == 'F':
            print(dist[x][y]//G, dist[x][y]%G)
            return
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if out(nx, ny):
                continue
            nd = d+a[nx][ny]
            if dist[nx][ny] > nd:
                dist[nx][ny] = nd
                heappush(q, (nd, nx, ny))

for i in range(n):
    for j in range(m):
        if b[i][j] == 'S':
            heappush(q, (0, i, j))
            dist[i][j] = 0
        elif b[i][j] == 'g':
            a[i][j] = G
            for k in range(4):
                ni, nj = i+dx[k], j+dy[k]
                if not out(ni, nj) and b[ni][nj] == '.':
                    a[ni][nj] = 1
dijkstra()

---

참고

• 백준 온라인 저지 : BOJ 1445
• 위키피디아 : 데이크스트라 알고리즘
• 최단경로