[BaekJoon/백준] 5558번 Cheese

 

 

일본어로 된 문제다.

 

구글 번역기를 돌려서 해결하엿따

 

 

어렵게 생각할 필요 없는게, 그냥 숫자 순서대로 치즈를 먹으러 간다고 보면 된다.

같은 숫자는 없다는게 문제의 가정이다.

 

 

S는 시작지점이고

X는 갈 수 없는 지점이다.

 

맵 내에서 숫자들을 만날 때 마다, 해당 숫자들을 저장해준 뒤 오름차순으로 정렬한 뒤

낮은 숫자부터 찾아가면 된다.

 

각 숫자를 찾아간 뒤에는 VISIT을 초기화해주는 것도 잊지 않는다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M, K;

char MAP[1000][1000];
int VISIT[1000][1000];

int SX, SY;

vector<pair<int, pair<int, int>>> CHEESSE;

int mx[4] = {0, 0, -1, 1};
int my[4] = {1, -1, 0, 0};


int cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
    
    return a.first < b.first;
    
}

int bfs(int x, int y, int GOAL_X, int GOAL_Y) {
    
    queue<pair<int, int>> que;
    
    que.push({x, y});
    VISIT[x][y] = 1;
    
    
    while(!que.empty()) {
        
        int x = que.front().first;
        int y = que.front().second;
        
        que.pop();
        
        if(x == GOAL_X && y == GOAL_Y) {
            SX = GOAL_X; SY = GOAL_Y;
            return VISIT[x][y] - 1;
        }
        
        for(int i = 0; i < 4; i++) {
            
            int tx = x + mx[i];
            int ty = y + my[i];
            
            if(tx < 0 || tx >= N || ty < 0 || ty >= M)
                continue;
            
            
            if(VISIT[tx][ty] == 0 && MAP[tx][ty] != 'X') {
                
                que.push({tx, ty});
                VISIT[tx][ty] = VISIT[x][y] + 1;
                                
            }
        }
        
        
    }
    
    return -1;
}

int main() {
    
    cin >> N >> M >> K;
    
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            
            cin >> MAP[i][j];
            
            if(MAP[i][j] == 'S') {
                SX = i; SY = j;
            }
            
            if(MAP[i][j] >= '1' && MAP[i][j] <= '9') {
                CHEESSE.push_back({MAP[i][j]-'0', {i, j}});
            }
        }
    }
    
    sort(CHEESSE.begin(), CHEESSE.end(), cmp);
    
    
    int TO = 0;
    for(int i = 0; i < CHEESSE.size(); i++) {
        
        memset(VISIT, 0, sizeof(VISIT));
        
        TO += bfs(SX, SY, CHEESSE[i].second.first, CHEESSE[i].second.second);
        
    }
    cout << TO << "\n";
    
    
}

 

 

소요 시간 : 30분