백준 2206번: 벽 부수고 이동하기 (Python, C++)

접근

재채점 후 시간초과 되어 실패 뜬 문제를 C++로 다시 풀면서 Python 코드도 다시 확인하였다.

지금 확인해보니 왜 그때는 그렇게 풀었는지 모르겠는데 deque 대신에 그냥 리스트를 쓰고 popleft 대신에 pop(0)을 썼었다. 이 부분에서 시간이 초과된 것 같았다. 이 부분만 고쳐주니 시간 안에 들어왔고, 또 풀이 방법이 틀린 방법은 아니어서 그대로 두기로 했다.

---

최단 경로를 따라가는 BFS 알고리즘의 특성을 이용한 미로찾기와 비슷하지만, 벽 부수기라는 새로운 요소가 추가된 문제였다. 미로찾기 문제와 비슷하게 visited를 만들되, 각 칸이 요소를 2개씩 가진 3차원 배열을 만들어주었다.

visited[x][y][w] 에서 w가 0이라면 벽을 한번 뚫은 상태이고, 1이라면 아직 벽을 한번 뚫을 수 있는 상태를 나타닌다.

BFS 알고리즘을 순환하면서, 벽을 뚫을 수 있는 상태이고, 벽을 만난다면 벽을 뚫어주고 + 1을 해준다. 아직 방문하지 않았고 벽이 아니라면 + 1을 해준다.

BFS 알고리즘 참고문제 : 2021.04.11 - [코딩/백준 (Python)] - 백준 2178번: 미로 탐색 (Python)

백준 2178번: 미로 탐색 (Python)

코드

#include <iostream>
#include <queue>

using namespace std;

#define endl '\n'
#define MAX_N 1001
#define INF 987654321

struct INFO {
    int r;
    int c;
    int cnt;
};

int N, M;
char MAP[MAX_N][MAX_N];
int visited[MAX_N][MAX_N][2];

int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};

bool OutMap(int r, int c) {
    return (r < 0 || N <= r || c < 0 || M <= c);
}

int bfs() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            visited[i][j][0] = INF;
            visited[i][j][1] = INF;
        }
    }
    queue<INFO> Q;
    Q.push({0, 0, 0});
    visited[0][0][0] = 1;
    while (!Q.empty()) {
        int r = Q.front().r;
        int c = Q.front().c;
        int cnt = Q.front().cnt;
        Q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (OutMap(nr, nc)) continue;
            if (MAP[nr][nc] == '0' && visited[r][c][cnt] + 1 < visited[nr][nc][cnt]) {
                visited[nr][nc][cnt] = visited[r][c][cnt] + 1;
                Q.push({nr, nc, cnt});
            } else if (MAP[nr][nc] == '1' && visited[r][c][cnt] + 1 < visited[nr][nc][cnt + 1] && cnt < 1) {
                visited[nr][nc][cnt + 1] = visited[r][c][cnt] + 1;
                Q.push({nr, nc, cnt + 1});
            }
        }
    }
    int min = INF;
    for (int i = 0; i < 2; i++) {
        if (visited[N - 1][M - 1][i] < min) {
            min = visited[N - 1][M - 1][i];
        }
    }
    if (min == INF) {
        return -1;
    } else {
        return min;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
    cout << bfs() << endl;

    return 0;
}

import sys

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def bfs():
    q = []
    q.append([0, 0, 1])
    visit = [[[0] * 2 for _ in range(m)] for __ in range(n)]
    visit[0][0][1] = 1
    while q:
        x, y, w = q.pop(0)
        if x == n - 1 and y == m - 1:
            return visit[x][y][w]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if location[nx][ny] == 1 and w == 1:
                    visit[nx][ny][0] = visit[x][y][1] + 1
                    q.append([nx, ny, 0])
                elif location[nx][ny] == 0 and visit[nx][ny][w] == 0:
                    visit[nx][ny][w] = visit[x][y][w] + 1
                    q.append([nx, ny, w])
    return -1


n, m = map(int, sys.stdin.readline().split())
location = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
print(bfs())

더 생각해 볼 것?

BFS 알고리즘 문제인 것을 알고있어도 벽을 뚫는다는 것을 표시하기 위한 방법을 찾는데 굉장히 오래걸리고 힘들었던 문제였다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!