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

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

BFS 응용

bfs로 바로 풀 수 있다.
다만 조건식이 조금 복잡하여 올리고자 한다.

구조체

typedef struct {
    int x;
    int y;
    int blk; ///벽을 뚫을 수 있는 횟수
} pos;

큐에 좌표값과 벽을 뚫었는지 안 뚫었는지의 여부를 저장해야하는데, pair을 두번 쓰기 싫어서 구조체를 만들어버렸다.

조건문

//갈인데 (0) 안 갔음
        if (x != (n - 1) && map[x + 1][y] == 0 && v[x + 1][y][blk] == 0) {
            v[x + 1][y][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x + 1;
            temp.y = y;
            temp.blk = blk;
            q.push(temp);
        }
        //벽인데 (1) 아직 안 뚫었음
        if (x != (n - 1) && map[x + 1][y] == 1 && blk == 1) {
            v[x + 1][y][blk - 1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x + 1;
            temp.y = y;
            temp.blk = blk - 1;
            q.push(temp);
        }

두 조건문이 다름을 알아야한다.

• 길이 0 일때
  v[x + 1][y][blk] = v[x][y][blk] + 1;
• 길이 1 일때 (벽)
  v[x + 1][y][blk - 1] = v[x][y][blk] + 1;

적고보니 이게끝이다. 상당히 쉬운데 귀찮은 문제였다.
오랜만에 백준 푼 김에 업로드 한다.

#include <iostream>
#include <queue>
#include <stdio.h>

using namespace std;

typedef struct {
    int x;
    int y;
    int blk; ///벽을 뚫을 수 있는 횟수
} pos;

queue<pos> q;

int n, m,
    map[1005][1005] = {0,},v[1005][1005][2] = {0,};

int bfs() {
    pos p;
    p.x = 0;
    p.y = 0;
    p.blk = 1;
    v[0][0][1]=1;
    q.push(p);

    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int blk = q.front().blk;
        q.pop();
//        cout<<x<<" "<<y<<" "<<blk<<"\n";

        if (x == n -1 && y == m -1)
            return v[x][y][blk];

        //갈인데 (0) 안 갔음
        if (x != (n - 1) && map[x + 1][y] == 0 && v[x + 1][y][blk] == 0) {
            v[x + 1][y][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x + 1;
            temp.y = y;
            temp.blk = blk;
            q.push(temp);
        }
        //벽인데 (1) 아직 안 뚫었음
        if (x != (n - 1) && map[x + 1][y] == 1 && blk == 1) {
            v[x + 1][y][blk - 1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x + 1;
            temp.y = y;
            temp.blk = blk - 1;
            q.push(temp);
        }

        // 2
        if (x != 0 && map[x - 1][y] == 0 && v[x - 1][y][blk] == 0) {
            v[x - 1][y][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x - 1;
            temp.y = y;
            temp.blk = blk;
            q.push(temp);
        }
        if (x != 0 && map[x - 1][y] == 1 && blk == 1) {
            v[x - 1][y][blk-1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x - 1;
            temp.y = y;
            temp.blk = blk - 1;
            q.push(temp);
        }

        // 3
        if (y != (m - 1) && map[x][y + 1] == 0 && v[x][y + 1][blk] == 0) {
            v[x][y + 1][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x;
            temp.y = y + 1;
            temp.blk = blk;
            q.push(temp);
        }
        if (y != (m - 1) && map[x][y + 1] == 1 && blk == 1) {
            v[x][y + 1][blk -1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x;
            temp.y = y + 1;
            temp.blk = blk -1;
            q.push(temp);
        }

        // 4
        if (y != 0 && map[x][y - 1] == 0 && v[x][y - 1][blk] == 0) {
            v[x][y - 1][blk] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x;
            temp.y = y - 1;
            temp.blk = blk;
            q.push(temp);
        }
        if (y != 0 && map[x][y - 1] == 1 && blk == 1) {
            v[x][y - 1][blk-1] = v[x][y][blk] + 1;
            pos temp;
            temp.x = x;
            temp.y = y - 1;
            temp.blk = blk -1;
            q.push(temp);
        }
    }
    return -1;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &map[i][j]);
        }
    }

    cout<<bfs();
    
    return 0;
}