BOJ 5558 · チーズ

알고리즘 분류 : BFS  

쥐가 먹을 수 있는 치즈를 순서대로 먹으면서 이동하는 최단 거리를 구하는 문제다.  

• 다음 치즈를 먹으러 이동할 때, 방문했던 곳을 다시 방문할 수 있다.
• 치즈를 낮은 숫자부터 순서대로 먹어야 하고, 현재 먹을 수 없는 높은 숫자의 치즈는 무시하고 이동할 수 있다.
• 위 두 가지를 잘 고려하여, BFS 탐색을 해야 한다. 
• 우선 BFS를 통해 먹을 수 있는 치즈를 찾고, 먹은 위치와 이동 거리를 저장한 후 BFS를 종료한다.
• 방문 여부를 확인하는 check 배열을 초기화하고, 위에서 먹은 위치부터 다음 치즈까지 BFS 탐색을 다시 시작한다.
• 즉, 시작점 → 1번 치즈, 1번 치즈 → 2번 치즈, ···, N-1번 치즈 → N번 치즈 순으로 BFS를 돌리면 된다.

---

C++ 소스코드

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

struct mouse {
    int x, y, d;
};

int h, w, n;
int mx, my, ans, hp=1;
char a[1001][1001];
bool check[1001][1001];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void bfs() {
    queue<mouse> q;
    q.push({mx, my, 0});
    check[mx][my] = true;
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y, d = q.front().d;
        q.pop();
        for (int i=0; i<4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if (check[nx][ny] || a[nx][ny] == 'X') continue;
            if ('1' <= a[nx][ny] && a[nx][ny] <= '9') {
                if (hp >= a[nx][ny]-'0') {
                    hp++;
                    a[nx][ny] = '.';
                    ans += (d+1);
                    mx = nx, my = ny;
                    return;
                }
            }
            q.push({nx, ny, d+1});
            check[nx][ny] = true;
        }
    }
}

int main() {
    scanf("%d %d %d", &h, &w, &n);
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            scanf("%1s", &a[i][j]);
            if (a[i][j] == 'S') {
                mx = i, my = j;
            }
        }
    }
    for (int i=0; i<n; i++) {
        memset(check, false, sizeof(check));
        bfs();
    }
    printf("%d\n", ans);
    return 0;
}

---

Python 3 소스코드

from sys import stdin
from collections import deque
input = stdin.readline

h, w, n = map(int, input().split())
a = [list(input().strip()) for _ in range(h)]
dx, dy = (-1, 0, 1, 0), (0, 1, 0, -1)
mx, my, ans, hp = 0, 0, 0, 1
for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            mx, my = i, j
            break

def bfs(check):
    global mx, my, ans, hp
    q = deque()
    q.append((mx, my, 0))
    check[mx][my] = True
    while q:
        x, y, d = q.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if check[nx][ny] or a[nx][ny] == 'X':
                continue
            if '1' <= a[nx][ny] <= '9':
                if hp >= int(a[nx][ny]):
                    hp += 1
                    mx, my = nx, ny
                    ans += (d+1)
                    a[nx][ny] = '.'
                    return
            check[nx][ny] = True
            q.append((nx, ny, d+1))

for _ in range(n):
    check = [[False] * w for _ in range(h)]
    bfs(check)

print(ans)

---

참고

• 백준 온라인 저지 : BOJ 5558