[C++] 백준 2206 벽 부수고 이동하기 + 결정적 반례

• 문제

• 풀이 과정

• 초기 접근 방법

• 초기 코드 ( 정답 X )

• <반례 입력>

• 최종 코드

• 잡담

백준 2206 : 벽 부수고 이동하기
난이도 : 골드 3

시간 : 1시간 30분 소요(온전히 자력X, 반례 찾아봄)

 

 

 

문제

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

풀이 과정

 

고민을 많이 해본 문제이다.

 

초기 접근 방법

먼저 bfs를 사용하여 구현했다.

조건 검사 크게 4가지였다.

1. 범위를 벗어나는 경우를 먼저 검사 ( 1~N, 1~M)

2. 방문했는지 검사 후에

  2-1. 벽이 있으면 벽을 부술 수 있는지 확인하며, 부술 수 있다면 부수고 큐에 넣는다.

  2-2. 벽이 없으면 방문처리가 하고 큐에 넣는다.

 

 

초기 코드 ( 정답 X )

#include <iostream>
#include <queue>
#include <cstring>

using namespace::std;

int N, M;
int board[1001][1001];
bool pos[1001][1001];
int visited[1001][1001];

int ud[4] = {-1,1,0,0};
int lr[4] = {0,0,-1,1};

void bfs(int y, int x){
    queue<pair<int, int>> q;
    visited[y][x] = 1;
    q.push({y, x});
    
    while(!q.empty()){
        int ty = q.front().first;
        int tx = q.front().second;
        q.pop();
        
        if(ty == N && tx == M){
            break;
        }
        
        for(int i=0; i<4; i++){
            int ny = ty + ud[i];
            int nx = tx + lr[i];
            if(ny>=1 && nx >= 1 && ny<=N && nx<=M){
                if(visited[ny][nx] == 0){
                    if(board[ny][nx] == 1 && !pos[ty][tx]){
                        pos[ny][nx] = true;
                        visited[ny][nx] = 1+visited[ty][tx];
                        q.push({ny, nx});
                    }else if(board[ny][nx] == 0){
                        visited[ny][nx] = 1+visited[ty][tx];
                        pos[ny][nx] = pos[ty][tx];
                        q.push({ny, nx});
                    }
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &N, &M);
    
    for(int i=1; i<=N; i++){
        string tmp;
        cin>>tmp;
        for(int j=1; j<=M; j++){
            board[i][j] = tmp[j-1] - 48;
        }
    }
    
    bfs(1, 1);
    if(visited[N][M] == 0){
        printf("-1\n");
        return 0;
    }
    printf("%d\n", visited[N][M]);
}

 

이 방법으로 했지만 실패했고, 어떤 것이 잘못됐는지 생각했다.

하지만 반례를 생각하지 못해 여러 반례들을 봤고, 결정적인 반례를 찾았다.

빨간색 부분이 잘못된 것이었다.

 

<반례 입력>

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

출력 : 29

https://www.acmicpc.net/board/view/66299

글 읽기 - 반례 모음집

 

나는 출력이 "-1"로 되었다.

그리고 무엇이 잘못됐는지 고민을 했다.

 

핵심은 벽을 부수고 방문할 때와 벽을 부수지 않고 방문할 때를 구별해야 한다는 것이다.

 

위의 반례를 보면 초록루트가 정답 루트이며, 노란 루트는 반례가 되는 루트이다.

초록루트가 빨간색 지점에 도착하면 이미 방문처리가 됐기 때문에 더이상 진행을 못하게 된다.

 

따라서 visited[1001][1001] 배열을 visited[1001][1001][2]로 바꿔 벽을 부수고 방문했는지 부수지 않고 방문했는지 구별했다.

 

또한, 큐를 위에서 아래로 바꿔서 벽 파괴여부와 거리 카운팅을 위한 변수도 선언했다.

queue<pair<int, int>> q;

queue<pair<pair<int, int>, pair<int, int>>> q;  // {{좌표, 좌표}, {벽 파괴여부, 거리카운팅}}

 

그 후 조건검사는

1. 큐에서 나온 노드가 벽을 부순 노드인지 벽을 부수지 않은 노드인지 판별한다.

2. 벽을 부쉈다면 더이상 벽을 만나면 안된다.

3. 벽을 부수지 않았다면

   3-1. 다음 갈 곳이 벽이라면 벽을 부수고, 벽 파괴여부를 1로 바꾸고, 거리 카운팅을 하고, 큐에 넣는다.

   3-2. 다음 갈 곳이 벽이 아니라면 거리 카운팅만 하고, 큐에 넣는다.

4. 목적지에 도달하면 fin 변수로 표시하고, 출력한다.

5. 도달하지 못했다면 fin 변수가 그대로이기 때문에 "-1"를 출력한다.

 

최종 코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace::std;

int N, M;
int board[1001][1001];
int visited[1001][1001][2];
bool fin = true;

int ud[4] = {-1,1,0,0};
int lr[4] = {0,0,-1,1};

void bfs(int y, int x){
    queue<pair<pair<int, int>, pair<int, int>>> q;
    visited[y][x][0] = 1;
    visited[y][x][1] = 1;

    q.push({{y, x}, {0, 1}});
    
    while(!q.empty()){
        int ty = q.front().first.first;
        int tx = q.front().first.second;
        int wall = q.front().second.first;
        int c = q.front().second.second;
        q.pop();
        
        if(ty == N && tx == M){
            printf("%d\n", c);
            fin = false;
            break;
        }
        
        for(int i=0; i<4; i++){
            int ny = ty + ud[i];
            int nx = tx + lr[i];
            if(ny>=1 && nx >= 1 && ny<=N && nx<=M){
                if(wall == 1 && visited[ny][nx][1] == 0){  // 벽 뚫었다면
                    if(board[ny][nx] == 0){  // 이제 벽이 없어야 함.
                        visited[ny][nx][1] = 1;
                        q.push({{ny, nx}, {wall, c+1}});
                    }
                }
                else if(wall == 0){  // 벽을 뚫지 않은 상태
                    if(board[ny][nx] == 1){  // 현재 벽 뚫기
                        visited[ny][nx][1] = 1;
                        q.push({{ny, nx}, {1, c+1}});
                    }
                    else if(board[ny][nx] == 0 && visited[ny][nx][0] == 0){  // 현재 벽 x
                        visited[ny][nx][0] = 1;
                        q.push({{ny, nx}, {0, c+1}});
                    }
                }
            }
        }
    }
}

int main(){
    scanf("%d %d", &N, &M);
    
    for(int i=1; i<=N; i++){
        string tmp;
        cin>>tmp;
        for(int j=1; j<=M; j++){
            board[i][j] = tmp[j-1] - 48;
        }
    }
    
    bfs(1, 1);
    
    if(fin){
        printf("-1\n");
    }
}

 

 

잡담

pair 를 두 쌍으로 사용가능한지는 몰랐는데 유용한 것을 알게 되었다.

예전에는 골드3 정도면 무척이나 버거웠는데 이젠 그래도 풀만하다는 생각이 든다.

그래도 반례는 자력으로 찾은 것이 아니기 때문에 아직 더 많은 노력이 필요한 것 같다.