[프로그래머스] 경주로 건설 (Python 파이썬)

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

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

문제 설명

문제의 설명이 위 링크에 상세하게 나와있습니다.

(0,0) 칸 부터 (N-1, N-1)칸 까지 가는데 최소한의 비용을 구하는 문제입니다.

---

풀이 과정

시작지점에서 오른쪽과 아래쪽의 루트 중 한가지를 선택할 수 있습니다.

그래서 오른쪽으로 가는방법과 아래쪽으로 가는 방법 둘 다 실행해서

더 작은 값을 정답으로 출력하면 됩니다.

 

코드 설명은 다음과 같습니다.

price는 각 칸까지의 비용을 저장하는 그래프입니다.

시작지점은 0원이므로 0으로 저장을 하고 나머지 지점은 max값으로 지정을 합니다.

 

다음칸 까지 이동하는데, 방향이 같으면 100원, 방향을 꺾으면 600원을 추가하여

그 추가한 금액이 저장된 금액보다 적을 경우에만 값을 갱신합니다.

 

처음에는 max값으로 설정되어 있어, 무조건 갱신되겠지만

갱신된 곳은 더 적은 경우에만 갱신하게 됩니다.

 

마지막으로, 도착 칸의 값을 리턴하면 됩니다!

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(board, dir):
    n = len(board)
    price = [[int(1e9)] * n for _ in range(n)]
    price[0][0] = 0

    queue = deque()
    queue.append((0, 0, 0, dir))  # (시작X, 시작Y, 시작Cost, 시작방향)

    while queue:
        x, y, c, z = queue.popleft()

        if x == n - 1 and y == n - 1:
            continue

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = i

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if board[nx][ny] == 1:
                continue

            if nz == z:
                nc = c + 100
            else:
                nc = c + 600

            if nc < price[nx][ny]:
                price[nx][ny] = nc
                queue.append((nx, ny, nc, i))

    return price[-1][-1]


def solution(board):
    answer = min(bfs(board, 0), bfs(board, 2))
    return answer

 

 

두 번째 풀이는 bfs를 한 번만 실행하여 값을 구하는 방법입니다.

시작지점에서는 오른쪽 아래쪽 둘 다 움직일 수 있으므로

예외사항으로, 5라는 방향을 주어 두 방향 모두 100원을 추가하도록 합니다.

(단, 여기서 price칸 값을 갱신할 때 " < " 가 아닌 " <= " 를 해주어야 합니다. 그래야 같은 칸에서 두 방향으로 온 값이 겹쳤을 때 값이 같게되면, 멈추지 않고 계속 진행하게 됩니다. )

 

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(board):
    n = len(board)
    price = [[int(1e9)] * n for _ in range(n)]
    price[0][0] = 0

    queue = deque()
    queue.append((0, 0, 0, 5))  # (시작X, 시작Y, 시작Cost, 시작방향)

    while queue:
        x, y, c, z = queue.popleft()

        if x == n - 1 and y == n - 1:
            continue

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            nz = i

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if board[nx][ny] == 1:
                continue
            
            if z==5:
                nc = c + 100

            elif nz == z:
                nc = c + 100
                
            else:
                nc = c + 600

            if nc <= price[nx][ny]:
                price[nx][ny] = nc
                queue.append((nx, ny, nc, i))

    return price[-1][-1]


def solution(board):
    n = len(board)
    answer = bfs(board)
    return answer

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !