[정올] 2893 : 제리의 치즈먹기 (Cheese)

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2156&sca=9030 

JUNGOL

 

문제 이해 

제리의 체력이 치즈를 먹을 때마다 1씩 증가하고, 치즈는 1에서 N까지 하나씩만 있으므로, 

1에서 N까지의 치즈를 순서대로 하나하나씩 찾아가는 경로를 찾으면 된다.

최단 시간(경로) 를 찾으라고 했으니 BFS를 사용하는 문제일 것이다. 

 

좀 더 자세히 보자면

시작위치에서 1까지 가는 최단 경로를 BFS를 이용해서 찾고,

2에서 3까지의 최단 경로를 BFS를 이용해서 찾고 이런 식이다.

 

각 BFS를 호출할 때마다 큐와 visited 배열을 초기화 하는 것을 잊지 말자!!

 

추가적으로 주의해야할 점은, map을 문자열로 받기 때문에 정수와의 호환이 필요하다는 점이다.

다행히 치즈가 최대 9개라서, 각 치즈의 위치를 map 배열을 탐색해서 찾는 것도, BFS를 9번 호출하는 것도 가능하다.

 

작성 코드

#include <stdio.h>
#define SIZEY 1000
#define SIZEX 1000

int H, W, N;
char map[SIZEY + 10][SIZEX + 10];
int visited[SIZEY + 10][SIZEX + 10];

// 치즈 공장 좌표 
int desty[10];
int destx[10];

int ans;

typedef struct pos {
    int y;
    int x;
    int t;
}POS;

POS q[SIZEY * SIZEX + 10];
int wp, rp;

void enq(int y, int x, int t) {
    q[wp].y = y;
    q[wp].x = x;
    q[wp].t = t;
    wp++;
}

POS deq(void) {
    POS tmp = q[rp];
    rp++;
    return tmp;
}

int empty(void) {
    return wp == rp;
}

int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

int BFS(int sy, int sx, int oy, int ox) {
    enq(sy, sx, 1);
    visited[sy][sx] = 1;

    while (!empty()) {
        POS cur = deq();

        if (cur.y == oy && cur.x == ox) return cur.t;

        for (int i = 0; i < 4; i++) {
            int ny = dy[i] + cur.y;
            int nx = dx[i] + cur.x;

            if (ny < 0 || ny >= H) continue;
            if (nx < 0 || nx >= W) continue;
            if (visited[ny][nx] > 0) continue;
            if (map[ny][nx] == 'X') continue;

            if (ny == oy && nx == ox) return cur.t + 1;
            visited[ny][nx] = cur.t;
            enq(ny, nx, cur.t + 1);
        }
    }
    return -1;
}

void Solve(void) {
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (map[i][j] >= '1' && map[i][j] <= '9') {
            // 1번부터 9번까지 치즈 위치 찾기
                desty[map[i][j] - '0'] = i;
                destx[map[i][j] - '0'] = j;
            }
            if (map[i][j] == 'S') {
            // 시작은 제리의 위치부터
                desty[0] = i;
                destx[0] = j;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        // dest 배열의 i 번째 위치에서 i+1 번째 위치로 가는 BFS 수행
        ans += BFS(desty[i], destx[i], desty[i + 1], destx[i + 1])-1;
        
        // 초기화
        wp = 0, rp = 0;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                visited[i][j] = 0; // 초기화
            }
        }
    }
}

int main(void) {

    // get input
    scanf("%d %d %d", &H, &W, &N);
    for (int i = 0; i < H; i++) {
        scanf("%s", &map[i]);
    }
    Solve();
    printf("%d", ans);
    return 0;
}