경주로 건설 문제풀이

이 문제는 주어진 nxn 보드에 도로를 건설하는 것이 목표다. 최단거리, 최소비용으로 도착점에 도달해야한다.

• 최단거리로 가야하니 왔던 길을 되돌아가면 안된다.
• 최소비용으로 가야하니 방향을 최소한으로 틀어야한다. (직/후진은 100원, 좌/우회전은 600원)
• 모든 경로를 기록해야하니 알맞은 저장방식이 필요하다.
  BFS(Breadth First Search) 탐색 방식을 이용한 풀이를 정리해보자.
• 풀이는 자바스크립트로 했으며 코드는 아래와 같다.

const solution = (board) => {
    const n = board.length
    const Q = [[0,0,'',0]]
    const directionAdds = [0, 1, 3]

    const checkPush = ([x,y]) => {
        return x >= 0 && x < n && y >= 0 && y < n && !(x === 0 && y === 0) && board[y][x] !== 1
    }

    while (Q.length) {
        let [x,y,direction,price] = Q[0]
        if (board[y][x] >= price || board[y][x] === 0) {
            board[y][x] = price
            directionAdds.forEach(n => {
                let D = (direction+n)%4
                let a = D === 0 ? x+1 : (D === 2 ? x-1 : x)
                let b = D === 1 ? y+1 : (D === 3 ? y-1 : y)
                if (checkPush([a,b])) {
                    Q.push([a,b, D, n === 0 || direction === '' ? price + 100 : price + 600])
                }
            })
        }
        Q.shift()
    }
    return board[n-1][n-1]
}

프로그래머스에서 문제 보기

경주로 건설 문제

I. 목록에 저장하는 형식

1. 수많은 경로

일단 기본으로 주어지는 장애물 없는 3x3칸을 살펴보자. 이 경우 한번만 꺾어 도착지점에 도달하는 900원이 답이된다.

• 다만 (2, 0)을 지나 도착지점에 갈 수도 있고 (0, 2)를 지나 도착지점에 갈 수도 있다.
  

• 하지만 이 외에도 무수히 많은 경로가 존재할 수 있다. 이 모든 경로들을 탐색해서 위처럼 최소비용으로 건설할 수 있는 방법을 찾아야한다.

• 따라서 모든 경로들을 탐색할 필요가 있다.
  여기서 BFS(Breadth First Search) 방식으로 모든 가능성을 살펴본다.

BFS는 가장 가까운 거리의 노드, 즉 지금 당장 한칸 이동으로 어디에 갈 수 있는지만 모두 파악한다. 위 문제에서 처음에 갈 수 있는 곳은 두가지다.

그렇다면 다음 방문 칸을 (1, 0)과 (0, 1)이라고 저장해보자.

2. 좌표 외의 정보가 필요한 이유

다음 방문 칸을 (1, 0)이라고만 저장한다면 아래와 같은 문제가 발생한다.

• 출발지점에서 온 것인지, (1, 1)에서 온 것인지 아니면 (2, 0)에서 온 것인지를 알 수 없다.
• 때문에 해당 칸까지의 건설 비용 또한 알 방법이 없다.
  

3. 필요한 정보

따라서 칸의 좌표만 저장하는 것이 아니라 총 네 가지 정보를 저장하기로 한다.
1. 방문할 칸의 x좌표
2. 방문할 칸의 y좌표
3. 해당칸을 방문한 방향
4. 해당칸까지의 경주로 건설 비용
여기서 해당칸을 방문한 방향은 어떤칸에서 왔는지를 알려준다. 방향은 아래와 같이 0, 1, 2, 3의 숫자로 나타낸다.

예시

위 그림에에서 (1, 0) 칸을 저장하는 방법은 다음과 같다.

x, y, D, price
[1, 0, 0, 100]

• (1, 0)은 위치를 나타낸다
• 0은 왼쪽칸에서 왔음을 뜻하는 방향이다
• 100은 현재까지의 건설비용이 100원임을 뜻한다

이제 가능한 모든 경우의 수를 목록(queue)에 저장해야한다.

II. 조건 설정

[x좌표, y좌표, 최근방향, 현재까지 비용] 형식으로 가장 낮은 깊이부터 탐색 및 저장을 하게된다.

하지만 다음 탐색 칸이 보드 밖으로 넘어가거나 이미 왔던 길을 되돌아가는 등의 불필요한 탐색이 발생할 수 있으니 규칙을 정해야한다.

1. x, y 조건

0 ≤ x < n
0 ≤ y < n
x = 0 AND y = 0 이면 안된다 ( 시작점으로 가면 안됨)
board[y][x] = 0 (1이면 장애물이 있다는 뜻으로 해당 칸에 경주로를 건설할 수 없다)

2. 다음 방향 구하기

되돌아가면 안된다

다음 방향을 설정하는데 있어 가장 중요한 것은 이미 왔던 길을 되돌아가면 안된다는 것이다.

방향이 0이었다면 다음 방향이 2가 되면 안된다
방향이 1이었다면 다음 방향이 3이 되면 안된다
방향이 2였다면 다음 방향이 0이 되면 안된다
방향이 3이었다면 다음 방향이 1이 되면 안된다.

공식

되돌아가는 것만 제외한 방향을 구해보자

k = [0, 1, 3]
D_new = (D_old + k) % 4

• 반대방향끼리는 서로 2가 차이나기때문에 k에는 2만 제외하고 대입해준다.
• 0, 1, 3을 차례대로 대입해 방향을 정해주면 되돌아가는 것만 제외한 방향들이 나온다.

예시

D_old = 0;
D_new = (0 + 0) % 4 = 0; (k=0)
D_new = (0 + 1) % 4 = 1; (k=1)
D_new = (0 + 3) % 4 = 3; (k=3)
D_new = [0, 1, 3];

• 이전 방향이 0이었다면 다음 방향은 2가 되면 안된다.
• k에 0, 1, 3을 차례대로 대입해 다음 방향을 구해주면 0, 1, 3이 나오는 것을 확인할 수 있다. 이전 방향이 다른 숫자여도 마찬가지다.

3. 보드에 기록

방문할 칸의 목록을 작성하는 방법은 알아봤다.
하지만 방문순서만으로는 정답 경로가 무엇인지 확인하기 어렵다.
때문에 보드판에 경주로 비용을 계속 입력해줘야한다.

보드판에 입력하는 규칙은 다음과 같다.

1. 목록의 칸과 그에 해당하는 비용을 순서대로 참고한다.
2. 해당하는 칸의 비용이 0이라면 구한 비용을 적어준다.
3. 해당하는 칸에 이미 비용이 기입되어있더라도 만약 목록의 비용이 더 작다면 작은 것으로 바꿔준다.
4. 벽을 뜻하는 1이 적혀있는 칸은 당연히 비용을 적지 않는다.

예시

다음과 같은 탐색 목록이 작성되었다고 해보자. 편의상 번호를 매겼다.

1. [1, 0, 0, 100]
2. [0, 1, 1, 100]
3. [2, 0, 0, 200]
4. [1, 1, 1, 700]
5. [0, 2, 1, 200]
6. [1, 1, 0, 700]

보드판에는 위와같은 비용들이 입력된다. 아직 탐색을 끝마치지 않았기 때문에 도착점까지의 비용은 입력되지않았다.

• 여기서 4, 6번이 같은 칸에 대한 탐색임을 알 수 있다.
• 4번은 위에서 내려온 것이고 6번은 왼쪽에서 온 것이다.
• 다행히 둘의 비용이 700원으로 같았으나 만약 한 쪽 값이 컸다면 더 작은 값으로 대체되었을 것이다.

III. 목록에 저장하기

필요한 규칙을 모두 정했으니 이제 탐색을 시작해보자. BFS 방식으로 어느 칸에 갈지 탐색 목록을 만들고 각 이동을 보드판에 비용으로 기록할 것이다.

1. 첫번째 깊이

시작점에서 갈 수 있는 곳은 우측과 아래, 두가지뿐이다.

따라서 목록에는 [1, 0, 0, 100]과 [0, 1, 1, 100] 이렇게 두가지만 저장된다.
목록은 Q 라는 배열을 만들어 관리하도록 하자.

Q = [
	[1, 0, 0, 100],
    	[0, 1, 1, 100]
    ]

2. 두번째 깊이

다음 이동은 1번과 2번에서 각각 뻗어나간다.

• 1번에서 갈 수 있는 옵션은 우측과 아래 두가지이다. 꺾는 순간 비용은 600원이 추가되기 때문에 아래로 이동하는 경우의 비용은 700원이 된다.

• 2번은 아래와 우측 두갈래로 뻗어나갈 수 있다.

1번과 2번에서 각각 두가지 탐색을 진행했기 때문에 총 네가지의 이동이 목록에 추가된다.

Q = [
	[1, 0, 0, 100],
    	[0, 1, 1, 100],
        [2, 0, 0, 200],
        [1, 1, 1, 700],
        [0, 2, 1, 200],
        [1, 1, 0, 700]
    ]

그리고 보드에 비용을 차례대로 입력해주면 된다.

탐색 목록은 링크에서 확인할 수 있다.

번호순으로 탐색해 목록 Q에 차례대로 저장하면서 보드판에 비용을 입력해준다.
최종적으로 도착지점에 입력된 비용이 경주로 건설의 최소비용이 된다.

IV. 코드 분석

참고한 코드는 아래와 같다.

const solution = (board) => {
    const n = board.length
    const Q = [[0,0,'',0]]
    const Dadd = [0, 1, 3]

    const checknext = ([x,y]) => {
        return x >= 0 && x < n && y >= 0 && y < n && !(x === 0 && y === 0) && board[y][x] !== 1
    }

    while (Q.length) {
        let [x,y,D,price] = Q[0]
        if (board[y][x] >= price || board[y][x] === 0) {
            board[y][x] = price
            Dadd.forEach(k => {
                let D = (D_old+n)%4
                let a = D === 0 ? x+1 : (D === 2 ? x-1 : x)
                let b = D === 1 ? y+1 : (D === 3 ? y-1 : y)
                if (checknext([a,b])) {
                    Q.push([a,b, D, k === 0 || D_old === '' ? price + 100 : price + 600])
                }
            })
        }
        Q.shift()
    }
    return board[n-1][n-1]
}

• n 은 보드판의 크기를 나타낸다. 3x3 보드판이라면 n은 2가된다.
• Q는 탐색 목록으로 x좌표, y좌표, 방향, 그리고 비용을 한 배열에 저장한다.
• checknext 함수는 [x, y] 좌표를 인자로 받으며 해당 칸이 갈 수 있는 칸인지 판단해준다
  • 유효한 이동칸이면 1을, 유효하지않으면 0을 반환한다.
• Q 목록에 탐색항목이 존재하는 동안 Q에 탐색항목을 계속 추가하고 앞의 것을 제거한다
  • Q.shift()는 Q배열의 첫항목을 제거해준다.
• Q의 첫 항목을 현재 x, y, D, price로 지정한다.
• 보드판에서 현재 좌표에 해당하는 칸의 값이 0이거나 비용보다 크면 비용으로 대체한다.
  • 항상 더 적은 비용으로 대체해야한다
• Dadd[0, 1, 3]에 대해 각각 탐색을 진행한다.
  • 방향에 0, 1, 3을 더해 현재 칸에서 이동할 방향을 구한다.
  • 구해진 방향으로 이동했을 때의 좌표를 (a, b)로 구한다
  • 다음 이동하기로 한 (a, b)칸이 유효한 칸인지 확인한다.
  • 유효한 경우 Q 목록에 추가한다.
    • k=0으로 현재 방향 그대로 가거나 예전 방향이 존재하지않을 때 (처음일 때)는 비용이 100원이다.
    • 하지만 방향이 바뀌면 비용은 600원이 된다.
    • 뒤로 되돌아가는 것은 유효하지 않아 제외한다.