[C++] 백준 2206 - 벽 부수고 이동하기(BFS)

0. [c++] 백준

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

1. 풀이

메모이제이션과 BFS방식을 섞어서 문제를 풀어보았다.

visited는 x,y의 위치 이외에 추가적으로 벽을 부수었는가의 여부를 저장해주었다.

반복문에서 깔끔하게 정리하기 위해 큐에 모든 경우를 넣은 이후, pop을 해주면서 방문했는지를 체크해주었다.

한번 visited[x][y] = true가 된 이후 다시 등장한다면, count만 더 커진 경우이므로 경로 체크에서 제외시켜주는 방식으로 구현이 되어있다.

벽이 막힌 경우라면 무조건 벽을 뚫고 이동이 가능하다면 이동을 우선적으로 하도록 설계하였다.

이런 방식으로 상하좌우 이동을 하고 그 이동을 qu 에 저장해주었고, N,M의 위치에 도달하면 그때 count를 출력해주었다.

2. 소스코드

#include<iostream>
#include<string>
#include<queue>
 
using namespace std;
 
int N, M;
//arr[y][x];
int arr[1001][1001];
//qu.first.first = 현재 x, qu.first.second = 현재 y
//qu.second.first = 벽을 부수었는가? , qu.second.second = 이동횟수
queue<pair<pair<int, int>, pair<int, int> > > qu;
//visited[y][x][k] = y,x 위치를 방문하였는가, k는 벽을 부수었는지 여부
bool visited[1001][1001][2];
 
int bfs() {
    while (!qu.empty()) {
        pair<int, int> here = qu.front().first;
        int y = here.first;
        int x = here.second;
        int k = qu.front().second.first;
        int count = qu.front().second.second;
        qu.pop();
 
        if (visited[y][x][k])
            continue;
 
        visited[y][x][k] = true;
 
        if (y == N - 1 && x == M - 1)
            return count + 1;
 
        //상하좌우로 이동
        //상
        if (y > 0) {
            if (arr[y - 1][x] == 0) {
                qu.push({ {y - 1,x}, {k, count + 1} });
            }
            else if (k == 0) {
                qu.push({ {y - 1,x}, {1, count + 1} });
            }
        }
        //하
        if (y < N - 1) {
            if (arr[y + 1][x] == 0) {
                qu.push({ {y + 1,x}, {k, count + 1} });
            }
            else if (k == 0) {
                qu.push({ {y + 1,x}, {1, count + 1} });
            }
        }
        //좌
        if (x > 0) {
            if (arr[y][x - 1] == 0) {
                qu.push({ {y,x - 1}, {k, count + 1} });
            }
            else if (k == 0) {
                qu.push({ {y,x - 1}, {1, count + 1} });
            }
        }
        //우
        if (x < M - 1) {
            if (arr[y][x + 1] == 0) {
                qu.push({ {y,x + 1}, {k, count + 1} });
            }
            else if (k == 0) {
                qu.push({ {y,x + 1}, {1, count + 1} });
            }
        }
    }
 
    return -1;
}
 
int main() {
    string s;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> s;
        for (int j = 0; j < M; j++) {
            arr[i][j] = s[j] - 48;
        }
    }
 
    qu.push({ {0,0}, {0,0} });
 
    cout << bfs() << endl;
 
    return 0;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!