programmers.co.kr/learn/courses/30/lessons/42898
코딩테스트 연습 - 등굣길
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m =
programmers.co.kr
처음엔 단순히 bfs로 풀어보려고 했습니다.
// 오답
from collections import deque
dx = [1, 0]
dy = [0, 1]
def solution(m, n, puddles):
answer = 0
max_num = 1000000007
queue = deque([[1, 1]])
board = [[0] * (m + 1) for _ in range(n + 1)]
for x, y in puddles:
board[y][x] = 1
while queue:
x1, y1 = queue.pop()
for i in range(2):
nx = x1 + dx[i]
ny = y1 + dy[i]
if 1 <= nx <= m and 1 <= ny <= n and not board[ny][nx]:
if nx == m and ny == n:
answer += 1
break
queue.append([nx, ny])
return answer % max_num
m = 4
n = 3
puddles = [[2, 2]]
print(solution(m, n, puddles))하지만 시간초과가 많이 났고, 결국엔 dp 문제라는 걸 깨닫게 되었습니다...
// 통과
def solution(m, n, puddles):
max_num = 1000000007
board = [[0] * (m + 1) for _ in range(n + 1)]
board[1][1] = 1
for i in range(1, n + 1):
for j in range(1, m + 1):
if i == 1 and j == 1:
continue
if [j, i] in puddles:
board[i][j] = 0
else:
board[i][j] = board[i - 1][j] + board[i][j - 1]
answer = board[n][m]
return answer % max_num
