문제 : boj 2206

풀이

  • 벽이 뚫리지 않았을 때(w=0), 벽이 뚫렸을 때(w=1)를 확인할 수 있도록 배열 dist를 3차원 배열로 만들고, 거리를 담는다.
  • 새로 탐색하는 좌표를 q에 담고, 하나씩 꺼내면서 이전 좌표값에 1씩 더한다. 이 값을 dist에 넣는다.

C++

#include <iostream>
#include <queue>
using namespace std;

struct map
{
    int x, y, w;
};


int N,M;
int zido[1001][1001];
int dist[2][1001][1001];
int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1};

int bfs(){
    map now;
    int xtmp, ytmp;
    queue<map> q;
    q.push({0,0,0});
    dist[0][0][0] = 1;

    while (!q.empty()){
        now = q.front(); q.pop();
        if (now.x == N-1 && now.y == M-1) return dist[now.w][now.x][now.y];
        for (int i(0); i < 4; i++){
            xtmp = now.x + dx[i];
            ytmp = now.y + dy[i];
            if (xtmp >= 0 && xtmp < N && ytmp >=0 && ytmp < M){
                if (!zido[xtmp][ytmp] && !dist[now.w][xtmp][ytmp]){
                    dist[now.w][xtmp][ytmp] = dist[now.w][now.x][now.y] + 1;
                    q.push({xtmp, ytmp, now.w});
                }
                else if(zido[xtmp][ytmp] && !now.w && !dist[now.w][xtmp][ytmp]){
                    dist[1][xtmp][ytmp] = dist[now.w][now.x][now.y] + 1;
                    q.push({xtmp, ytmp, 1});
                }
            }
        }
    }
    return -1;
}

int main(){
    char tmp;
    cin >> N >> M;

    for(int n(0); n < N; n++){
        for(int m(0); m < M; m++){
            cin >> tmp;
            zido[n][m] = tmp - '0';
            dist[0][n][m] = 0;
            dist[1][n][m] = 0;
        }
    }

    cout << bfs();
    return 0;
}

python

import sys
import queue
input = lambda: sys.stdin.readline().rstrip()

def bfs():
    dist = [[[0,0] for _ in range(M)] for _ in range(N)]
    q = queue.Queue()
    q.put((0,0,0))
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    dist[0][0][0] = 1
    while not q.empty():
        x, y, w = q.get()
        print(x, y, w)
        if x == N-1 and y == M-1:
            return dist[x][y][w]
        for i in range(4):
            xtmp = x+dx[i]
            ytmp = y+dy[i]
            if 0<= xtmp < N and 0<= ytmp < M:
                if zido[xtmp][ytmp] == '0' and dist[xtmp][ytmp][w] == 0:
                    dist[xtmp][ytmp][w] = dist[x][y][w] + 1
                    q.put((xtmp, ytmp, w))
                elif zido[xtmp][ytmp] == '1' and w == 0 and dist[xtmp][ytmp][w] == 0:
                    dist[xtmp][ytmp][1] = dist[x][y][w] + 1
                    q.put((xtmp, ytmp, 1))
    return -1

N, M = map(int, input().split())
zido = [list(input()) for _ in range(N)]
print(bfs())

c++와 같은 방법으로 python 코드를 작성하였지만 python은 시간초과