출처: 백준 온라인 저지
https://www.acmicpc.net/problem/17070
시간 초과 풀이 1
from sys import stdin
n = int(stdin.readline())
house = [[1] * (n + 1)]
for _ in range(n):
nums = [1] + [int(x) for x in stdin.readline().split()]
house.append(nums)
def dp(r, c, direction):
if r == (n - 1) and c == (n - 1):
return 1
if r == n:
if direction == 'S':
return 0
else:
return 1
if c == n:
if direction == 'E':
return 0
else:
return 1
if house[r][c + 1] == 1:
a = 0
else:
a = dp(r, c + 1, 'E')
if house[r][c + 1] == 1 or house[r + 1][c] == 1:
b = 0
else:
b = dp(r + 1, c + 1, 'SE')
if house[r + 1][c] == 1:
c = 0
else:
c = dp(r + 1, c, 'S')
if direction == 'E':
return a + b
elif direction == 'SE':
return a + b + c
else:
return b + c
print(dp(1, 2, 'E'))1월 31일의 풀이다. 당시 동적 프로그래밍 문제들을 풀고 있어서, DP로 구현해보았는데 시간 초과가 떴다. 얼핏 봐도 조건이 지나치게 많아서 비효율적으로 보인다.
시간 초과 풀이 2
from sys import stdin
from collections import deque
n = int(stdin.readline())
house = [[-1] * (n + 2)]
for _ in range(n):
house.append([-1] + [-int(x) for x in stdin.readline().split()] + [-1])
house.append([-1] * (n + 2))
def get_in_queue(r, c, q, way):
house[r][c] += 1
q.append((r, c, way))
def bfs(r, c, direction):
queue = deque()
queue.append((r, c, direction))
house[r][c] += 1
while queue:
r, c, direction = queue.popleft()
if house[r][c + 1] > -1 and house[r + 1][c] > -1 and house[r + 1][c + 1] > -1:
get_in_queue(r + 1, c + 1, queue, 'SE')
if direction == 'E' or direction == 'SE':
if house[r][c + 1] > -1:
get_in_queue(r, c + 1, queue, 'E')
if direction == 'S' or direction == 'SE':
if house[r + 1][c] > -1:
get_in_queue(r + 1, c, queue, 'S')
bfs(1, 2, 'E')
if house[n][n] == -1:
print(0)
else:
print(house[n][n])몇 시간 전의 풀이다. 그래프 탐색 문제 카테고리에도 이 문제가 있어서, 이번에는 BFS로 구현해보았다. 이번 코드도 역시 한 눈에 보기에도 정답과는 멀어 보이며, 실제로도 시간 초과가 떴다.
시간 초과 풀이 3
다시 DP로 풀어보기로 했다. 앞선 DP 풀이는 어떤 규칙을 찾았다기보다는, 그저 모든 경우의 수를 하나하나 다 따져서 더하는 것에 불과했다.
https://www.acmicpc.net/board/view/34823
위 글에서, 각 칸마다 3가지 방향으로 그 칸에 갈 수 있는 경로의 수를 저장하여 DP로 풀 수 있음을 말했다. 그런데 그렇게 할 경우 재귀 함수가 여러 값을 반환해야 하므로, 처리하기가 복잡했다. 그래서 아예 각 방향별로 따로 재귀 함수를 만들기에 이르렀다. 역시 시간 초과였다.
from sys import stdin
n = int(stdin.readline())
house = [[1] * (n + 2)]
for _ in range(n):
house.append([1] + [int(x) for x in stdin.readline().split()] + [1])
house.append([1] * (n + 2))
def east(r, c):
if house[r][c] > 0:
return 0
if r == 1 and c == 2:
return 1
if c < 3:
return 0
else:
return east(r, c - 1) + southeast(r, c - 1)
def southeast(r, c):
if house[r][c] > 0 or house[r - 1][c] > 0 or house[r][c - 1] > 0:
return 0
if r == 1 or c < 3:
return 0
else:
return east(r - 1, c - 1) + southeast(r - 1, c - 1) + south(r - 1, c - 1)
def south(r, c):
if house[r][c] > 0:
return 0
if r < 3 or c < 3:
return 0
else:
return southeast(r - 1, c) + south(r - 1, c)
print(east(n, n) + southeast(n, n) + south(n, n))정답 풀이
무언가 근본적인 문제가 있다는 생각으로 10분쯤 종이에 그린 표를 바라보다가 갑자기 문제를 깨달았다.
동적 프로그래밍을 구현하는 방식은 크게 2가지가 있다. 하나는 재귀 함수를 사용하는 Memoization이고, 다른 하나는 반복문을 사용하는 Tabulation이다.
이 문제에서는 어떤 좌표 A에 대해서, 그 좌표의 왼쪽, 왼쪽 위, 위쪽 좌표를 끝점으로 하는 경로의 수를 알고 있으면, 좌표 A를 끝으로 하는 경로들의 수도 구할 수 있다. 따라서 반복문으로 한 행마다 채워나가면 전체 좌표의 경로의 수를 구할 수 있다. 이렇게 Tabulation 방식으로 구현하면 복잡한 재귀로 인한 오버헤드를 방지할 수 있다.
구현하기도 쉽다.
n = int(stdin.readline())
house = [[1] * (n + 2)]
for _ in range(n):
house.append([1] + [int(x) for x in stdin.readline().split()] + [1])
house.append([1] * (n + 2))
ways = [[[0, 0, 0] for _ in range(n + 2)] for _ in range(n + 2)]
ways[1][2][0] = 1
for c in range(3, n + 1):
for r in range(1, n + 1):
if house[r][c] == 0:
ways[r][c][0] = ways[r][c - 1][0] + ways[r][c - 1][1]
ways[r][c][2] = ways[r - 1][c][1] + ways[r - 1][c][2]
if house[r - 1][c] == 0 and house[r][c - 1] == 0:
ways[r][c][1] = sum(ways[r - 1][c - 1])
print(sum(ways[n][n]))별로 어렵지 않은 문제였는데, DP는 곧 재귀라는 생각에 갇혀서 푸는데 아주 오래 걸렸다. DP는 반복문으로도 풀 수 있다는 사실을 잊지 말자.
