Py) 프로그래머스 67259 경주로 건설

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

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

 

1. 내 접근

가능한 모든 경우의 수를 전부 체크해야겠다고 생각했다.

완전 탐색에도 이용할 수 있는 방식이 여러가지가 있는데 (Brute Force, 순열, 재귀, 비트마스크, bfs/dfs)
* ref - https://hongjw1938.tistory.com/78

이 문제는 최단 거리는 아니지만 최소 비용을 탐색해야하고 맵의 크기가 엄청 크지 않아서 (최대 25*25) bfs를 사용할 수 있겠다고 생각함.

여기까지 괜찮은 생각이었는데,

이차원 리스트를 형성해서 진행되는 row, col 이 바뀌면 500원을 더하자! 라고 생각하기 시작했다.

그리고 머릿속이 꼬이기 시작함. 그 다음 단계가 꽉 막혀서 생각이 안나는 느낌...

+

DP를 사용해야할까? 잠깐 생각도 했었으나, 하나의 문제를 여러 하위로 나눠 푸는 것과, 메모이제이션 방식을 사용할 일이 없었다.

 

* 주의사항
최단 경로가 무조건 답이 아닐 수 있다.

입출력 예 4번을 보면 파란색은 11칸, 빨간색 13칸을 지나지만 비용적인 면에선 빨간색이 더 이익이다.

 

2. Solution

2-1. 사용 알고리즘: BFS
ⓛ가까운 노드부터 탐색하는 성질, ②최단 거리(경로) 탐색

2-2. 사용 자료구조
deque     # from collections import deque

2-3. 그 밖
float('inf')    # inf - 양의 무한대를 의미

 

2-4. 알고리즘 해설

1) dx, dy로 방향을 설정하고, 각 인덱스는 방향을 의미한다.

각각 1, 3은 좌, 상을 의미하는데, 우나 하는 뒤로 가는 것이므로 최단 비용이 될 수 없음이 분명하다.

따라서 첫 시작점에서 좌, 상으로 움직이는 경우를 고려하도록 방향을 append 해준다.

2) 현 좌표에서 각 0,1,2,3 (우,좌,하,상)의 경우를 더해서 각 위치당 경우를 고려한다.

이때, 입력되어있는 방향이 현재 방향과 다르면 +600 (코너+직선)원, 같으면 +100이다.

3) 범위와 벽인지 길인지 여부 체크, 현재 나온 비용이 앞서 구한 비용보다 적은지 판단해서 그 다음 계산 대상으로 append 해준다.

 

2-5. 코드

from collections import deque

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

def solution(board):
    answer = 0
    N = len(board)
    start, end = (0, 0), (N - 1, N - 1)
    costs = [[float('inf')] * N for _ in range(N)]
    # inf - 양의 무한대

    deq = deque()
    deq.append((0, 0, 0, 1))    # 좌
    deq.append((0, 0, 0, 3))    # 상
    costs[0][0] = 0     # 현재 비용: 0원
    while deq:
        x, y, cost, dir = deq.popleft()     # 좌표, 비용, 방향
        for k in range(4):      # 상하좌우 하나씩 좌표를 움직임
            nx = x + dx[k]
            ny = y + dy[k]
            tmp_cost = cost + 100 if dir == k else cost + 600   # 좌||상이면 100
            if 0 <= nx < N and 0 <= ny < N:     # 범위 체크
                if board[nx][ny] == 0 and tmp_cost <= costs[nx][ny]:    # 벽이 아닌지, 최소 값이 맞는지
                    costs[nx][ny] = tmp_cost        # 비용 설정
                    deq.append((nx, ny, tmp_cost, k))   # append

    answer = costs[end[0]][end[1]]

    return answer

 

*수정

테스트케이스 25번에서 계속 틀렸습니다가 뜸.

2차원 배열을 사용한 모든 코드가 다 틀렸습니다로 뜨고 있었다.

3차원 배열을 통해 재방문의 경우도 찾아내서 차단해줘야한다.

from collections import deque
def solution(board):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    N = len(board[0])

    answer = float('inf')
    deq = deque([])
    cost = [[[float('inf') for y in range(len(board))] for x in range(len(board))] for z in range(4)]

    for z in range(4):      # 방향을 추가해줌
        cost[z][0][0] = 0
        
    if board[1][0] != 1:    # x
        deq.append([1, 0, 100, 1])
        cost[1][1][0] = 100

    if board[0][1] != 1:    # y
        deq.append([0, 1, 100, 3])
        cost[3][0][1] = 100

    while deq:
        x, y, price, dir = deq.popleft()    # popleft다, 주의하자

        for i in range(4):      # 방향 비교, 범위 0~3
            nx = x+dx[i]
            ny = y+dy[i]
            tmp_price = price + 100 if i == dir else price + 600

            if 0 <= nx < N and 0 <= ny < N:
                if tmp_price < cost[i][nx][ny] and board[nx][ny] == 0:
                    deq.append([nx, ny, tmp_price, i])
                    cost[i][nx][ny] = tmp_price

    for z in range(4):
        if answer > cost[z][N-1][N-1]:
            answer = cost[z][N-1][N-1]


    return answer

방향 주의하자.. 진짜 헷갈린다..