17070

날짜 : 2023. 06. 23

사용 언어 : python

 

문제

 

코드

정답(DP 사용)

import sys

n = int(sys.stdin.readline())
graph = list()
for _ in range(n): graph.append(list(map(int, sys.stdin.readline().split())))
dp = [[[0] * n for _ in range(n)] for _ in range(3)]
dp[0][0][1] = 1   # 방향, r, c

for i in range(2, n):
    if graph[0][i] == 0:
        dp[0][0][i] = dp[0][0][i-1]  # 가로 이동

for i in range(1, n):
    for j in range(1, n):
        # 현재 위치가 대각선
        if graph[i][j] == 0 and graph[i][j-1] == 0 and graph[i-1][j] == 0:
            dp[2][i][j] = dp[0][i-1][j-1] + dp[1][i-1][j-1] + dp[2][i-1][j-1]
        # 현재 상태가 가로 / 세로
        if graph[i][j] == 0:
            dp[0][i][j] = dp[0][i][j - 1] + dp[2][i][j - 1]  # 가로상태(가로->가로, 대각선->가로)
            dp[1][i][j] = dp[1][i - 1][j] + dp[2][i - 1][j]  # 세로상태(세로->세로, 대각선->세로)
res = 0
for i in range(3):
    res += dp[i][n-1][n-1]
print(res)

 

DFS(시간초과)

import sys

def dfs(now):
    global res
    i, j, dir = now
    # print(now)
    if i == (n - 1) and j == (n - 1):
        res += 1
        return
    # 대각선 이동
    if (i + 1) < n and (j + 1) < n:
        if g[i + 1][j] == 0 and g[i][j+1] == 0 and g[i+1][j+1] == 0:
            dfs([i+1, j+1, 2])
    # 가로 이동
    if dir == 0 or dir == 2:
        if (j + 1) < n:
            if g[i][j + 1] == 0:
                dfs([i, j + 1, 0])
    # 세로 이동
    if dir == 1 or dir == 2:
        if (i + 1) < n:
            if g[i + 1][j] == 0:
                dfs([i + 1, j, 1])
    return


n = int(sys.stdin.readline())
g = []
for _ in range(n): g.append(list(map(int, sys.stdin.readline().split())))

start = [0, 1, 0]
res = 0
dfs(start)
print(res)

 

BFS(시간초과)

import sys
from collections import deque

def check(r, c, flag):
    if r == (n-1) and c == (n-1) and flag and graph[r][c] == 0:  # 도착
        global cnt
        cnt += 1
        return False
    if r in range(n) and c in range(n) and graph[r][c] == 0:  # 범위 체크, 가능성 확인
        return True
    else:  
        return False

def bfs():
    queue = deque()
    queue.append([0, 1, 0])
    while queue:
        i, j, dir = queue.popleft()
        if dir == 0:  # 가로
            fir = [i, j+1, 0]
            sec = [i+1, j+1, 2]
            if check(fir[0], fir[1], True):
                queue.append(fir)
            if check(i+1, j, False) and check(i, j + 1, False) and check(sec[0], sec[1], True):
                queue.append(sec)
        elif dir == 1:  # 세로
            fir = [i + 1, j, 1]
            sec = [i + 1, j + 1, 2]
            if check(fir[0], fir[1], True):
                queue.append(fir)
            if check(i+1, j, False) and check(i, j + 1, False) and check(sec[0], sec[1], True):
                queue.append(sec)
        elif dir == 2:  # 대각
            fir = [i, j + 1, 0]
            sec = [i + 1, j, 1]
            thd = [i + 1, j + 1, 2]
            if check(fir[0], fir[1], True):
                queue.append(fir)
            if check(sec[0], sec[1], True):
                queue.append(sec)
            if check(i+1, j, False) and check(i, j + 1, False) and check(thd[0], thd[1], True):
                queue.append(thd)
    return


n = int(sys.stdin.readline())
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

cnt = 0

bfs()
print(cnt)

 

 

풀이

- 조건에 따라 입력받은 후 방향, 좌표에 따른 이동방식을 저장하기 위한 3차원 리스트(dp)를 만든다.

- 일괄적으로 가로로 이동이 가능한 케이스가 있기 때문에 for문을 사용해 맨 위의 열을 초기화한다.

- 이후, 현재 dp 리스트의 맨 처음 인덱스값에 따라 진행방향을 맞추어 나간다.

- 예를들어, dp[1][3][2]의 경우, 선발점이 graph[3][2]이고, 현재 세로방향으로 위치한다는 것을 의미한다.

- 이렇게 이중 for문을 실행하면서, 해당 인덱스의 graph값이 0인 경우 이동이 가능하기 때문에 앞선 방향으로부터 메모이제이션을 진행한다.

- 현재 위치에서 각각 가로, 세로, 대각선의 케이스를 전부 조건에 맞추어 구해나간 후, 마지막에는 해당 위치에 도달했을 때 가로, 세로, 대각선인 상태의 경우의 수를 전부 더한 다음 값을 출력한다.

 

 

알게된 점

- 처음 완전탐색을 사용해 BFS로 풀어보려 했지만 TLE

- 이후 DFS를 사용해 진행하려고 했지만 TLE

- 찾아보니까 파이썬은.... DFS, BFS로는 1초 안에 풀 수가 없는 듯 했다.

- 그래서 결국 DP로 풀이하는 방식을 참고했고, 아래 링크를 참고해서 풀 수 있었다.

- 처음에는 맨 위의 row를 전부 1로 초기화하는 이유를 몰랐지만, 가로, 세로의 경우에는 각각 오른쪽 아래로 진행한다는 것에 착안해 미리 선언했다는 것을 이해할 수 있었다.

- 정답률에 혹해서 풀었지만 되게.. 억까를 많이 당한듯한 문제였다.

 

 

참고 사이트

- DP 풀이 참고 : https://backtony.github.io/algorithm/2021-03-02-algorithm-boj-class4-44/

(Python) 백준 17070번 파이프 옮기기1 - class 4