[프로그래머스 LV 3] 경주로 건설 (파이썬/python)

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

 

풀던도중에 갑자기 매형이 우리집에 와서 가족식사를 했다...

진짜 밥 먹는 내내 풀던 코드 생각나서 밥도 제대로 못 먹음

 

푼 방법은 bfs를 사용했다. depth를 최소로 하며 목적지 까지 가고싶었기 때문이다. dfs로 풀어도 됐을듯?

visit 리스트에는 그 칸에 갈 수 있는 최소 금액을 저장해줬다. 

만약 이미 방문은 했지만 금액이 

내가 지금 다시 갔을때 더 쌀 경우 방문하고 금액수정해줬다.

 

visit[len(board)-1][len(board)-1] 에 저장된 금액이 목적지로 도착 하는데 필요한 금액이자 최소값이다.

 

 

import sys
from collections import deque
 
 
def solution(board):
    # 상,하,좌,우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque()
    visit = [[sys.maxsize] * len(board) for _ in range(len(board))]
    visit[0][0] = 0
 
    # 현재 행, 현재 열, 상태(모름 : 0 / 가로 : 1 / 세로 : 2) , 금액
    q.append([0, 0, 0, 0])
 
    while q:
 
        x, y, state, cnt = q.popleft()
 
        for i in range(4):
 
            nx = x + dx[i]
            ny = y + dy[i]
 
            if nx < 0 or ny < 0 or nx >= len(board) or ny >= len(board):
                continue
 
            if board[nx][ny] != 1:
                # 가로상태 좌우 이동 -> 직진도로
                if (state == 1 and (i == 2 or i == 3)) or (state == 2 and (i == 0 or i == 1)):
                    if visit[nx][ny] >= cnt + 100:
                        if state == 1:
                            q.append([nx, ny, 1, cnt + 100])
                            visit[nx][ny] = cnt + 100
                        else:
                            q.append([nx, ny, 2, cnt + 100])
                            visit[nx][ny] = cnt + 100
                elif (state == 1 and (i == 0 or i == 1)) or (state == 2 and (i == 2 or i == 3)):
                    if visit[nx][ny] >= cnt + 600:
                        if state == 1:
                            q.append([nx, ny, 2, cnt + 600])
                            visit[nx][ny] = cnt + 600
                        else:
                            q.append([nx, ny, 1, cnt + 600])
                            visit[nx][ny] = cnt + 600
 
                    # state 가 0인 상태일때
                else:
                    # 상하
                    if i == 0 or i == 1:
                        q.append([nx, ny, 2, 100])
                        visit[nx][ny] = 100
                    else:
                        q.append([nx, ny, 1, 100])
                        visit[nx][ny] = 100
 
    return visit[len(board) - 1][len(board) - 1]