BOJ 5558 チーズ

백준 5558 링크

https://www.acmicpc.net/problem/5558

문제 해석(클릭?)

문제

올해도 JOI구역에서 치즈 공장이 생산을 시작해, 쥐들이 집에서 얼굴을 내밀었다. JOI구역은 동서남북으로 구역이 정리되어있고, 각 구역은 쥐집, 치즈공장, 장애물, 빈땅으로 정리할 수 있다. 쥐들은 집에서 출발하여 모든 치즈공장을 방문하여 치즈를 하나씩 먹는다. 이 구역에는 N개의 치즈공장이 있고, 치즈를 하나 먹을 때마다 체력이 1씩 오른다. 다만, 쥐는 자신의 체력보다 단단한 치즈를 먹을 수는 없다. 쥐는 동서남북으로 이웃해있는 구획에 1분걸려 이동할수 있으나, 장애물이 있는 구역에는 들어갈 수 없다. 치즈공장에서 치즈를 먹지 않고 지나가는 것도 가능하다. 모든 치즈를 먹는데 걸리는 최단시간을 구하여라. 단, 쥐가 치즈를 먹는데 걸리는 시간은 무시한다.

입력

입력은 H+1행이 있다. 첫째행에는 세 정수 H，W，N (1 ≦ H ≦ 1000，1 ≦ W ≦ 1000，1 ≦ N ≦ 9)가 이 순서대로 공백에 구분지어 적혀있다. 두번째 행부터 H+1행째까지의 각행에는 'S'，'1', '2', ..., '9'，'X'，'.'으로 이루어진 W문자의 문자열이 적혀있어, 각각이 각구획의 상태를 표시한다. 북쪽에서 i번째, 서쪽에서 j번째의 구획을 (i,j)로 기입하는 것으로 하면 (1 ≦ i ≦ H, 1 ≦ j ≦ W), 제 i+1번째 행의 j번째 문자는 구획(i,j) 이 쥐집인 장소는 'S'가 되고, 장애물인 장소는 'X'가 되고, 빈 땅은 '.' 이 된다. 단단함이 1, 2, ..., 9인 치즈를 생산하는 공장이 있는 장소는 각각 '1', '2', ..., '9' 이 된다. 입력에는 쥐집과 단단함 1, 2, ..., N의 치즈를 생산하는 공장이 각각 하나씩 있다. 다른 집단은 장애물 혹은 빈 땅이 보증되어있다. 쥐는 모든 치즈를 먹는것이 보증되어있다.

출력

모든 치즈를 먹는데 걸리는 최단시간 (분)을 표현하는 정수를 1행에 출력하여라.

사실 예제의 입력하고 출력만 보면 느낌 오죠? 😎

풀이방법

難しくはなかった。🙄

코드

#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;
char map[1005][1005];
bool visit[1005][1005];
int target[12][2];
int start[2];
int r, c, n, cnt;
int ly[] = { 1,-1,0,0 };
int lx[] = { 0,0,1,-1 };
typedef struct record {
    int y, x, mov_n;
};
bool isin(int y, int x) {
    if (y >= 1 && y <= r && x >= 1 && x <= c && map[y][x] != 'X')
        return true;
    else
        return false;
}
void find(int y, int x, int n) {
    queue <record> q;
    q.push({ y,x,0 });
    visit[y][x] = true;
    while (!q.empty()) {
        record t = q.front(); q.pop();
        // 도착했는지 확인
        if (t.y == target[n][0] && t.x == target[n][1]) {
            cnt += t.mov_n;
            start[0] = t.y;
            start[1] = t.x;
            break;
        }
        // 아니면 계속 돎
        for (int i = 0; i < 4; i++) {
            int ny = t.y + ly[i];
            int nx = t.x + lx[i];
            if (isin(ny, nx) && !visit[ny][nx]) {
                q.push({ ny, nx, t.mov_n + 1 });
                visit[ny][nx] = true;
            }
        }
    }
}
int main() {
    //freopen("input.txt", "r", stdin);
    cin >> r >> c >> n;
    //입력
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            cin >> map[i][j];
            if (map[i][j] >= '0' && map[i][j] <= '9') { //순서 지정
                target[map[i][j] - '0'][0] = i;
                target[map[i][j] - '0'][1] = j;
            }
            if (map[i][j] == 'S') { //시작지점
                start[0] = i;
                start[1] = j;
            }
        }
    }
    //찾는 과정 시작
    for (int i = 1; i <= n; i++) {
        memset(visit, false, sizeof(visit));
        find(start[0], start[1], i);
    }
    cout << cnt;
}