[프로그래머스] 경주로 건설 / Python / 2020 카카오 인턴십

 

https://programmers.co.kr/learn/courses/30/lessons/67259?language=python3

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

---

---

Solution

from collections import deque

# 동남북서
dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]
    
def racing(n, x, y, board, cost, direction):
    cost[y][x] = 0
    q = deque()
    q.append((0,x,y,0))
    q.append((0,x,y,1))
    while q:
        curr_cost, x, y, d = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            next_cost = 0
            if nx < 0 or ny < 0 or nx >= n or ny >= n or board[ny][nx] == 1:
                continue
            if i == d:
                new_cost = 100
            else:
                new_cost = 600
            next_cost = new_cost + curr_cost
            if cost[ny][nx] == -1 or cost[ny][nx] >= next_cost:
                cost[ny][nx] = next_cost
                q.append((next_cost, nx, ny, i))
    
def solution(board):
    n = len(board)
    cost = [[-1] * n for _ in range(n)]
    racing(n, 0, 0, board, cost, 0)
    print(cost)
    return cost[n-1][n-1]

 

BFS 응용 문제이다.

기존의 BFS를 이용하면 한번 방문했던 곳은 다시 방문하지 않지만 이 문제에서는 조건에 맞을 경우 다시 한번 더 방문할 필요가 있다. 처음 (0,0)에서 갈 수 있는 방향이 동쪽과 남쪽 두 가지이므로 그것까지 고려해서 풀어야한다. 나 같은 경우에는 queue에 현재 비용과 좌표, 방향을 담았다.

 

# 큐에 동쪽방향과 남쪽방향 각각 담는다.
def racing(n, x, y, board, cost, direction):
    cost[y][x] = 0
    # (현재 위치에서의 비용, x좌표, y좌표, 방향)
    q = deque()
    q.append((0,x,y,0))
    q.append((0,x,y,1))

 

queue에서 꺼낸 현재 보고있는 방향하고 BFS로 상하좌우로 탐색하면서 각각의 방향을 비교해서 같을 경우에는 직진 코스이므로 cost를 100만큼 더해주고, 다를 경우 코너 코스이므로 cost에 600을 더해준다. 그리고 next_cost에 현재 비용과 더해질 비용을 더해 넣는다.

 

# 직진 코스
if i == d:
    new_cost = 100
# 코너 코스
else:
    new_cost = 600
next_cost = new_cost + curr_cost

 

그리고 한번도 방문하지 않았거나, 다음 방문할 곳의 cost가 위에서 구한 next_cost보다 크거나 같을 경우 cost값을 갱신해준다.

 

if cost[ny][nx] == -1 or cost[ny][nx] >= next_cost:
    cost[ny][nx] = next_cost
    q.append((next_cost, nx, ny, i))