Gidhub BE Developer

[BOJ] 3055. 탈출

2018-02-05
goodGid

Problem

Problem URL : 탈출

Screenshots of Problem Explain

[1] Answer Code (18. 02. 05)


#include<iostream>
#include<queue>
using namespace std;

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
char map[51][51];
int n,m;
queue<pair<int,int>> w_q;
queue<pair<int,int>> s_q;

int main(){
    pair<int, int> d; // d is Destination
    
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            scanf(" %c", &c);
            if( c == '*'){
                map[i][j] = '*';
                w_q.push({i,j});
            }
            else if ( c == 'S'){
                map[i][j] = 'S';
                s_q.push({i,j});
            }
            else if ( c == 'D'){
                map[i][j] = 'D';
                d = {i,j};
            }
            else if ( c == 'X'){
                map[i][j] = 'X';
            }
            else
                map[i][j] = '.';
        }
    }
    
    int ans=0;
    
    while (! s_q.empty()) {
        int nx,ny;
        int w_size = (int) w_q.size();
        int s_size = (int) s_q.size();
        ans ++;
        for(int i=0; i<s_size; i++){
            int s_x = s_q.front().first;
            int s_y = s_q.front().second;
            s_q.pop();
            
            if( map[s_x][s_y] != 'S') continue;
            
            for(int j=0; j<4; j++){
                nx = s_x + dx[j];
                ny = s_y + dy[j];
                
                if( map[nx][ny] == '.' ){
                    map[nx][ny] = 'S';
                    s_q.push({nx,ny});
                }
                
                if( map[nx][ny] == 'D'){
                    cout << ans << endl;
                    return 0;
                }
            }
        }
        
        for(int i=0; i<w_size; i++){
            int w_x = w_q.front().first;
            int w_y = w_q.front().second;
            w_q.pop();
            
            for(int j=0; j<4; j++){
                nx = w_x + dx[j];
                ny = w_y + dy[j];
                
                if( map[nx][ny] == '.' || map[nx][ny] == 'S' ){
                    map[nx][ny] = '*';
                    w_q.push({nx,ny});
                }
            }
        }
    }
    
    cout << "KAKTUS" << endl;
    
    return 0;
}

Review

  • 알쿡 대회에 출제되었던 구현 문제

  • 대회 때 시간이 없어서 아예 보지도 못했던 문제

  • BFS + 구현문제이다.

  • 한 번에 풀었는데 너무나 뿌듯하더라 그리고 이런 문제 무서워서 포기하려 했는데 포기 안하길 잘했다 !


Comments

Content