BOJ 1707

me

문제

문제 자체는 이해하기 쉬웠다. 현재 배치에 따라서 갈 수 있는 곳이 정해져있는 것으로 이해했다.
그래서 현재 배치에 따라 갈 수 있는 방향을 딕셔너리로 저장해두고, 방향마다 체크해야할 부분도 따로 저장해두었다. n*n까지 가는 방법 가짓 수를 구하는 거니깐 전체 탐색을 통해 루트를 찾아야 한다. 그래서 dfs를 이용해야 겠다는 생각을 했다. stack을 이용하였고, 첫 번째는 [(0,0),(0,1),가로]로 두었다.
visit을 체크해야겠다는 생각에 루트를 문자열로 통째로 저장했다. <= 이게 시간 초과의 발단이었던 것 같다.

코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
spaces = [list(map(int,input().split())) for _ in range(N)]

if spaces[N-1][N-1]==1:
    print(0)
    sys.exit()
    
dir = {0:[0,2],1:[1,2],2:[0,1,2]}
check = {0:[(0,+1)],1:[(+1,0)],2:[(0,+1),(+1,0),(+1,+1)]}

q= deque([[0,(0,0),(0,1),"00"]])
cnt=0
routes = []
while q:
    cur_dir, start, end, route = q.popleft()
    if end[0]==N-1 and end[1]==N-1 and route not in routes:
        routes.append(route)
        cnt+=1
        continue
    for d in dir[cur_dir]:
        isOk = True
        for dx,dy in check[d]:
            nx = end[0]+dx
            ny = end[1]+dy
            if not(-1<nx<N and -1<ny<N):
                # 경계 밖이면
                isOk=False
                break
            if spaces[nx][ny]!=0:
                # 빈 칸이 아니면
                isOk=False
                break
        if isOk:
            q.append([d,end,(nx,ny), route+str(end[0])+str(end[1])])
print(cnt)

-> 시간 초과가 났다. 방문 체크하는 부분에서 시간을 많이 잡아먹는 것 같다. 아무래도 루트가 길 수록 또 루트가 많을 수록 체크하는 데 시간을 오래 잡아먹는다는 생각이 들었다. 매번 여기를 알면서도 저런 방식으로 체크를 하게 된다..

solution

dfs

from collections import deque
import sys
input = sys.stdin.readline
def dfs(x, y, direction):
    global count
    if x == n - 1 and y == n - 1: count += 1
    if direction == 0:
        if y + 1 < n and s[x][y + 1] == 0: dfs(x, y + 1, 0)
        if x + 1 < n and y + 1 < n:
            if s[x][y + 1] == 0 and s[x + 1][y + 1] == 0 and s[x + 1][y] == 0:
                dfs(x + 1, y + 1, 2)
    elif direction == 1:
        if x + 1 < n and s[x + 1][y] == 0: dfs(x + 1, y, 1)
        if x + 1 < n and y + 1 < n:
            if s[x][y + 1] == 0 and s[x + 1][y + 1] == 0 and s[x + 1][y] == 0:
                dfs(x + 1, y + 1, 2)
    elif direction == 2:
        if y + 1 < n and s[x][y + 1] == 0: dfs(x, y + 1, 0)
        if x + 1 < n and s[x + 1][y] == 0: dfs(x + 1, y, 1)
        if x + 1 < n and y + 1 < n:
            if s[x][y + 1] == 0 and s[x + 1][y + 1] == 0 and s[x + 1][y] == 0:
                dfs(x + 1, y + 1, 2)
n = int(input())
s = [list(map(int, input().split())) for i in range(n)]
count = 0
dfs(0, 1, 0)
print(count)

dfs로 되는 거 보니깐 확실히 체크하는 부분에서 시간을 잡아먹은 거 같다. 재귀를 이용해서 중복된 길이 없도록 체크할 수 있다..!근데 이걸로 돌려보니깐 이 친구도 시간초과가 났다..

리팩토링 코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())
spaces = [list(map(int,input().split())) for _ in range(N)]
if spaces[N-1][N-1]==1:
    print(0)
    sys.exit()
dir = {0:[0,2],1:[1,2],2:[0,1,2]}
check = {0:[(0,+1)],1:[(+1,0)],2:[(0,+1),(+1,0),(+1,+1)]}

cnt=0

def dfs(cur_dir,start,end):
    global cnt
    if end[0]==N-1 and end[1]==N-1 : # and route not in routes:
        cnt+=1
        return
    for d in dir[cur_dir]:
        isOk = True
        for dx,dy in check[d]:
            nx = end[0]+dx
            ny = end[1]+dy
            if not(-1<nx<N and -1<ny<N):
                # 경계 밖이면
                isOk=False
                break
            if spaces[nx][ny]!=0:
                # 빈 칸이 아니면
                isOk=False
                break
        if isOk:
            dfs(d,end,(nx,ny))

dfs(0,(0,0),(0,1))
print(cnt)

얘도 시간초과는 마찬가지이다..

다른 분의 dfs

출처

def dfs(pos):
    global cnt
    x, y, z = pos

    # n,n 도달
    if x == n - 1 and y == n - 1:
        cnt += 1
        return

    # 가로 세로 대각선의 경우 대각선 이동
    if x + 1 < n and y + 1 < n:
        if graph[x + 1][y + 1] == 0 and graph[x][y + 1] == 0 and graph[x + 1][y] == 0:
            dfs((x + 1, y + 1, 2))

    # 가로 대각선의 경우 가로 이동
    if z == 0 or z == 2:
        if y + 1 < n:
            if graph[x][y + 1] == 0:
                dfs((x, y + 1, 0))

    # 세로 대각선의 경우 세로 이동
    if z == 1 or z == 2:
        if x + 1 < n:
            if graph[x + 1][y] == 0:
                dfs((x + 1, y, 1))


n = int(input())
graph = [[] for _ in range(n)]
cnt = 0
# 그래프 정보 입력
for i in range(n):
    graph[i] = list(map(int, input().split()))

# x,y,현재방향
dfs((0, 1, 0))

print(cnt)

분기를 줄이니깐 통과한 것 같다. if문을 최대한 덜 써야 하는 것 같다.

dp

n = int(input())
graph = [[] for _ in range(n)]

# 0은 가로, 1은 세로, 2는 대각선
dp = [[[0] * n for _ in range(n)] for _ in range(3)]

# 그래프 정보 입력
for i in range(n):
    graph[i] = list(map(int, input().split()))

dp[0][0][1] = 1  # 첫 시작 위치

# dp를 위해서는 윗 행을 사용해야하므로 첫 행을 먼저 초기화
for i in range(2, n):
    if graph[0][i] == 0:
        dp[0][0][i] = dp[0][0][i - 1]

for r in range(1, n):
    for c in range(1, n):
        # 현재위치가 대각선인 경우
        if graph[r][c] == 0 and graph[r][c - 1] == 0 and graph[r - 1][c] == 0:
            dp[2][r][c] = dp[0][r - 1][c - 1] + dp[1][r - 1][c - 1] + dp[2][r - 1][c - 1]

        if graph[r][c] == 0:
            # 현재 위치가 가로인 경우
            dp[0][r][c] = dp[0][r][c - 1] + dp[2][r][c - 1]
            # 현재 위치가 세로인 경우
            dp[1][r][c] = dp[1][r - 1][c] + dp[2][r - 1][c]

print(sum(dp[i][n - 1][n - 1] for i in range(3)))

여태 올 수 있었던 경로를 각 가로, 세로, 대각선 그리드에 저장시켜준다. 각 위치까지 올 수 있는 경로를 저장하는 것이다.!!!

각각의 형태(가로, 세로, 대각선)으로 올 수 있는 경우의 수를 구해줍니다.
가로로 올 수 있는 경우의 수 -> (가로에서 가로로 가능, 대각선에서 가로로 가능) 이 경우의 수들의 합
세로로 올 수 있는 경우의 수 -> (세로에서 세로로 가능, 대각선에서 세로로 가능) 이 경우의 수들의 합
대각선으로 올 수 있는 경우의 수 -> (가로에서 대각선 가능, 세로에서 대각선 가능, 대각선에서 대각선 가능) 이 경우의 수들의 합

출처1
출처2