[Python]DFS와BFS 백준 2206

   문제

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

이전 미로찾기와 다른점은 벽을 한번 뚫었을때의 경우도 생각해준다.

벽을 뚫지 않았을때와 한번 뚫었을때를 따로 저장해 준다.

이전 미로찾기 코드에서 벽에 대한 코드만 추가해보자

import sys
from collections import deque
 
 
 
def find_maze(start_row,start_colume,N,M):#bfs를 통해 찾기
    q=deque()
    q.append([start_row,start_colume,0])
    wallcheck[start_row][start_colume][0]=1
    dx=[1,-1,0,0]
    dy=[0,0,-1,1]
    while q:
        [x, y, z] = q.popleft()
        for i in range(4):#네군데 큐담기
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M:#미로를 벗어나지않고
                   if matrix[nx][ny]==0 and wallcheck[nx][ny][z]==0:#길이 뚤려있고 한번도 안갓다면
                    q.append([nx,ny,z])
                    wallcheck[nx][ny][z]+=wallcheck[x][y][z]+1#해당노드까지의 칸수
                elif z==0 and matrix[nx][ny]==1:#길이 막혀있고 한번도 뚫은적이 없다면
                    q.append([nx,ny,1])
                    wallcheck[nx][ny][1]+=wallcheck[x][y][z]+1
 
 
    if wallcheck[N-1][M-1][0]==0 and wallcheck[N-1][M-1][1]==0:#둘다 도착하지못했다면
        return -1
    elif wallcheck[N-1][M-1][0]==0:#벽을 한번도 안뚫고 도착했을때
        return wallcheck[N-1][M-1][1]
    elif wallcheck[N-1][M-1][1]==0:#벽을 안뚫고는 도착할수 없을때
        return wallcheck[N-1][M-1][0]
    else:#둘다 도착할수 있을때
        return min(wallcheck[N-1][M-1][0],wallcheck[N-1][M-1][1])
 
 
N,M=map(int,sys.stdin.readline().split())
 
matrix=[]
 
for i in range(N):
    str=sys.stdin.readline()
    tmp=[]
    for i in range(M):
        tmp.append(int(str[i]))
    matrix.append(tmp)
 
wallcheck=[[[0,0] for _ in range(M)] for _ in range(N)]
 
print(find_maze(0,0,N,M))

먼가 최적화 할수 있을거 같은데 생각대로 잘되지는 않았다.

벽을 뚫었을때 이동했던곳을 다시 돌아가는 부분이 조금 마음에 들지않는다.

답을 찾는부분에서도 모두찾은뒤 답을 출력하기보단 중간에 출력할수 있었으면 좋겟다.

벽을 뚫었을때 다시돌아가는부분은 언제 뚫을지 알 수 없기때문에 구현하기 어려울거

같다.답을 찾는부분은 코드만 간결하게 바꾸었다.큐를 돌다가 끝에 도달한값이 나온다

면 바로 출력할수 있게 만들었다.

import sys
from collections import deque
 
def find_maze(start_row,start_colume,N,M):#bfs를 통해 찾기
    q=deque()
    q.append([start_row,start_colume,0])
    wallcheck[start_row][start_colume][0]=1
    dx=[1,-1,0,0]
    dy=[0,0,-1,1]
    while q:
        [x, y, z] = q.popleft()
        if x==N-1 and y==M-1:#끝에 도달했다면 출력
            return wallcheck[x][y][z]
        for i in range(4):#네군데 큐담기
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<N and 0<=ny<M:#미로를 벗어나지않고
                if matrix[nx][ny]==0 and wallcheck[nx][ny][z]==0:#길이 뚤려있고 한번도 안갓다면
                    q.append([nx,ny,z])
                    wallcheck[nx][ny][z]+=wallcheck[x][y][z]+1#해당노드까지의 칸수
                elif z==0 and matrix[nx][ny]==1:#길이 막혀있고 한번도 뚫은적이 없다면
                    q.append([nx,ny,1])#뚫어주고 뚫었을때의 배열로 넘어간다.
                    wallcheck[nx][ny][1]+=wallcheck[x][y][z]+1
    return -1
 
 
N,M=map(int,sys.stdin.readline().split())
 
matrix=[]
 
for i in range(N):
    str=sys.stdin.readline()
    tmp=[]
    for i in range(M):
        tmp.append(int(str[i]))
    matrix.append(tmp)
 
wallcheck=[[[0,0] for _ in range(M)] for _ in range(N)]
 
 
print(find_maze(0,0,N,M))