17070:파이프 옮기기 [백준 문제풀이][Python][CLASS 4]

문제:https://www.acmicpc.net/problem/17070

난이도: 골드5

파이프를 (1,1),(1,2) 부터 시작하여 반대쪽 끝점까지 옮기면 되는 문제이다.

아이디어1

우선 보자마자 bfs를 떠올렸고, 탐색을 할때 x,y 말고도 방향 r을 넣어서 케이스를 나눴고, 각 방향마다 요구하는 빈칸이 다르기 때문에 이를 if문을 통해 걸러 리스트에 넣어준다.

시도1

from collections import deque
n=int(input())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
cnt=0
d=deque([(0,1,0)])#세로,가로,방향
while len(d)!=0:
    p,q,r = d.popleft()
    if(p==n-1 and q==n-1):
        cnt+=1
        continue
    x =q<n-1#가로
    y =p<n-1#세로
    if((r==0 or r==2) and x):#가로
        if(l[p][q+1]==0):d.append((p,q+1,0))
    if((r==1 or r==2) and y):#세로
        if(l[p+1][q]==0):d.append((p+1,q,1))
    if(x and y):#대각선
        if(l[p+1][q+1]==0 and l[p+1][q]==0 and l[p][q+1]==0):d.append((p+1,q+1,2))
print(cnt)

실패한 이유

첫 시도는 70%에서 시간초과. 이후 빠른 입출력을 적용해봤지만 80%에서 여전히 시간초과가 일어났다. 잠시 생각을 하다가... 혹시? 싶어서 bfs -> dfs(append -> appendleft)로 바꿔 코드를 넣어봤더니...

정답 코드

from collections import deque
import sys
input= sys.stdin.readline
n=int(input())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
cnt=0
d=deque([(0,1,0)])#세로,가로,방향
while len(d)!=0:
    p,q,r = d.popleft()
    if(p==n-1 and q==n-1):
        cnt+=1
        continue
    x =q<n-1#가로
    y =p<n-1#세로
    if((r==0 or r==2) and x):#가로
        if(l[p][q+1]==0):d.appendleft((p,q+1,0))
    if((r==1 or r==2) and y):#세로
        if(l[p+1][q]==0):d.appendleft((p+1,q,1))
    if(x and y):
        if(l[p+1][q+1]==0 and l[p+1][q]==0 and l[p][q+1]==0):d.appendleft((p+1,q+1,2))
print(cnt)

놀랍게도 맞았다... dfs와 bfs가 큰 차이는 없어서 이유는 잘 모르겠다만, 추측을 해보자면, 일반 탐색들과는 달리 다음 칸으로 갈때 모양을 정하며 가기 때문에 3가지의 케이스가 나누어져, bfs로 가게 될 경우, 케이스가 너무 많아져서 도달하기도 전에 시간초과가 나는게 아닐까 싶다... 적재적소에 사용해야 된다는건 알고 있었지만 이렇게 미묘한 차이로 갈리는 경우는 처음이었다.