[DAY97] Algorithm : Race Track Construction

격자판에서 출발지부터 목적지까지 경주로를 건설하는 최소 비용을 구하는 문제다. 직선 도로와 코너의 건설 비용이 다르기 때문에, 단순한 최단 거리가 아닌 '방향(Direction)'을 포함한 최소 비용을 계산해야 한다. 이를 위해 BFS와 3차원 배열을 활용하여 상태를 관리하는 것이 핵심이다.

---

❓ 문제 분석

• 목표: (0, 0)에서 (N-1, N-1)까지 가는 경주로 건설의 최소 비용 구하기.
• 제약 조건:
  • 격자 크기 $N$: $3 \le N \le 25$.
  • 비용: 직선 도로는 100원, 코너(방향 전환)는 500원 추가.
  • 핵심 포인트: 특정 지점에 도착했을 때, 어느 방향에서 왔느냐에 따라 다음 지점으로 가는 비용이 달라진다. 따라서 2차원 방문 배열(visited[x][y])만으로는 최적해를 보장할 수 없다.
• 핵심 키워드: "최소 비용", "직선 도로 vs 코너", "방향성"

---

💡 풀이 설계

1. 시도했던 접근 (2D BFS)

• 처음엔 일반적인 미로 찾기처럼 visited[x][y]에 최소 비용을 저장하려 했다.
• 하지만, 같은 지점이라도 '위에서 왔을 때'와 '왼쪽에서 왔을 때' 다음 이동 비용이 달라지는(회전 여부) 문제를 해결할 수 없어 실패했다.

2. 최종 해결책 (3D BFS with Direction) 💡

• 전략: 방문 상태를 (행, 열, 방향) 3가지로 정의하여 관리한다.
• 자료구조: int cost[25][25][4]
  • cost[x][y][dir]: (x, y) 지점에 dir 방향을 보며 도착했을 때의 최소 비용.
• 알고리즘 흐름:
  1. 초기화: 출발점 (0, 0)에서는 방향이 없으므로, 시작하자마자 갈 수 있는 오른쪽/아래쪽 칸을 미리 계산하여 큐에 넣고 시작한다. (비용 100원)
  2. BFS 탐색:
     • 큐에서 현재 상태(x, y, dir, cost)를 꺼낸다.
     • 4방향으로 이동을 시도한다.
     • 비용 계산: 기본 100원을 더하고, 만약 현재 방향 != 다음 방향이면 코너 비용 500원을 추가한다.
  3. 갱신 조건: 계산된 next_cost가 cost[nx][ny][next_dir]에 기록된 값보다 저렴할 때만 갱신하고 큐에 넣는다.
  4. 결과: 도착점 (N-1, N-1)의 4가지 방향 중 최솟값을 반환한다.

---

💻 코드 구현

#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 방향: 0(우), 1(하), 2(좌), 3(상)
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

struct State {
    int x, y, dir, total_cost;
};

int solution(vector<vector<int>> board) {
    int N = board.size();
    // cost[x][y][dir]: (x, y) 위치에 dir 방향으로 진입했을 때의 최소 비용
    // N이 최대 25이므로 고정 배열 사용이 간편함
    int cost[25][25][4];
    
    // 비용 배열을 충분히 큰 값(INF)으로 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int d = 0; d < 4; d++) {
                cost[i][j][d] = 1e9;
            }
        }
    }

    queue<State> q;

    // 출발점 초기화 예외 처리
    // (0,0)에서 방향 없이 시작하는 대신, 가능한 첫 이동(우, 하)을 미리 수행
    if (board[0][1] == 0) {
        q.push({0, 1, 0, 100}); // 오른쪽 이동
        cost[0][1][0] = 100;
    }
    if (board[1][0] == 0) {
        q.push({1, 0, 1, 100}); // 아래쪽 이동
        cost[1][0][1] = 100;
    }

    // BFS 탐색
    while (!q.empty()) {
        State cur = q.front();
        q.pop();

        // 현재 경로가 이미 기록된 비용보다 비싸다면 더 볼 필요 없음 (Pruning)
        if (cost[cur.x][cur.y][cur.dir] < cur.total_cost) continue;

        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];

            // 범위 초과 또는 벽(1) 체크
            if (nx < 0 || nx >= N || ny < 0 || ny >= N || board[nx][ny] == 1) continue;

            // 비용 계산: 직선(100) + 코너(500, 방향 다를 시)
            int next_cost = cur.total_cost + 100;
            if (cur.dir != i) next_cost += 500;

            // 더 저렴한 비용으로 도달 가능한 경우만 갱신
            if (cost[nx][ny][i] > next_cost) {
                cost[nx][ny][i] = next_cost;
                q.push({nx, ny, i, next_cost});
            }
        }
    }

    // 정답 도출: 도착점에 도달한 모든 방향 중 최소 비용 선택
    int answer = 1e9;
    for (int i = 0; i < 4; i++) {
        answer = min(answer, cost[N - 1][N - 1][i]);
    }

    return answer;
}

---

🐛 시행착오 및 디버깅

• 초기 상태 처리: 시작점 (0, 0)은 이전 방향이 없어서 코너 계산이 애매했다. 이를 반복문 안에서 if (x==0 && y==0)으로 처리하면 코드가 복잡해지므로, 아예 시작하자마자 한 칸 이동한 상태들을 큐에 넣고 시작하는 방식으로 깔끔하게 해결했다.
• 차원 확장: 처음엔 2차원 배열로 풀려다 실패했다. 이동 비용에 '방향'이 영향을 미칠 때는 반드시 방향 정보까지 상태에 포함(3차원 배열)시켜야 한다는 점을 배웠다.

---

✅ 오늘의 회고

항목	내용
유형	BFS (너비 우선 탐색), DP
체감 난이도	상 (상태 관리 아이디어가 필요함)
복잡도	시간: $O(N^2 \times 4)$, 공간: $O(N^2 \times 4)$
새로 배운 것	최단 거리 문제에서 '비용'이 가변적일 때(예: 회전 비용), 방문 배열(visited)의 차원을 늘려 상태를 구체화해야 한다는 테크닉을 익혔다.