Gidhub BE Developer

[BOJ] 2206. 벽 부수고 이동하기

2018-09-23
goodGid

Problem

Problem URL : 벽 부수고 이동하기


[1] Answer Code (18. 09. 23)

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

int map[1000][1000];
int v[1000][1000][2];

int n,m;

int dx[] = {1,0,0,-1};
int dy[] = {0,1,-1,0};

struct Node{
    int x;
    int y;
    int time;
    int break_used; // Break했다면 True
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int ans = 2e9;
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        for(int j=0; j<m; j++){
            map[i][j] = s[j] - '0';
        }
    }
    
    Node node{0,0,1,0};
    queue<Node> q;
    q.push(node);
    v[0][0][0] = 1; // 0,0위치 Break하지 않은 상태로 방문했다.
    
    while (! q.empty()) {
        Node top = q.front();
        q.pop();
        int x = top.x;
        int y = top.y;
        int time = top.time;
        int break_used = top.break_used;
        
        if( x == n-1 && y == m-1 ){
            ans = time;
            break;
        }
    
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            
            // 벽이 있고 Break 가능 상태
            if(map[nx][ny] == 1){
                if(break_used == 1) continue;
                if(! v[nx][ny][1]  ){
                    q.push(Node{nx,ny,time+1,1});
                    v[nx][ny][1] = 1;
                }
            } // end of if
            else{
                if(!v[nx][ny][break_used]){
                    q.push(Node{nx,ny,time+1, break_used});
                    v[nx][ny][break_used] = 1;
                }
            }
        }
    }
    
    if(ans == 2e9)
        ans = -1;
    cout << ans << endl;
    return 0;
}

Review

  • BFS에 대한 기초적인 지식이 부족함을 많이 느낀다.

  • 뭔가 SWEA만 풀다보니 BOJ에 있는 BFS유형에 익숙지 않은 느낌도 든다.

  • 오히려 알고리즘에 대한 자신감이 떨어지는거 같다. 큰일이다.

 if( x == n-1 && y == m-1 ){
            ans = time;
            break;
        }
  • 위 코드가 자꾸 맘에 걸렸다.

  • 가장 먼저 도착하는 값이 최적의 해라는걸 어떻게 증명할까?

  • 생각보다 단순하게 증명이 된거 같다.

  • Tree에서 BFS를 돌리면 같은 레벨에 있는거 부터 체크한다.

  • 그렇기 때문에 가장 먼저 도착하는게 최적이다.


Comments

Content