17070 백준 파이썬

어떤 문제든, 문제를 잘 읽는게 제일 중요하다.

문제를 제대로 안읽어서 BFS로 접근했던 문제

가로, 세로 상황에서 대각선으로 꺾는것을 기준점의 이동 없이 옮기는 줄 알고 여러가지 가능한 경우 중 최단거리의 갯수를 찾는 문제인 줄 알았다.

 

하지만 이건 DFS이다. 다중 조건 미로찾기라고 생각하면 될 것 같다.

기준점과 움직이는 점을 분리해서 푼 코드이다.

import sys
input=sys.stdin.readline
def bfs(stdx,stdy,mvx,mvy):
    if mvx==n-1 and mvy==n-1:
        global c
        c+=1
        return
    #가로
    if stdx==mvx and stdy==mvy-1:
        if mvy+1<n and m[mvx][mvy+1]==0:
            bfs(stdx,stdy+1,mvx,mvy+1)
        if mvx+1<n and mvy+1<n and m[mvx+1][mvy]==0 and m[mvx+1][mvy+1]==0 and m[mvx][mvy+1]==0:
            bfs(stdx,stdy+1,mvx+1,mvy+1)
    #세로
    elif stdx==mvx-1 and stdy==mvy:
        if mvx+1<n and m[mvx+1][mvy]==0:
            bfs(stdx+1,stdy,mvx+1,mvy)
        if mvx+1<n and mvy+1<n and m[mvx][mvy+1]==0 and m[mvx+1][mvy]==0 and m[mvx+1][mvy+1]==0:
            bfs(stdx+1,stdy,mvx+1,mvy+1)
    #대각
    elif stdx==mvx-1 and stdy==mvy-1:
        if mvy+1<n and m[mvx][mvy+1]==0:
            bfs(stdx+1,stdy+1,mvx,mvy+1)

        if mvx+1<n and m[mvx+1][mvy]==0:
            bfs(stdx+1,stdy+1,mvx+1,mvy)
        if mvx+1<n and mvy+1<n and m[mvx+1][mvy]==0 and m[mvx+1][mvy+1]==0 and m[mvx][mvy+1]==0:
            bfs(stdx+1,stdy+1,mvx+1,mvy+1)

n=int(input())
m=[]
for _ in range(n):
    m.append(list(map(int,input().split())))
c=0
bfs(0,0,0,1)
print(c)

배열에 접근하는 속도가 느려서인지 시간초과가 났다.

 

그 다음에는 대각, 가로, 세로를 상태로 분류하여 풀었다.

 

가로인 경우 그 다음이 가로인 경우와 대각선인 경우로 갈린다

세로인 경우 그 다음이 세로인 경우와 대각선인 경우로 갈린다.

대각선인 경우 그 다음이 가로인 경우와 세로인 경우, 그리고 대각선인 경우로 갈린다.

import sys
input=sys.stdin.readline
def dfs(status,x,y):
    if x==n-1 and y==n-1:
        global c
        c+=1
        return
    if status==0:
        if y+1<n and m[x][y+1]==0:
            dfs(0,x,y+1)
        if x+1<n and y+1<n and m[x+1][y]==0 and m[x+1][y+1]==0 and m[x][y+1]==0:
            dfs(2,x+1,y+1)
    elif status==1:
        if x+1<n and m[x+1][y]==0:
            dfs(1,x+1,y)
        if x+1<n and y+1<n and m[x+1][y]==0 and m[x][y+1]==0 and m[x+1][y+1]==0:
            dfs(2,x+1,y+1)
    elif status==2:
        if y+1<n and m[x][y+1]==0:
            dfs(0,x,y+1)
        if x+1<n and m[x+1][y]==0:
            dfs(1,x+1,y)
        if x+1<n and y+1<n and m[x+1][y]==0 and m[x+1][y+1]==0 and m[x][y+1]==0:
            dfs(2,x+1,y+1)

n=int(input())
m=[]
for _ in range(n):
    m.append(list(map(int,input().split())))
c=0
dfs(0,0,1)
print(c)