2206 백준 파이썬

오랜만의 bfs, dfs

항상 그렇듯, dfs는 시간초과다.

 

처음 짠 코드

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
M=[]
for _ in range(n):
    M.append(list(str(input())))

def bfs(x,y,Mcopy):
    vismap=[[0 for x in range(m)] for y in range(n)]
    q=deque()
    cnt=1
    q.append([x,y,cnt])
    while q:
        x,y,cnt=q.popleft()
        a=[-1,1,0,0]
        b=[0,0,-1,1]
        for t in range(4):
            X=x+a[t]
            Y=y+b[t]
            if 0<=X<n and 0<=Y<m:
                if Mcopy[X][Y]=='0' and vismap[X][Y]!=1:
                    q.append([X,Y,cnt+1])
                    vismap[X][Y]=1
    if vismap[-1][-1]!=1:
        return -1
    else:
        return cnt
def dfs(M):
    ans=[]
    Mcopy=M[:]
    ans.append(bfs(0,0,Mcopy))
    for x in range(n):
        for y in range(m):
            if M[x][y]=='1':
                Mcopy[x][y]='0'
                ans.append(bfs(0,0,Mcopy))
                Mcopy[x][y]='1'
    return ans
print(max(dfs(M)))

한번에 짜서 와, 좀 늘었을지도? 하고있었는데 역시나 어림도 없다.

 

이건 3차원 배열을 사용한다. 2차원도 이제야 감이 잡히는데 3차원을 처음 써보려니 머리가 너무 어지러웠다.

벽을 뚫었을 경우 3차원 배열을 이동시켜, 벽을 한번 뚫었다는 것을 체크해준다. z=0일때만 벽을 뚫을 수 있으므로, 단 한번 뚫을 수 있다. 이후부터는 bfs가 vismap을 갱신하며 최소거리가 마지막 값에 입력되게 된다.

 

엄청시간을 많이 썼다. 난 아직 멀었다.

 

정답 코드

from collections import deque
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
M=[]
for _ in range(n):
    M.append(list(str(input())))
vismap=[[[-1]*2 for x in range(m)] for y in range(n)]
def bfs():
    vismap[0][0][0]=1
    q=deque()
    q.append([0,0,0])
    while q:
        x,y,z=q.popleft()
        a=[-1,1,0,0]
        b=[0,0,-1,1]
        for t in range(4):
            X=x+a[t]
            Y=y+b[t]
            if 0<=X<n and 0<=Y<m:
                if M[X][Y]=='0' and vismap[X][Y][z]==-1:
                    vismap[X][Y][z]=vismap[x][y][z]+1
                    q.append([X,Y,z])
                elif M[X][Y]=='1'and vismap[X][Y][z]==-1 and z==0:
                    vismap[X][Y][1]=vismap[x][y][z]+1
                    q.append([X,Y,1])
bfs()
wallx=vismap[-1][-1][0]
wall=vismap[-1][-1][1]
if wallx==-1 and wall!=-1:
    print(wall)
elif wallx!=-1 and wall==-1:
    print(wallx)
else:
    print(min(wall,wallx))