📌 프로그래머스 Level 3 : 경주로 건설
bfs로 최소비용 업데이트해주면서 풀면 되겠다! 해서 풀었다가 마지막 테스트케이스를 통과 못해서 정말 애먹었던 문제..
구글링을 해보니 3차원 배열을 사용해 각 경로의 저비용을 계속 업데이트해줘야하는 문제였다..
처음에는 dp 풀듯이 bfs로 계속 최소 비용 저장해주면서 진행했는데,
이렇게 하면 지금은 최소 비용이지만, 다음 경로에서 가장 최소가 되는 경로가 누락되기 때문에 모든 방향에 대한 경로를 저장해주어야한다.
📝 내 답안
from collections import deque
def solution(board):
answer = 600*25
M = 600*25
n = len(board)
dp = [[[M for _ in range(n)] for _ in range(n)] for _ in range(4)]
# 방향 초기화
for i in range(4):
dp[i][0][0] = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()
#(x,y,방향,비용)
#시작할 때는 0과 1방향만 있으므로
q.append((0,0,0,0))
q.append((0,0,1,0))
while q:
x,y,d,c = q.popleft()
if (x,y) == (n-1,n-1):
continue
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n and board[nx][ny] == 0:
# 진행방향이 달라질 때
if i != d:
if c+6 < dp[i][nx][ny]:
dp[i][nx][ny] = c+6
q.append((nx,ny,i,c+6))
else:
if c+1 <= dp[i][nx][ny]:
dp[i][nx][ny] = c+1
q.append((nx,ny,i,c+1))
for i in range(4):
answer = min(answer,dp[i][-1][-1])
return answer*100
틀렸던 답안(2차원 배열 사용)
from collections import deque
def solution(board):
answer = 0
M = 600*25
n = len(board)
dp = [[M for _ in range(n)] for _ in range(n)]
dp[0][0] = 0
dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()
#(x,y,방향,비용)
#시작할 때는 0과 1방향만 있으므로
q.append((0,0,0,0))
q.append((0,0,1,0))
while q:
x,y,d,c = q.popleft()
if (x,y) == (n-1,n-1):
continue
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<n and board[nx][ny] == 0:
# 진행방향이 달라질 때
if i != d:
if c+6 <= dp[nx][ny]:
dp[nx][ny] = c+6
q.append((nx,ny,i,c+6))
else:
if c+1 <= dp[nx][ny]:
dp[nx][ny] = c+1
q.append((nx,ny,i,c+1))
answer = dp[-1][-1]*100
return answer
사실 처음에 틀렸던 2차원 배열 사용 답안이랑 3차원 배열 사용 답안이랑 거의 차이가 없다. 그저 3차원 배열을 사용해서 업데이트만 해주면 된다!
앞으로는 최소비용이면 꼭꼭 3차원 배열을 사용해야지..
