백준 14503 로봇 청소기

해당 문제는 3 종류의 파이프를 나누어서 처리하는 문제이다.

0. 문제 핵심

1. 첫 파이프는 가로이며 0,0 과 0,1에 있다. 즉, 0,1 지점에서 시작된다.
   

2. 파이프의 움직이는 방향은 가로, 세로, 대각선이므로 위로는 올라갈 수 없다. 즉, visit 배열을 쓰지 않아도 n-1, n-1 지점에 도달 할 수 있다.
   (아래의 그림을 통해 이해할 수 있다.)
   
   

즉, 모든 경로를 탐색하는 bfs dfs를 선택할 수 있다. 또한, 해당 좌표에서의 모든 경우의 수를 더하는 dp도 선택 가능하다.

1. bfs (시간초과)

bfs의 경우 que로 부터 인접 좌표를 먼저 탐색하므로 특정 좌표에 도달하는 문제에는 성능이 떨어진다.

from collections import deque
import sys

def cross_check(y, x):
    if lis[y+1][x] == 0 and lis[y][x+1] == 0 and lis[y+1][x+1] == 0:
        return True

    return False

def bfs(y,x,pipe):      # pipe = 0,1,2 -> 가로,세로,대각선
    global cnt
    que = deque()

    que.append((y,x,pipe))

    while que:
        ty, tx, tpipe = que.popleft()

        if ty == n-1 and tx == n-1:
            cnt += 1
            continue        # 모든 경우의 수를 찾아야하므로

        if tpipe == 0:
            if 0 <= tx+1 <= n-1 and lis[ty][tx+1] == 0:
                que.append((ty,tx+1,0))
            if 0 <= ty+1 <= n-1 and 0 <= tx+1 <= n-1:
                if cross_check(ty, tx):
                    que.append((ty+1,tx+1,2))

        elif tpipe == 1:
            if 0 <= ty+1 <= n-1 and lis[ty+1][tx] == 0:
                que.append((ty+1,tx,1))
            if 0 <= ty+1 <= n-1 and 0 <= tx+1 <= n-1:
                if cross_check(ty, tx):
                    que.append((ty+1,tx+1,2))

        elif tpipe == 2:
            if 0 <= tx+1 <= n-1 and lis[ty][tx+1] == 0:
                que.append((ty,tx+1,0))
            if 0 <= ty+1 <= n-1 and lis[ty+1][tx] == 0:
                que.append((ty+1,tx,1))
            if 0 <= ty+1 <= n-1 and 0 <= tx+1 <= n-1:
                if cross_check(ty, tx):
                    que.append((ty+1,tx+1,2))



input = sys.stdin.readline

n = int(input())
lis = []
cnt = 0

for _ in range(n):
    lis.append(list(map(int, input().split(" "))))

bfs(0,1,0)
print(cnt)

2. dfs

dfs의 경우 특정 좌표에 도달할 때 까지 탐색하므로 이 문제에서는 bfs 보다 조금 더 적합하다. (문제에서의 시간제한이 빡빡하기 때문에)

# dfs
# 가로 = 가로, 대각선
# 세로 = 세로, 대각선
# 대각선 = 가, 세, 대각선

# visit는 필요 없음 -> n, n으로 가는 방법밖에 없기 때문

def dfs(y, x, pipe):        # pipe = 0,1,2 -> 가로, 세로, 대각선
    global cnt

    if y == n-1 and x == n-1:
        cnt += 1
        return

    if pipe == 0:
        if x+1 < n and lis[y][x+1] == 0:
            dfs(y, x+1, 0)
        if x+1 < n and y+1 < n and lis[y+1][x] == 0 and lis[y+1][x+1] == 0 and lis[y][x+1] == 0:
            dfs(y+1, x+1, 2)
    if pipe == 1:
        if y+1 < n and lis[y+1][x] == 0:
            dfs(y+1, x, 1)
        if x+1 < n and y+1 < n and lis[y+1][x] == 0 and lis[y+1][x+1] == 0 and lis[y][x+1] == 0:
            dfs(y+1, x+1, 2)
    if pipe == 2:
        if x+1 < n and lis[y][x+1] == 0:
            dfs(y, x+1, 0)
        if y+1 < n and lis[y+1][x] == 0:
            dfs(y+1, x, 1)
        if x+1 < n and y+1 < n and lis[y+1][x] == 0 and lis[y+1][x+1] == 0 and lis[y][x+1] == 0:
            dfs(y+1, x+1, 2)


import sys

input = sys.stdin.readline
n = int(input())
lis = []
cnt = 0

for _ in range(n):
    lis.append(list(map(int, input().split(" "))))

dfs(0,1,0)

print(cnt)

3. dp

dp의 메모이제이션으로 인해 시간, 메모리 부분에서 가장 적합했다.
dp[y][x][pipe] 가 있다면, y,x 좌표에서의 특정 파이프에 대한 경우의 수이다. (pipe = 0,1,2를 가로,세로,대각선으로 가정했다.)

예를 들어, pipe = 0 = 가로라면 이전 좌표에서도 가로 or 대각선이었기에, dp[y][x][0] = dp[y][x-1][0] + dp[y][x-1][2] 가 된다.

# dp
# d[y][x][pipe] = y,x에서의 pipe일 때 경우의 수

n = int(input())
lis = []
dp = [[[0] * 3 for _ in range(n)] for _ in range(n)]

for _ in range(n):
    lis.append(list(map(int, input().split(" "))))

dp[0][1][0] = 1     # 초기 가로 파이프

for r in range(n):
    for c in range(2, n):
        if lis[r][c] == 1:
            continue

        if c-1 >= 0 and lis[r][c-1] == 0:
            dp[r][c][0] = dp[r][c-1][0] + dp[r][c-1][2]

        if r-1 >= 0 and lis[r-1][c] == 0:
            dp[r][c][1] = dp[r-1][c][1] + dp[r-1][c][2]

        if r-1 >= 0 and c-1 >= 0 and lis[r-1][c-1] == 0 and lis[r-1][c] == 0 and lis[r][c-1] == 0:
            dp[r][c][2] = dp[r-1][c-1][1] + dp[r-1][c-1][0] + dp[r-1][c-1][2]

print(dp[n-1][n-1][2] + dp[n-1][n-1][1] + dp[n-1][n-1][0])

아래는 시간, 메모리 제한 결과이다. (위부터 dp, dfs, bfs..)