[프로그래머스]2020 카카오 인턴십- 경주로 건설, 파이썬

문제

---

• ㅍ로그래머스 경주로 건설 문제 링크

풀이

---

• 경로문제, 벽이 있는 문제이므로 아래, 위, 오른쪽, 위 4가지 방향으로 모두 움직이는 케이스를 고려해야 한다.
• 비용은 상하 에서 좌우로 변할 때 600원 상하, 좌우끼리는 100원 소요되므로 상하는 -1, 좌우는 1 값을 넣어 계산해줬다.
• 다음에 위치할 수 있는 위치(상하좌우로 이동, 0~N 사이의 위치, 벽이 아닌 경우)를 계산한다.
• check 배열을 만들어 초기값으로 무한을 주고 check 배열에 들어있는 값보다 같거나 작을 경우 큐에 추가해준다.
• check 배열을 만들지 않으면 무한루프에 빠짐
• x == N-1 and y == N-1 마지막에 도달하면 지금까지의 비용을 cand 배열에 넣고 최소값을 리턴한다.
• 뭔가 좀 지저분하게 푼 것 같은데 나중에 다시 확인해보기!

코드

---

  from collections import deque

  def nxt_cost(cur, nxt, cost):
      if cur * nxt > 0:  
          return cost + 100
      else :
          return cost + 600

  def bfs(q, cand, board, N, check):
      delta = [(0, 1, -1), (1, 0, 1), (0, -1, -1), (-1, 0, 1)]
      while q:
          x, y, cost, cur = q.popleft()
          if x == N-1 and y == N-1:
              cand.append(cost)
              continue
          for i, j, nxt in delta:
              n_x, n_y, n_cost = x + i, y + j, nxt_cost(cur, nxt, cost)
              if 0 <= n_x < N and 0 <= n_y <  N and not board[n_x][n_y]:
                  if check[n_x][n_y] >= n_cost:
                      check[n_x][n_y] = n_cost
                      q.append((n_x, n_y, n_cost, nxt))

  def solution(board):
      cand = []
      N = len(board)
      q = deque([(0, 0, 0, -1),(0, 0, 0, 1)])
      check = [[float('inf') for _ in range(N)] for _ in range(N)]
      bfs(q, cand, board, N, check)
      return min(cand)