백준 2206. 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

전에 푼 토마토 같은 bfs 문제와 거의 같지만 다른점은 벽을 한번 뚫을수가 있다.

처음에는 bfs탐색으로 맵을 이동하면서 막히면 벽을 뚫고 그것을 큐에 같이 넣어서 다음 큐에서 팝했을때 벽이 이미 뚫었다는 정보가 담겨있다면 안뚫고 진행하는 방식으로 짰는데, 그게 최단경로가 아닐수가 있어서 실패했다.

 

답들을 보니 방문여부를 체크하는 배열을 3차원으로 만들어서 벽을 부쉈는지 안부쉈는지에 대한 정보도 담아서,

같은 정점이라도 벽을 부수고 왔는지 안부수고 왔는지를 확인해줄수 있다.

 

1. 맵을 벗어나는지 체크하고

 

2. 갈수 있는길이고, 아직 방문하지 않았다면 큐에넣고, 방문여부 체크하는 mark배열에 기록

벽을 뚫지 않았으므로 mark[nr][nc][wall]에 기록. 

큐에 {{nr,nc}, wall} 푸쉬.

 

3. 갈수 없는 길이고, 벽을 뚫을수 있는 기회가 남아있다면, 

벽을 뚫었으므로 mark[nr][nc][wall-1]에 기록, 

큐에 {{nr,nc}, wall-1} 푸쉬.

 

#include <iostream>
#include <queue>
using namespace std;
#define MAX 1001
#include <cstdio>

int N, M;
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
char map[MAX][MAX];
int mark[MAX][MAX][2];
int idx = 1;

int bfs() {
    // {r,c}, 부실수 있는 벽 횟수
    queue<pair<pair<int,int>, int>> q;
    // {1,1}에서 시작, 벽 1번 부술수 있음
    q.push({{1,1},1});
    mark[1][1][1] = 1;

    while(!q.empty()) {
        int r = q.front().first.first;
        int c = q.front().first.second;
        int wall = q.front().second;
        q.pop();

        if(mark[r][c][wall] > idx) idx++;

        if(r == N && c == M) {
            return mark[r][c][wall];
        }

        // 4방향으로 탐색
        for(int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            // 맵 벗어나면 실행안함
            if(nr < 1 || nr > N || nc < 1 || nc > M) continue;

            // 갈수있는 길이고, 방문하지 않았다면
            if(map[nr][nc] == '0' && mark[nr][nc][wall] == 0) {
                q.push({{nr,nc}, wall}); // 갈수있는 길이므로 wall안부숴도 됨
                mark[nr][nc][wall] = idx+1;
            }
            // 갈수없는 길이고, 벽을 뚫을수 있는 기회가 남았다면
            if(map[nr][nc] == '1' && wall) {
                mark[nr][nc][wall-1] = idx+1;
                // 벽을 뚫었으므로 벽을 뚫을수있는 기회가 소진됨. wall-1
                q.push({{nr,nc},wall-1});
            }

        }

    }
    return -1;
}

void print() {
    for(int re = 0; re < 2; re++) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= M; j++) {
                cout << mark[i][j][re] << ' ';
            } cout << '\n';
        }    cout << '\n\n';
    }

}

int main() {

    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        scanf("%s", &map[i][1]);
    }
    
    cout << bfs();
}

 

 

---

또 다른 블로그글을 보고 공부하던 중에 실행속도를 향상시킬수 있는 방법을 찾았다.

이전에 맵을 입력받을때 scanf("%1d", &arr[i][j]) 이런식으로 받아서 총 M x N 번을 받았는데

arr을 char형으로 선언하고 scanf("%s", &arr[i][1]) 이런식으로 받아주면 N번만 입력을 받으면 되기때문에 속도가 빨라진다. 

그리고 bfs 탐색에서 arr값을 확인할때 그냥 if(arr[i][j] == '1') 이런식으로 캐릭터형을 비교해주면 된다.

 

#include <iostream>
#include <queue>
using namespace std;
#define MAX 1001

int N,M;
char arr[MAX][MAX];
int mark[MAX][MAX][2];
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

int bfs() {
    /* {r,c}, 벽뚫을수 있는 횟수 */
    queue<pair<pair<int,int>, int>> q;
    q.push({{1,1},1});
    mark[1][1][1] = 1;

    while(!q.empty()) {
        int r = q.front().first.first;
        int c = q.front().first.second;
        int wall = q.front().second;
        q.pop();

        if(r == N && c == M) {
            return mark[r][c][wall];
        }

        /*4방향으로 탐색*/
        for(int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            /* 맵벗어나면 실행안함 */
            if(nr < 1 || nr > N || nc < 1 || nc > M) continue;
            /* 갈수있는 길이고, 아직 방문하지 않았으면 */
            if(arr[nr][nc] == '0' && mark[nr][nc][wall] == 0) {
                mark[nr][nc][wall] = mark[r][c][wall] + 1;
                q.push({{nr,nc}, wall});
            }

            /* 갈수없는 길이고, 벽을 뚫을수 있는 기회가 남아있다면 */
            if(arr[nr][nc] == '1' && wall) {
                mark[nr][nc][wall-1] = mark[r][c][wall]+1;
                q.push({{nr,nc}, wall-1});
            }
        }

    }
    return -1;
}


int main() {

    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        scanf("%s", &arr[i][1]);
    }

    cout << bfs();


}