[Algorithm] BOJ 2206 벽 부수고 이동하기

Juppi·2023년 1월 25일
0

BFS & DFS

목록 보기
1/4

문제 링크

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

문제 풀이

출발지에서 도착지점까지 최단거리를 찾는 전형적인 BFS 문제 풀이이다.
다만, 갈 수 없는 길을 하나 부수고 갈 수 있다는 점을 처리 하기 위해
visited 차원을 하나 추가해서 길을 뚫은 상태인지, 아닌지를 체크하였다.

다음 목적지 map[nx][ny] 갈 수 있는 상태라면, 현재 뚫은 상태를 그대로 가지고 간다.
만약 다음 목적지가 갈 수 없는 상태라면, 현재 뚫은 상태에 따라 달라진다.

  • 이미 한번 뚫었다면 그 길은 갈 수 없다
  • 뚫을 수 있으면 간다 ➡️ visited[nx][ny] [1-curK] = visited[x][y][curK]

현재 상태는 0 아니면 1이기 때문에 1-curK 연산으로 교체해준다.
상태 변수 이름이 curK 인 이유는, 벽 부수고 이동하기 2를 풀다가 건너왔기 때문,,

처음엔 경로의 길이를 queue에 넣어서 풀었지만, 메모리 초과가 났다.
다시 풀어보니 queue에 경로의 길이를 넣어서 메모리 초과가 난건 아니지만,
이미 잡혀있는 visited 메모리를 활용하는게 더 효율적일것같아서 visitied에 경로의 길이를 저장하였다.

코드

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAX = 1000;

int n, m;
int map[MAX][MAX];
int visited[MAX][MAX][2];

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

int bfs(int sx, int sy, int k) {
    // x, y, k
    queue<vector<int>> q;
    q.push({sx, sy, 0});

    while(!q.empty()) {
        int x = q.front()[0];
        int y = q.front()[1];
        int curK = q.front()[2];
        q.pop();

        if (x == n-1 && y == m-1)
            return visited[x][y][curK] + 1;

        for (int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;

            if (visited[nx][ny][curK] == 0) {
                // 갈수 있는 길, 뚫은 상태 or 안뚫은상태 쭉감
                if (map[nx][ny] == 0) {
                    q.push({nx, ny, curK});
                    visited[nx][ny][curK] = visited[x][y][curK] + 1;
                } else if (curK == 0) {             // 못가는데 뚫을 수 있으면
                    q.push({nx, ny, 1 - curK});
                    visited[nx][ny][1-curK] = visited[x][y][curK] + 1;
                }
            }
        }
    }
    return -1;
}

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

    cin >> n >> m;
    string rows;
    for (int i=0; i<n; i++) {
        cin >> rows;
        for (int j=0; j<m; j++) {
            map[i][j] = rows[j] - 48;
        }
    }
    memset(visited, 0, sizeof(visited));

    cout << bfs(0, 0, 0);
    return 0;
}
profile
잠자면서 돈버는 그날까지

0개의 댓글