문제 : 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())