5558 치 ~ 즈

5558 치 ~ 즈

최단거리를 응요해서 푸는 문제이다.

1. 방문기록과 state 정보를 함께 저장할 pair형 visited를 만든다.

2. 다음지점이 '.'일때와 치즈일 때를 나눈다.

3. '.' 일 때, first를 먼저 비교하교 같은경우 second를 비교하여 방문

4. 치즈일 때, state가 기준 이상일 때와 기준 미만일때를 나눠서 방문.

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#define P pair<int,int>
using namespace std;
 
int r, c, n, sx, sy, state;
int map[1002][1002];
P visited[1002][1002]; // first=state, second 시간
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
int bfs() {
    queue<P> q;
    q.push(P(sx, sy));
    visited[sx][sy] = P(1, 1);
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        for (int i = 0; i < 4; i++) {
            int ax = x + dx[i];
            int ay = y + dy[i];        
 
            //장애물이거나 맵 밖으로 빠져나가면 continue
            if (map[ax][ay] == 'X' || map[ax][ay] == 0) continue;
 
            //다음지점이 .일때
            if (map[ax][ay] == '.') {
                // first가 낮으면 방문, 같을때는 second까지 비교해서 방문
                if (visited[ax][ay].first < visited[x][y].first 
                    || ((visited[ax][ay].first == visited[x][y].first) 
                        && visited[ax][ay].second > visited[x][y].second + 1)) {
                    q.push(P(ax, ay));
                    visited[ax][ay].first = visited[x][y].first;
                    visited[ax][ay].second = visited[x][y].second + 1;
                }
            }
            //방문지점이 숫자일때
            else {
                // state가 기준 이상일 때
                if (visited[x][y].first >= map[ax][ay] - '0') {
                    if (map[ax][ay] - '0' == n) return visited[x][y].second;
                    map[ax][ay] = '.';
                    state++;
                    visited[ax][ay].first = state;
                    visited[ax][ay].second = visited[x][y].second + 1;
                    q.push(P(ax, ay));
                }
                //state가 기준 미만일 때
                else {
                    if (visited[ax][ay].first < visited[x][y].first 
                        || ((visited[ax][ay].first == visited[x][y].first) 
                            && visited[ax][ay].second > visited[x][y].second + 1)) {
                        q.push(P(ax, ay));
                        visited[ax][ay].first = visited[x][y].first;
                        visited[ax][ay].second = visited[x][y].second + 1;
                    }
                }
            }
        }
    }
    return 0;
}
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> r >> c >> n;
    state = 1;
 
    for (int i = 1; i <= r; i++) {
        string buf;
        cin >> buf;
        for (int j = 1; j <= c; j++) {
            map[i][j] = buf[j-1];
            if (map[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }
 
    cout << bfs() << endl;
 
}