[Seop's의 코드풀이] 프로그래머스 경주로 건설 - Python

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

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

 

 

문제요약

2차원 배열에서 최단거리를 구하는 문제에서 방향을 바꾸었을때 추가적인 비용이 발생하는 문제이다.  

목적지 N-1, N-1 에 도달하기 까지 가장 적은 비용을 구해내면 된다. 

 

문제풀이 IDEA

문제를 파악하고 난 후 해결해야 하는 문제는 다음과 같았다. 

• 각 칸에서 방향이 변동했는지 확인하기(코너인지 아닌지 파악)
• 가격정보를 어떻게 저장할 것이지?
• 어떤 탐색 방법을 사용할 것인지?

먼저 방향 변동에 대한 확인은 이전 방향과 같은지 파악하면 되었다. 상하좌우 4개 밖에 없기에 이 값을 기억하도록 진행했다. 

 

가격정보는 Board와 똑같은 N*N 배열을 만들어 저장했다. 하지만 해당 위치에서 가격이 같다 할지라도 최종 가격이 달라질 수 있었다. 

만들어 놓은 보드에는 최소 값만 저장하도록 진행하였고 현재 위치에서의 가격은 추가로 저장하였다.

 

배열의 최대 크기가 25*25 이므로 모두다 탐색 가능하다고 판단하여 BFS를 선택하였다.

 

이러한 정보를 기반으로 BFS를 동작시킬 Queue에 들어갈 정보는 다음과 같았다. 

(세로축 좌표, 가로축 좌표, 방향값, 해당 위치의 가격)

 

Queue의 정보를 가지고 문제에 따라서 BFS를 진행하준다면 가장 적은 비용을 알 수 있다.  

 

전체코드

from collections import deque

class Track :
    def __init__(self, board) :
        self.board = board
        self.N = len(board)
        self.check = [[0 for _ in range(self.N) ] for _ in range(self.N) ]

        self.di = [-1, 0, 1, 0]
        self.dj = [0, 1, 0, -1]

    def BFS(self) :
        que = deque()
        que.append((0,0,0,0))
        # i,j,방향, 가격

        while que :
            i,j,k, v = que.popleft()
            for p in range(4) :
                ni = i + self.di[p]
                nj = j + self.dj[p]
                
                if ni < 0 or nj < 0 or ni >= self.N or nj >= self.N  or (ni == 0 and nj == 0 ):
                    continue
                if self.board[ni][nj] == 1 :
                    continue

                if i == 0 and j == 0 :
                    price = 100
                elif k == p :
                    price = v + 100
                else :
                    price = v + 600

                if self.check[ni][nj] == 0 :
                    self.check[ni][nj] = price
                    que.append((ni,nj,p, price))
                elif price <= self.check[ni][nj] :
                    que.append((ni, nj, p, price))
                    self.check[ni][nj] = price
        
    def getAnswer(self) :
        self.BFS()
        return self.check[-1][-1]


def solution(board):
    answer = 0
    t = Track(board)
    answer = t.getAnswer()
    return answer

 

질문 및 피드백은 언제나 감사드립니다.