[백준] 2206 벽 부수고 이동하기 C++

1. 문제 설명

• 링크 : https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

---

2. 풀이 과정

• 문제 해결의 흐름 
  1. 맵의 정보를 입력 받은 배열(land)를 기준으로 시작점은 land[0][0], 도착점은 land[N-1][M-1]일 것이다.
  2. 벽을 한 번만 부술 수 있으므로 다음의 기준으로 bfs를 구현하면 어떨까? 
     • (1) 다음 칸이 벽이고 벽을 부술 수 있다면? 벽을 뚫고 방문처리 
     • (2) 다음 칸이 벽이 아니고 아직 방문하지 않았다면? 방문처리
• 나의 코드 (1번째 시도) 

#include <iostream>
#include <queue>
#include <string>

using namespace std;

struct coordinate {
    int row;
    int col;
    int cnt;
};

int N, M; // N : 행, M : 열
int land[1001][1001] = {};  // 전부 0으로 초기화
int visited[1001][1001] = {};    
queue<coordinate> q;
int dr[4] = {0,1,0,-1}; // 행
int dc[4] = {1,0,-1,0}; // 열

int bfs() {
    coordinate start = {0,0,0};
    q.push(start); // 시작 지점은 무조건 0,0, 벽 부순 횟수는 0
    visited[0][0] = 1;

    while (!q.empty()) {
        // 현재 위치 및 벽을 부숫 횟수
        int now_row = q.front().row;
        int now_col = q.front().col;
        int cnt = q.front().cnt;
        q.pop();

        // 도착지에 도착했다면 결과값 return해주기
        if (now_row == (N-1) && now_col == (M-1)) return visited[now_row][now_col];

        for (int i = 0; i < 4; i++) {
            int new_row = now_row + dr[i];  // 행 이동
            int new_col = now_col + dc[i];  // 열 이동

            if (new_row >= N || new_col < 0 || new_col >= M || new_row < 0) continue;   // 범위에 벗어나면 continue

            if (land[new_row][new_col] == 1 && cnt == 0) { // 다음 칸이 벽이고 벽을 부술 수 있다면 (벽을 부술 수 있다는 것 자체가 처음 방문한다는 거임. 왜냐하면 한 번만 부술 수 있으니깐)
                coordinate new_coordinate = {new_row, new_col, cnt + 1};
                q.push(new_coordinate);
                visited[new_row][new_col] = visited[now_row][now_col] + 1;
            } else if (land[new_row][new_col] == 0 && visited[new_row][new_col] == 0) {  // 다음 칸이 벽이 아니고 방문하지 않았을 때
                coordinate new_coordinate = {new_row, new_col, cnt};
                q.push(new_coordinate);
                visited[new_row][new_col] = visited[now_row][now_col]+ 1;
            }
        }
    }


    return -1;
}

int main() {
    // 입력 받기
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string line ;
        cin >> line;
        for (int j = 0; j < line.size(); j ++) {
            land[i][j] = line[j] - '0';
        }
    }

    cout << bfs();

    return 0;
}

• 그러나 18%에서 틀렸다 ㅠㅠㅠㅠ... 도대체 왜지...??

 

 

• 반례를 통해 놓친 점이 무엇인지 생각해보았다. 반례는 다음과 같다. 

•  위의 예시에 따르면 land[0][0]에서 land[5][4]까지의 최단거리는 land[5][3]의 벽 한 개만 부수는 것이다. 즉, 도착점까지 ㄹ의 형태로 이동해야 한다. 그러나 ⭐️⭐️ 나의 코드에 의하면 visited[2][0]의 값은 land[1][0]의 벽을 부순 이동이 선점하게 된다. 그렇기에 ㄹ의 형태로 이동하는 과정은 visited[2][0]의 값이 0이 아니기에 land[2][0]을 통해 이동하지 못하게 된다. 
•  ⭐️⭐️ 이러한 문제를 해결하기 위해서는 벽을 부순 이동과 벽을 부수지 않은 이동의 방문처리를 다르게 처리해주어야 한다. 따라서 벽을 부순 채 이동하는 visited 배열과 벽을 부수지 않고 이동하는 visited 배열, 2가지 배열을 만들어주자! 
•  나의 코드 (성공!!) 

#include <iostream>
#include <queue>
#include <string>

using namespace std;

struct coordinate {
    int row;
    int col;
    int cnt;
};

int N, M; // N : 행, M : 열
int land[1001][1001] = {};  // 전부 0으로 초기화
int visited[1001][1001][2] = {};    // [0] : 벽을 부수지 않은 채 이동, [1] : 벽을 한 번 부순 채 이동
queue<coordinate> q;
int dr[4] = {0,1,0,-1}; // 행
int dc[4] = {1,0,-1,0}; // 열

int bfs() {
    coordinate start = {0,0,0};
    q.push(start); // 시작 지점은 무조건 0,0, 벽 부순 횟수는 0
    visited[0][0][0] = 1;

    while (!q.empty()) {
        // 현재 위치 및 벽을 부숫 횟수
        int now_row = q.front().row;
        int now_col = q.front().col;
        int cnt = q.front().cnt;
        q.pop();

        // 도착지에 도착했다면 결과값 return해주기
        if (now_row == (N-1) && now_col == (M-1)) return visited[now_row][now_col][cnt];

        for (int i = 0; i < 4; i++) {
            int new_row = now_row + dr[i];  // 행 이동
            int new_col = now_col + dc[i];  // 열 이동

            if (new_row >= N || new_col < 0 || new_col >= M || new_row < 0) continue;   // 범위에 벗어나면 continue

            if (land[new_row][new_col] == 1 && cnt == 0) { // 다음 칸이 벽이고 벽을 부술 수 있다면 (벽을 부술 수 있다는 것 자체가 처음 방문한다는 거임. 왜냐하면 한 번만 부술 수 있으니깐)
                coordinate new_coordinate = {new_row, new_col, cnt + 1};
                q.push(new_coordinate);
                visited[new_row][new_col][cnt + 1] = visited[now_row][now_col][cnt] + 1;
            } else if (land[new_row][new_col] == 0 && visited[new_row][new_col][cnt] == 0) {  // 다음 칸이 벽이 아니고 방문하지 않았을 때
                coordinate new_coordinate = {new_row, new_col, cnt};
                q.push(new_coordinate);
                visited[new_row][new_col][cnt] = visited[now_row][now_col][cnt] + 1;
            }
        }
    }


    return -1;
}

int main() {
    // 입력 받기
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        string line ;
        cin >> line;
        for (int j = 0; j < line.size(); j ++) {
            land[i][j] = line[j] - '0';
        }
    }

    cout << bfs();

    return 0;
}

 

 

• 이 문제를 통해 알 수 있는 것들 
  • ⭐️ '이맞틀....?'을 외치기 전에 반례를 통해 코드의 문제점을 찾아보자! 
  • ⭐️ bfs는 항상 최단거리로 이동한다.
  • ⭐️ 2차원 배열을 사용하는 문제를 풀 때 앞으로 dx[4], dy[4] 대신 dr[4], dc[4]를 사용하자. (헷갈림 방지!!)

---

3. 후기 

 포기 직전까지 갔었다 ㅠ.. 반례를 통해 내 코드의 문제점을 찾았다!!! 반례는 신이다.