728x90
😉 아이디어
1. _!오른쪽!_과 _!아래!_로 움직임 가능 -> 동적프로그래밍 적용
😉 오답
fields = []
answer = 0
min_cost = 0
def solution(m, n, puddles):
global fields
global answer
global min_cost
MOD = 1_000_000_007
fields = [[999_999 for _ in range(m)] for __ in range(n)]
fields[0][0] = 0
for p in puddles:
fields[p[1] - 1][p[0] - 1] = -999 # 웅덩이 표시
for i in range(n):
for j in range(m):
now_cost = fields[i][j]
# print(f'i : {i}, j : {j}, value : {now_cost}')
if now_cost == -999:
continue
# 오른쪽
if j + 1 < m and fields[i][j + 1] != -999:
fields[i][j + 1] = min(now_cost + 1, fields[i][j + 1])
# 아래
if i + 1 < n and fields[i + 1][j] != -999:
fields[i + 1][j] = min(now_cost + 1, fields[i + 1][j])
# print(f'필드 : {fields}')
# min_cost = fields[n - 1][m - 1] # 이동하는데 필요한 최소거리
# dfs([0, 0], 0, m, n)
return answer % MOD
# def dfs(start, cost, m, n):
# global fields
# global answer
# global min_cost
# y = start[0]
# x = start[1]
# # 웅덩이면 미실행
# if fields[y][n] == -999:
# return;
# # 도착했으면 최솟값인지 확인
# if n - 1 == y and m - 1 == x:
# if min_cost == cost:
# # print(f'min_cost = {min_cost} | cost = {cost}')
# answer = answer % 1_000_000_007
# answer += 1
# return;
# # 오른쪽
# if y + 1 < n and fields[y + 1][x] != -999:
# dfs([y + 1, x], cost + 1, m, n)
# if x + 1 < m and fields[y][x + 1] != -999:
# dfs([y, x + 1], cost + 1, m, n)
😉 풀이
fields = []
answer = 0
min_cost = 0
def solution(m, n, puddles):
global fields
global answer
global min_cost
MOD = 1_000_000_007
fields = [[0 for _ in range(m)] for __ in range(n)]
fields[0][0] = 1
for p in puddles:
fields[p[1] - 1][p[0] - 1] = -999 # 웅덩이 표시
for i in range(n):
for j in range(m):
# print(f'i : {i}, j : {j}, value : {now_cost}')
if fields[i][j] == -999:
continue
# 오른쪽
if j - 1 >= 0 and fields[i][j - 1] != -999:
fields[i][j] += fields[i][j - 1]
# 아래
if i - 1 >= 0 and fields[i - 1][j] != -999:
fields[i][j] += fields[i - 1][j]
print(f'필드 : {fields}')
return fields[n - 1][m - 1] % MOD
✔️ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42898