[백준]2206 벽 부수고 이동하기

1. 시간

queue 모듈과 deque모듈을 이용하여 풀었을 때 queue모듈은 시간초과가 났고 deque모듈은 통과되였다.

기본적으로 두 모듈 모두 알고리즘은 똑같다.

 

2. 소스코드

(1) queue(시간초과)

queue로 while문을 돌리기 위해선 매 반복마다 while(not q.empty()) 연산을 수행해야 하는데, 이것때문에 시간이 오래 걸린것으로 보인다

import queue

N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append(list(map(int,list(input()))))

q=queue.Queue()
q.put((0,0,0))
cL=[[[0,0] for i in range(M)] for j in range(N)]

cL[0][0][0]=1
dr=[0,0,1,-1]
dc=[1,-1,0,0]


while(not q.empty()): # 시간오래걸림
    r,c,h=q.get()
    for k in range(4):
        tempR=r+dr[k]
        tempC=c+dc[k]
        if 0<=tempR<N and 0<=tempC<M:
            if L[tempR][tempC]==0 and cL[tempR][tempC][h]==0:
                cL[tempR][tempC][h]=cL[r][c][h]+1
                q.put((tempR,tempC,h))
            elif L[tempR][tempC]==1 and h==0 and cL[tempR][tempC][1]==0:
                cL[tempR][tempC][1]=cL[r][c][0]+1
                q.put((tempR,tempC,1))

if cL[N-1][M-1][0]==0 and cL[N-1][M-1][1]==0:
    print(-1)
elif cL[N-1][M-1][0]==0:
    print(cL[N-1][M-1][1])
elif cL[N-1][M-1][1]==0:
    print(cL[N-1][M-1][0])
else:
    print(min(cL[N-1][M-1][0],cL[N-1][M-1][1]))

 

(2) deque 끝지점확인 조건문추가(6196ms)

deque으로 구현했다. 이때 r과 c가 처음으로 끝에 도달했을 때가 답이 되는 경우이다. 따라서 이때 ans의 값을 바꿔주고, 종료하여 ans을 출력하면 답이 된다. 하지만 이 방법은 매 반복마다 r과 c의 값을 탐색해줘야 하기 때문에 시간이 더 오래 걸린다.

break를 할 수 있기 때문에 이후 탐색을 하지 않다도 된다는 장점이 있지만, bfs 특성상 끝지점에 닿았다면 이제 반복이 얼마 남지 않았을 것이기 때문에 break문으로 얻는 시간효율은 많지 않을것으로 예상된다.

from collections import deque

N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append(list(map(int,list(input()))))

q=deque()
q.append((0,0,0))
cL=[[[0,0] for i in range(M)] for j in range(N)]

cL[0][0][0]=1
dr=[0,0,1,-1]
dc=[1,-1,0,0]

ans=-1

while(q):
    r,c,h=q.popleft()
    if r==N-1 and c==M-1:
        ans=cL[r][c][h]
        break
    for k in range(4):
        tempR=r+dr[k]
        tempC=c+dc[k]
        if 0<=tempR<N and 0<=tempC<M:
            if L[tempR][tempC]==0 and cL[tempR][tempC][h]==0:
                cL[tempR][tempC][h]=cL[r][c][h]+1
                q.append((tempR,tempC,h))
            elif L[tempR][tempC]==1 and h==0 and cL[tempR][tempC][1]==0:
                cL[tempR][tempC][1]=cL[r][c][0]+1
                q.append((tempR,tempC,1))


print(ans)

 

(3) deque, 조건문제거(6020ms)

while문 내에 조건문을 제거하고, while문밖에서 조건문을 이용하여 최종답을 출력한다.

from collections import deque

N,M=map(int,input().split())
L=[]
for i in range(N):
    L.append(list(map(int,list(input()))))

q=deque()
q.append((0,0,0))
cL=[[[0,0] for i in range(M)] for j in range(N)]

cL[0][0][0]=1
dr=[0,0,1,-1]
dc=[1,-1,0,0]


while(q):
    r,c,h=q.popleft()
    for k in range(4):
        tempR=r+dr[k]
        tempC=c+dc[k]
        if 0<=tempR<N and 0<=tempC<M:
            if L[tempR][tempC]==0 and cL[tempR][tempC][h]==0:
                cL[tempR][tempC][h]=cL[r][c][h]+1
                q.append((tempR,tempC,h))
            elif L[tempR][tempC]==1 and h==0 and cL[tempR][tempC][1]==0:
                cL[tempR][tempC][1]=cL[r][c][0]+1
                q.append((tempR,tempC,1))


if cL[N-1][M-1][0]==0 and cL[N-1][M-1][1]==0:
    print(-1)
elif cL[N-1][M-1][0]==0:
    print(cL[N-1][M-1][1])
elif cL[N-1][M-1][1]==0:
    print(cL[N-1][M-1][0])
else:
    print(min(cL[N-1][M-1][0],cL[N-1][M-1][1]))

 

* 그런데 3번 방식으로 했을때도 6252ms가 나올때도 있었다.. while문의 위치로 크게 시간의 영향을 받진 않는것으로 보인다...