BOJ 1445 일요일 아침의 데이트

www.acmicpc.net/problem/1445

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

 

greedy하게 다음 경로를 선택하는 쪽으로 구현하면 될 것 같아서 다익스트라를 사용하였다.

cost는 {쓰레기가 차있는 칸을 지나간 수, 쓰레기가 인접한 칸을 지나간 수} 로 해도 되지만, 나는 구현의 편의성 때문에 cost를 (쓰레기가 차있는 칸을 지나간 수) * 100000 + (쓰레기가 인접한 칸을 지나간 수) 로 하여 구현하였다.

코드는 다음과 같다.

#include <cstdio>
#include <queue>

using namespace std;


const int INF = 1e60;

int n,m;
int map[50][50];

long long visited[50][50];

char a[51];

int dr[4]={0,0,1,-1};
int dc[4]={1,-1,0,0};

bool out_of_range(int r, int c){

    if(r < 0 || c < 0 || r >= n || c >= m) return true;
    else return false;

}


int sr, sc, er, ec;

int main(){
    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++){
        scanf("%s",a);
        for(int j=0;j<m;j++){

            visited[i][j] = INF;
            
            if(a[j]=='g'){
                map[i][j] = 2;

                for(int k=0;k<4;k++){
                    int nextr = i + dr[k];
                    int nextc = j + dc[k];
                    if(out_of_range(nextr,nextc)) continue;
                    if(map[nextr][nextc]) continue;

                    map[nextr][nextc] = 1;
                }
            }
            else if(a[j] == 'S'){
                sr = i, sc = j;
            }
            else if(a[j] == 'F'){
                er = i, ec = j;
            }

        }
    }

    map[sr][sc] = 0;
    map[er][ec] = 0;

    priority_queue< pair<long long, pair<int, int>>> pq;

    pq.push({0, {sr, sc}});

    while(!pq.empty()){

        auto t = pq.top();
        pq.pop();

        int nowr = t.second.first;
        int nowc = t.second.second;

        long long nowt = -t.first;
        
        if(nowr == er && nowc == ec){
            printf("%lld %lld\n", 
                    visited[nowr][nowc]/100000, visited[nowr][nowc]%100000);
            break;
        }
        

        for(int i=0;i<4;i++){

            int nextr = nowr + dr[i];
            int nextc = nowc + dc[i];

            long long nextt = nowt;

            if(out_of_range(nextr, nextc)) continue;
            if(map[nextr][nextc] == 2){
                nextt = nowt + 100000;
            }
            else if(map[nextr][nextc] == 1){
                nextt = nowt + 1;
            }

            if(visited[nextr][nextc] > nextt){
                visited[nextr][nextc] = nextt;
                pq.push({-nextt, {nextr, nextc}});
            }

        }
    }




    return 0;
}

(cost의 type을 int 로 해도 통과한다.)

S와 F를 세지 않는다는 조건을 처리를 하지 않아 계속 WA를 받았었다.

해당 test case는 다음과 같다

6 6

ggggg.

g..F..

gggggg

..g...

ggg..g

...S.g