[백준][C++] 1445 일요일 아침의 데이트

www.acmicpc.net/problem/1445

1445번: 일요일 아침의 데이트

 

 

 

알고리즘 종류

다익스트라

우선순위 큐

 

 

 

사고 과정

다익스트라를 2차원 배열에 사용하여 해결했습니다.

 

값을 저장할 dp 2차원 배열을 만들어 줍니다.

 

시작점에서 출발하여, 아래 2가지 조건으로 비교합니다.

1. 쓰레기를 지나는 경우 비교

2. 쓰레기를 지나는 경우가 같으면, 쓰레기 주변을 지나는 경우 비교

 

목표 지점에 도착하면, 종료합니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#define MAX 987654321
 
using namespace std;
 
struct State{
    int y;
    int x;
    int pass; // 쓰레기를 지나간다. 
    int around; // 쓰레기 주변을 지나간다. 
};
 
struct Tmp{
    int pass=MAX;
    int around=MAX;
};
 
struct cmp{
    bool operator()(State a, State b){
        if(a.pass != b.pass) return a.pass > b.pass; // 쓰레기 적게 지나가는 거 먼저   
        return a.around > b.around; // 쓰레기 지나가기가 같을 경우, 주변을 적게 지나가는 거 먼저  
    }
};
 
int h, w;
int sy, sx;
 
char mat[51][51];
Tmp dp[51][51];
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
 
bool isValid(int y, int x){
    return (y>=0 && y<h) && (x>=0 && x<w);
}
 
// 쓰레기 주변 표시  
void around_garbage(){
    
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            
            if(mat[i][j] == 'g'){
                for(int d=0; d<4; d++){
                    int ny = i + dir[d][0];
                    int nx = j + dir[d][1];
                    
                    if(isValid(ny, nx) && mat[ny][nx] == '.'){
                        mat[ny][nx] = '#';
                    }
                }
            }
        }
    }
}
 
 
void solution(){
    
    around_garbage();
 
    priority_queue<State, vector<State>, cmp> pq; 
    pq.push({sy, sx, 0, 0});
    
    dp[sy][sx].pass = 0;
    dp[sy][sx].around = 0;
    
    while(true){
        
        int y = pq.top().y;
        int x = pq.top().x;
        int p = pq.top().pass;
        int a = pq.top().around;
        pq.pop();
 
        for(int d=0; d<4; d++){
            int ny = y + dir[d][0];
            int nx = x + dir[d][1];
            int np = p;
            int na = a;
            
            // 목표에 도착  
            if(mat[ny][nx] == 'F'){
                cout << np << " " << na << endl;
                return;
            }
            
            if(!isValid(ny, nx)) continue;
            
            if(mat[ny][nx] == 'g') np += 1;
            else if(mat[ny][nx] == '#') na += 1;
            
            // 쓰레기 지나는 경우 비교  
            if(dp[ny][nx].pass > np){
                dp[ny][nx].pass = np;
                dp[ny][nx].around = na;
                pq.push({ny, nx, dp[ny][nx].pass, dp[ny][nx].around});
            }
            // 쓰레기 지나는 경우가 같으면, 쓰레기 주변을 지나는 경우 비교  
            else if(dp[ny][nx].pass == np){
                if(dp[ny][nx].around > na){
                    dp[ny][nx].around = na;
                    pq.push({ny, nx, dp[ny][nx].pass, dp[ny][nx].around});
                }
            }
        }
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> h >> w;
    
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> mat[i][j];
            
            if(mat[i][j] == 'S'){
                sy = i;
                sx = j;
            }
        }
    }
    
    solution();
}
 

 

 

 

시행착오