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

문제: 2206번: 벽 부수고 이동하기

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture · GitHub

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>

using namespace std;

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    vector<string> board(n);
    vector<vector<int>> visit1(n);
    vector<vector<int>> visit2(n);
    vector<vector<int>> dists1(n);
    vector<vector<int>> dists2(n);
    for (int i = 0; i < n; i++) {
        visit1[i] = vector<int>(m);
        visit2[i] = vector<int>(m);
        dists1[i] = vector<int>(m);
        dists2[i] = vector<int>(m);

        cin >> board[i];
    }


    // 시작 지점에서 BFS
    queue<pair<int, int>> nexts1;
    nexts1.push(make_pair(0, 0));
    visit1[0][0] = 1;
    dists1[0][0] = 1;
    while (!nexts1.empty()) {
        pair<int, int> cur = nexts1.front();
        nexts1.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i]; // 행
            int ny = cur.second + dy[i]; // 열

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (visit1[nx][ny] == 1) continue;

            dists1[nx][ny] = dists1[cur.first][cur.second] + 1;
            visit1[nx][ny] = 1; // 방문 표시
            if (board[nx][ny] == '1') continue;
            nexts1.push(make_pair(nx, ny));
        }
    }

    // 종료 지점에서 BFS
    queue<pair<int, int>> nexts2;
    nexts2.push(make_pair(n - 1, m - 1));
    visit2[n - 1][m - 1] = 1;
    dists2[n - 1][m - 1] = 1;
    while (!nexts2.empty()) {
        pair<int, int> cur = nexts2.front();
        nexts2.pop();

        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i]; // 행
            int ny = cur.second + dy[i]; // 열

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (visit2[nx][ny] == 1) continue;

            dists2[nx][ny] = dists2[cur.first][cur.second] + 1;
            visit2[nx][ny] = 1; // 방문 표시
            if (board[nx][ny] == '1') continue;
            nexts2.push(make_pair(nx, ny));
        }
    }

    int min = INT_MAX;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dists1[i][j] == 0 || dists2[i][j] == 0) continue;

            int sum = dists1[i][j] + dists2[i][j];
            if (sum < min)
                min = sum;
        }
    }
    if (min == INT_MAX)
        cout << -1 << "\n";
    else
        cout << min - 1 << "\n";
    

    return 0;
}

 

시작점과 도착점에서 각각 BFS 를 돌리면 되는 문제였다. 만약 벽을 만난다면 방문 표시랑 거리 설정만 해주고 queue 에는 넣지 않고 빠져나오도록 했다. 즉, 벽을 만나면 그 방향으로는 더이상 이동하지 않는 것이다.

 

마지막에 이중포문을 돌면서 거리 두개를 더한 후 최소값을 구해서 -1 해서 출력해주면 된다. 그런데 만약 거리 중 둘 중 하나라도 0이면 최소값에 반영하지 않도록 했다.

 

도착점에 도달할 수 없는 것을 확인하는 조건은 min 값이 초기에 설정해둔 값에서 바뀌지 않았는지를 보는 것이다.