Programmers :: 경주로 건설

문제

링크

🤔 생각

• bfs 를 베이스로 응용한 문제다.

• 다른건 그냥 bfs와 같으나, 한가지 관건은

• 직각을 만났을 때 어떻게 해주느냐다.

• 즉, 큐잉할 때마다 자신의 방향이 상/하/좌/우 중 어딘지 알아야 한다.

• 그리고 방향이 같을 때를 제외하고, 모두 코너인 것으로 처리해 비용 산정을 해주면 되겠다. -> 두 직선 방향 중 하나는 이전 노드기 때문

📌 내 풀이

from collections import deque

def bfs(board):
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    
    n = len(board)
    q = deque([(0,0,0,0),(0,0,0,1)])
    cache = [[-1]*n for _ in range(n)]
    cache[0][0] = 0
    
    while q:
        value,x,y,d = q.popleft()

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

            if 0<=nx< n and 0<=ny<n:
                if board[nx][ny] == 1: continue
                cost = 100 if d == i else 600
                n_cost = value + cost
                
                if cache[nx][ny] == -1 or cache[nx][ny] >= n_cost:
                    cache[nx][ny] = n_cost
                    q.append((n_cost,nx,ny,i))

    return cache[n-1][n-1]

    

def solution(board):
    return bfs(board)

• dx, dy 배열 좌표 순서를 마음대로 했다가 볼장 다 봤다..

• 보통 문제에서는 상관 없는데, 이 문제에서는 첫 방향을 지정해줘야 하니까

• 처음 큐잉한대로 좌표 순서도 그에 맞게 바꿔줘야 한다.

• 즉 첫 큐잉을 우,하 로 했으면, dx,dy도 처음엔 (0,1), (1,0)이 되어야 한다.

✔ 회고

• bfs 문제는 첫 큐잉을 어떻게 하느냐도 매우 중요하다.
• 이렇게 방향을 미리 정해둬야 하는 문제면, 첫 방향 두개를 미리 큐잉해줘야 한다.
• bfs를 활용한 응용 문제는 코테 단골 문제인것 같다.
• 적당히 어렵게 내기 딱 좋다. 더 연습하자