문제 링크

내 코드

Solution 참고

Solution

Approach 1: Dynamic Programming

• 55ms, 29.73MB
• Complexity
  • Let $n$ be the number of rows and $m$ be the number of columns in the grid.
  • Time Complexity: $O({(n \cdot m)}^2)$
  • Space Complexity: $O(n \cdot m)$

class Solution {
public:
    int minCost(vector<vector<int>>& grid) {
        int numRows = grid.size(), numCols = grid[0].size();
        vector<vector<int>> minChanges(numRows, vector<int>(numCols, INT_MAX));

        // Initialize all cells with max value
        minChanges[0][0] = 0;

        while (true) {
            // Store previous state to check for convergence
            vector<vector<int>> prevState = minChanges;

            // Forward pass: check cells coming from left and top
            for (int row = 0; row < numRows; row++) {
                for (int col = 0; col < numCols; col++) {
                    // Check cell above
                    if (row > 0) {
                        minChanges[row][col] =
                            min(minChanges[row][col],
                                minChanges[row - 1][col] +
                                    (grid[row - 1][col] == 3 ? 0 : 1));
                    }
                    // Check cell to the left
                    if (col > 0) {
                        minChanges[row][col] =
                            min(minChanges[row][col],
                                minChanges[row][col - 1] +
                                    (grid[row][col - 1] == 1 ? 0 : 1));
                    }
                }
            }

            // Backward pass: check cells coming from right and bottom
            for (int row = numRows - 1; row >= 0; row--) {
                for (int col = numCols - 1; col >= 0; col--) {
                    // Check cell below
                    if (row < numRows - 1) {
                        minChanges[row][col] =
                            min(minChanges[row][col],
                                minChanges[row + 1][col] +
                                    (grid[row + 1][col] == 4 ? 0 : 1));
                    }
                    // Check cell to the right
                    if (col < numCols - 1) {
                        minChanges[row][col] =
                            min(minChanges[row][col],
                                minChanges[row][col + 1] +
                                    (grid[row][col + 1] == 2 ? 0 : 1));
                    }
                }
            }

            // If no changes were made in this iteration, we've found optimal
            // solution
            if (prevState == minChanges) {
                break;
            }
        }

        return minChanges[numRows - 1][numCols - 1];
    }
};

GPT (o3-mini-high)

이 코드는 주어진 그리드에서 좌측 상단에서 우측 하단으로 가는 경로를 만들기 위해 화살표를 바꿔야 하는 최소 비용(수정 횟수)을 구하는 문제를 해결합니다.
각 셀에는 1, 2, 3, 4 중 하나의 값이 주어지며, 각 숫자는 아래와 같이 방향을 나타냅니다:

• 1: 오른쪽
• 2: 왼쪽
• 3: 아래쪽
• 4: 위쪽

셀의 화살표 방향을 그대로 따라가면 비용 0으로 이동할 수 있습니다.
하지만 경로를 만들기 위해 다른 방향으로 이동하려면, 해당 셀의 화살표를 바꿔야 하며, 이때 비용이 1씩 듭니다.

---

알고리즘 개요

이 솔루션은 동적 계획법(Dynamic Programming)과 반복적 완화(relaxation)를 사용하여 각 셀에 도달하기 위해 필요한 최소 변경 횟수를 구합니다.
먼저, minChanges[row][col]는 (row, col) 셀에 도달하는 데 필요한 최소 비용(수정 횟수)를 저장합니다.

1. 초기화

   • 모든 셀의 minChanges 값을 INT_MAX로 초기화합니다.
   • 시작 셀인 (0,0)은 0으로 초기화합니다.

2. 반복적 완화

   • Forward pass (전방향 완화):
     위쪽과 왼쪽에서 오는 경로를 고려하여 각 셀의 값을 갱신합니다.
   • Backward pass (후방향 완화):
     오른쪽과 아래쪽에서 오는 경로를 고려하여 각 셀의 값을 갱신합니다.
   • 두 방향의 완화를 반복하면서 값이 더 이상 변경되지 않을 때까지(수렴할 때까지) 수행합니다.

3. 최종 결과

   • (numRows-1, numCols-1) 셀의 값이 바로 목적지까지 도달하는 데 필요한 최소 비용입니다.

---

코드 세부 설명

1. 초기화

int numRows = grid.size(), numCols = grid[0].size();
vector<vector<int>> minChanges(numRows, vector<int>(numCols, INT_MAX));

// 시작 셀 (0,0)은 0 비용 (아무 것도 수정하지 않음)
minChanges[0][0] = 0;

• minChanges는 그리드의 각 셀까지 도달하는 최소 비용을 저장합니다.
• (0,0)은 시작점이므로 비용 0입니다.

---

2. 반복적 완화 (Forward & Backward Pass)

전체 완화 과정을 while 루프로 반복하면서, 이전 상태와 비교하여 변화가 없으면 종료합니다.

while (true) {
    // 이전 상태를 저장 (변화가 없는지 확인하기 위함)
    vector<vector<int>> prevState = minChanges;

2-1. Forward Pass

왼쪽과 위쪽 셀에서 현재 셀로 오는 경우를 고려합니다.

    for (int row = 0; row < numRows; row++) {
        for (int col = 0; col < numCols; col++) {
            // 위쪽 셀 (row-1, col)에서 내려오는 경우
            if (row > 0) {
                // 위쪽 셀의 화살표가 아래를 가리키면 (값이 3) 추가 비용 0, 그렇지 않으면 비용 1
                minChanges[row][col] =
                    min(minChanges[row][col],
                        minChanges[row - 1][col] + (grid[row - 1][col] == 3 ? 0 : 1));
            }
            // 왼쪽 셀 (row, col-1)에서 오른쪽으로 오는 경우
            if (col > 0) {
                // 왼쪽 셀의 화살표가 오른쪽을 가리키면 (값이 1) 추가 비용 0, 아니면 비용 1
                minChanges[row][col] =
                    min(minChanges[row][col],
                        minChanges[row][col - 1] + (grid[row][col - 1] == 1 ? 0 : 1));
            }
        }
    }

• 위쪽에서 내려오는 경우:
  (row-1, col) 셀에서 현재 셀 (row, col)로 내려오려면,
  위쪽 셀의 화살표가 3 (아래) 인 경우에는 비용 0,
  아니면 1의 비용이 듭니다.

• 왼쪽에서 오른쪽으로 오는 경우:
  (row, col-1) 셀에서 현재 셀로 이동하려면,
  왼쪽 셀의 화살표가 1 (오른쪽) 인 경우에는 비용 0,
  아니면 비용 1이 듭니다.

2-2. Backward Pass

오른쪽과 아래쪽 셀에서 현재 셀로 오는 경우를 고려합니다.

    for (int row = numRows - 1; row >= 0; row--) {
        for (int col = numCols - 1; col >= 0; col--) {
            // 아래쪽 셀 (row+1, col)에서 위쪽으로 오는 경우
            if (row < numRows - 1) {
                // 아래쪽 셀의 화살표가 위쪽을 가리키면 (값이 4) 비용 0, 아니면 1
                minChanges[row][col] =
                    min(minChanges[row][col],
                        minChanges[row + 1][col] + (grid[row + 1][col] == 4 ? 0 : 1));
            }
            // 오른쪽 셀 (row, col+1)에서 왼쪽으로 오는 경우
            if (col < numCols - 1) {
                // 오른쪽 셀의 화살표가 왼쪽을 가리키면 (값이 2) 비용 0, 아니면 1
                minChanges[row][col] =
                    min(minChanges[row][col],
                        minChanges[row][col + 1] + (grid[row][col + 1] == 2 ? 0 : 1));
            }
        }
    }

• 아래쪽에서 위로 오는 경우:
  (row+1, col) 셀에서 현재 셀 (row, col)로 이동하려면,
  아래쪽 셀의 화살표가 4 (위쪽) 인 경우에는 비용 0, 아니면 비용 1이 듭니다.

• 오른쪽에서 왼쪽으로 오는 경우:
  (row, col+1) 셀에서 현재 셀로 이동하려면,
  오른쪽 셀의 화살표가 2 (왼쪽) 인 경우에는 비용 0, 아니면 비용 1이 듭니다.

2-3. 수렴 검사

    // 이전 상태와 동일하면 더 이상 개선할 수 없으므로 종료.
    if (prevState == minChanges) {
        break;
    }
}

• 이전 반복에서의 minChanges와 현재 minChanges가 같으면,
  더 이상 업데이트할 값이 없으므로 반복문을 종료합니다.

---

3. 최종 결과 반환

return minChanges[numRows - 1][numCols - 1];

• (numRows-1, numCols-1) 셀까지 도달하는 데 필요한 최소 비용이 최종 답이 됩니다.

---

요약

이 알고리즘은

• 시작 셀에서부터 각 셀까지 도달하는 데 필요한 최소 수정 횟수를 minChanges 테이블에 저장합니다.
• 각 셀로의 도착 비용은 해당 인접 셀의 도달 비용과, 인접 셀에 있는 화살표가 현재 셀로 이동하는 데 올바른 방향인지 여부에 따라 결정됩니다.
• 전방 및 후방 완화를 반복하여 전체 그리드에 대해 최적의 비용을 찾고,
  수렴 시 (변화가 없을 때) 최종 결과를 반환합니다.

이 방식은 반복적 완화(또는 다이나믹 프로그래밍의 여러 패스) 기법을 통해 올바른 경로를 만드는 데 필요한 최소 변경 비용을 효과적으로 계산합니다.

Approach 2: Dijkstra’s Algorithm

• 99ms, 30.72MB
• Complexity
  • Let $n$ be the number of rows and $m$ be the number of columns in the grid.
  • Time Complexity: $O(n \cdot m \cdot \log{(n \cdot m)})$
  • Space Complexity: $O(n \cdot m)$

class Solution {
public:
    // Direction vectors: right, left, down, up (matching grid values 1, 2, 3,
    // 4)
    vector<vector<int>> dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

    int minCost(vector<vector<int>>& grid) {
        int numRows = grid.size(), numCols = grid[0].size();

        // Min-heap ordered by cost. Each element is {cost, row, col}
        priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;
        pq.push({0, 0, 0});

        // Track minimum cost to reach each cell
        vector<vector<int>> minCost(numRows, vector<int>(numCols, INT_MAX));
        minCost[0][0] = 0;

        while (!pq.empty()) {
            auto curr = pq.top();
            pq.pop();
            int cost = curr[0], row = curr[1], col = curr[2];

            // Skip if we've found a better path to this cell
            if (minCost[row][col] != cost) continue;

            // Try all four directions
            for (int dir = 0; dir < 4; dir++) {
                int newRow = row + dirs[dir][0];
                int newCol = col + dirs[dir][1];

                // Check if new position is valid
                if (newRow >= 0 && newRow < numRows && newCol >= 0 &&
                    newCol < numCols) {
                    // Add cost=1 if we need to change direction
                    int newCost = cost + (dir != (grid[row][col] - 1) ? 1 : 0);

                    // Update if we found a better path
                    if (minCost[newRow][newCol] > newCost) {
                        minCost[newRow][newCol] = newCost;
                        pq.push({newCost, newRow, newCol});
                    }
                }
            }
        }

        return minCost[numRows - 1][numCols - 1];
    }
};

GPT (o3-mini-high)

이 코드는 그리드(grid)에서 좌측 상단에서 시작하여 우측 하단까지 이동할 때,
셀에 표시된 방향(1: 오른쪽, 2: 왼쪽, 3: 아래쪽, 4: 위쪽)을 가능한 한 따르면서
경로를 만들기 위해 바꿔야 하는 최소 비용(방향을 바꾸는 횟수)을 구하는 문제를
다익스트라(Dijkstra) 알고리즘을 이용해 해결합니다.

아래 단계별로 코드를 설명합니다.

---

1. 방향 벡터 설정

// Direction vectors: right, left, down, up (matching grid values 1, 2, 3, 4)
vector<vector<int>> dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

• dirs 배열은 각 셀이 가리키는 방향에 해당하는 이동 벡터를 저장합니다.
  • 인덱스 0 → {0, 1}: 오른쪽
  • 인덱스 1 → {0, -1}: 왼쪽
  • 인덱스 2 → {1, 0}: 아래쪽
  • 인덱스 3 → {-1, 0}: 위쪽
• 그리드의 각 셀에 있는 값은 1~4이며,
  이를 인덱스로 사용하려면 grid[row][col] - 1을 사용합니다.

---

2. 초기화

int numRows = grid.size(), numCols = grid[0].size();

• numRows와 numCols는 그리드의 행과 열의 개수를 나타냅니다.

// Min-heap ordered by cost. Each element is {cost, row, col}
priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;
pq.push({0, 0, 0});

• pq는 우선순위 큐(최소 힙)로, 각 원소는 {현재까지 비용, 행, 열}을 나타냅니다.
• 시작점 (0,0)에서의 비용은 0이므로, {0, 0, 0}을 큐에 삽입합니다.

// Track minimum cost to reach each cell
vector<vector<int>> minCost(numRows, vector<int>(numCols, INT_MAX));
minCost[0][0] = 0;

• minCost 2차원 배열은 각 셀까지 도달하는 데 필요한 최소 비용을 저장합니다.
• 모든 셀을 INT_MAX(최대값)로 초기화한 후, 시작점 (0,0)의 비용은 0으로 설정합니다.

---

3. 다익스트라 알고리즘을 이용한 최단 경로 탐색

while (!pq.empty()) {
    auto curr = pq.top();
    pq.pop();
    int cost = curr[0], row = curr[1], col = curr[2];

    // Skip if we've found a better path to this cell
    if (minCost[row][col] != cost) continue;

• 큐에서 가장 비용이 작은 노드를 꺼내고,
  만약 이미 더 나은 경로로 해당 셀에 도달한 상태라면(현재 저장된 비용과 다르면)
  이 노드는 건너뜁니다.

    // Try all four directions
    for (int dir = 0; dir < 4; dir++) {
        int newRow = row + dirs[dir][0];
        int newCol = col + dirs[dir][1];

        // Check if new position is valid
        if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols) {
            // Add cost=1 if we need to change direction, else 0.
            // grid[row][col]-1 is the direction the cell "wants" to go.
            int newCost = cost + (dir != (grid[row][col] - 1) ? 1 : 0);

            // Update if we found a better path
            if (minCost[newRow][newCol] > newCost) {
                minCost[newRow][newCol] = newCost;
                pq.push({newCost, newRow, newCol});
            }
        }
    }
}

• 네 방향에 대해 이동을 시도합니다.
• newRow, newCol: 현재 셀에서 각 방향으로 이동한 새로운 위치입니다.
• 이동 가능한 범위(그리드 내부)인지 확인합니다.
• 비용 계산:
  • 만약 현재 셀의 지정된 방향(즉, grid[row][col] - 1)과 이동하려는 방향 dir이 같다면 추가 비용 0,
  • 다르면 1의 비용이 추가됩니다.
• 만약 새로 계산된 비용이 현재 minCost[newRow][newCol] 보다 작다면,
  해당 셀의 비용을 갱신하고 새로운 노드를 우선순위 큐에 삽입합니다.

---

4. 최종 결과 반환

return minCost[numRows - 1][numCols - 1];

• 반복문 종료 후, 우측 하단 셀 (numRows-1, numCols-1)까지 도달하는 최소 비용을 반환합니다.

---

결론

• 문제 접근:
  다익스트라 알고리즘을 활용하여,
  각 셀까지 도달하는 최소 비용(방향 수정 횟수)을 구합니다.

• 핵심 아이디어:

  • 각 셀의 기본 방향(값에 따른 지정 방향)을 따르면 비용 0,
  • 다른 방향으로 이동하면 비용 1을 부여하여 최단 경로(최소 비용 경로)를 찾습니다.

• 우선순위 큐 사용:
  최단 경로 탐색을 위해 비용을 기준으로 오름차순 정렬된 우선순위 큐를 사용합니다.

이러한 방식으로, 시작점에서 출발해 목적지까지 도달하는 데 필요한 최소 방향 변경 횟수를 효율적으로 계산할 수 있습니다.

Approach 3: 0-1 Breadth-First Search

• 7ms, 26.09MB
• Complexity
  • Let $n$ be the number of rows and $m$ be the number of columns in the grid.
  • Time Complexity: $O(n \cdot m)$
  • Space Complexity: $O(n \cdot m)$

class Solution {
public:
    // Direction vectors: right, left, down, up (matching grid values 1, 2, 3,
    // 4)
    vector<vector<int>> dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

    int minCost(vector<vector<int>>& grid) {
        int numRows = grid.size(), numCols = grid[0].size();

        // Track minimum cost to reach each cell
        vector<vector<int>> minCost(numRows, vector<int>(numCols, INT_MAX));

        // Use deque for 0-1 BFS - add zero cost moves to front, cost=1 to back
        deque<pair<int, int>> deque;
        deque.push_front({0, 0});
        minCost[0][0] = 0;

        while (!deque.empty()) {
            auto [row, col] = deque.front();
            deque.pop_front();

            // Try all four directions
            for (int dir = 0; dir < 4; dir++) {
                int newRow = row + dirs[dir][0];
                int newCol = col + dirs[dir][1];
                int cost = (grid[row][col] != (dir + 1)) ? 1 : 0;

                // If position is valid and we found a better path
                if (isValid(newRow, newCol, numRows, numCols) &&
                    minCost[row][col] + cost < minCost[newRow][newCol]) {
                    minCost[newRow][newCol] = minCost[row][col] + cost;

                    // Add to back if cost=1, front if cost=0
                    if (cost == 1) {
                        deque.push_back({newRow, newCol});
                    } else {
                        deque.push_front({newRow, newCol});
                    }
                }
            }
        }

        return minCost[numRows - 1][numCols - 1];
    }

private:
    // Check if coordinates are within grid bounds
    bool isValid(int row, int col, int numRows, int numCols) {
        return row >= 0 && row < numRows && col >= 0 && col < numCols;
    }
};

GPT (o3-mini-high)

이 코드는 0-1 BFS (Breadth First Search)를 사용하여, 주어진 그리드에서 좌측 상단 (0,0)에서 우측 하단 (numRows-1, numCols-1)까지 도달하는 데 필요한 최소 비용(방향을 바꿔야 하는 횟수)을 구하는 문제를 해결합니다.

각 셀에는 1, 2, 3, 4 중 하나의 값이 있으며, 이 값은 해당 셀이 “가리키는” 기본 이동 방향을 나타냅니다:

• 1: 오른쪽
• 2: 왼쪽
• 3: 아래쪽
• 4: 위쪽

만약 셀의 기본 방향대로 이동하면 추가 비용 없이 (비용 0) 이동할 수 있고, 다른 방향으로 이동하면 비용 1이 듭니다.

---

코드 구성 및 동작 설명

1. 방향 벡터 선언

// Direction vectors: right, left, down, up (matching grid values 1, 2, 3, 4)
vector<vector<int>> dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

• dirs 배열은 가능한 네 방향에 대한 이동 벡터를 저장합니다.
• 인덱스 0, 1, 2, 3는 각각 오른쪽, 왼쪽, 아래, 위 방향을 나타내며,
  그리드 셀의 값과 비교할 때는 grid[row][col] - 1 로 매칭됩니다.

---

2. 최소 비용 배열 및 0-1 BFS 초기화

int numRows = grid.size(), numCols = grid[0].size();

// Track minimum cost to reach each cell
vector<vector<int>> minCost(numRows, vector<int>(numCols, INT_MAX));

// Use deque for 0-1 BFS - add zero cost moves to front, cost=1 to back
deque<pair<int, int>> deque;
deque.push_front({0, 0});
minCost[0][0] = 0;

• minCost: 각 셀까지 도달하는 데 필요한 최소 비용을 저장하는 2차원 배열로, 처음에는 무한대(INT_MAX)로 초기화되고, 시작 셀 (0,0)은 0으로 설정합니다.
• deque: 0-1 BFS를 위해 사용되며, 비용이 0인 이동은 큐의 앞쪽에, 비용이 1인 이동은 뒤쪽에 삽입하여 최소 비용 순서대로 탐색할 수 있도록 합니다.
• 시작 셀 (0,0)을 deque의 앞쪽에 삽입합니다.

---

3. 0-1 BFS 반복 과정

while (!deque.empty()) {
    auto [row, col] = deque.front();
    deque.pop_front();

• deque에서 가장 앞쪽의 셀 (row, col)을 꺼내 현재 위치로 설정합니다.
• 이미 더 나은 경로로 해당 셀에 도달한 경우(즉, minCost[row][col]가 갱신되었으면)에는 건너뛰도록 합니다. (이 부분은 이전 코드에서는 검사했으나, 여기서는 0-1 BFS 특성상 이미 최단 경로 순으로 탐색하기 때문에 생략한 형태입니다.)

    // Try all four directions
    for (int dir = 0; dir < 4; dir++) {
        int newRow = row + dirs[dir][0];
        int newCol = col + dirs[dir][1];
        int cost = (grid[row][col] != (dir + 1)) ? 1 : 0;

• 현재 셀에서 네 방향으로 이동을 시도합니다.
• newRow와 newCol: 이동 후 도착할 셀의 좌표를 계산합니다.
• cost:
  • 현재 셀의 값(grid[row][col])은 기본 이동 방향을 나타냅니다.
  • 만약 이동하려는 방향 dir (0부터 시작하므로 실제 방향 값은 dir + 1)과 일치하면 비용은 0,
  • 그렇지 않으면 비용은 1이 됩니다.

        // If position is valid and we found a better path
        if (isValid(newRow, newCol, numRows, numCols) &&
            minCost[row][col] + cost < minCost[newRow][newCol]) {
            minCost[newRow][newCol] = minCost[row][col] + cost;

• 새 좌표가 그리드 내에 있는지 확인한 후,
  현재까지의 비용 minCost[row][col]에 이동 비용 cost를 더한 값이 기존에 기록된 minCost[newRow][newCol]보다 작으면 해당 셀의 최소 비용을 갱신합니다.

            // Add to back if cost=1, front if cost=0
            if (cost == 1) {
                deque.push_back({newRow, newCol});
            } else {
                deque.push_front({newRow, newCol});
            }
        }
    }
}

• 이동 비용에 따라 다음과 같이 처리합니다:
  • 비용이 0이면, 해당 셀을 deque의 앞쪽에 추가합니다. (즉, 우선순위가 높음)
  • 비용이 1이면, 해당 셀을 deque의 뒤쪽에 추가합니다.
• 이 방식은 0-1 BFS의 표준 기법으로, 비용이 0인 경로를 먼저 처리하여 전체 최단 경로(최소 비용 경로)를 보장합니다.

---

4. 결과 반환 및 유효성 검사 함수

return minCost[numRows - 1][numCols - 1];

• 반복이 종료되면, 우측 하단 셀 (numRows-1, numCols-1)까지 도달하는 데 필요한 최소 비용이 minCost[numRows - 1][numCols - 1]에 저장되어 있습니다.

// Check if coordinates are within grid bounds
bool isValid(int row, int col, int numRows, int numCols) {
    return row >= 0 && row < numRows && col >= 0 && col < numCols;
}

• isValid 함수는 주어진 좌표가 그리드 내부에 있는지 검사하는 간단한 헬퍼 함수입니다.

---

결론

• 문제 접근:
  0-1 BFS를 이용하여, 그리드에서 각 셀까지 도달하는 최소 비용(방향을 변경해야 하는 횟수)을 구합니다.
• 핵심 아이디어:
  • 셀의 기본 방향을 따르면 비용이 0, 그렇지 않으면 비용이 1이다.
  • 비용이 0인 경로를 우선 처리하기 위해 deque를 사용합니다.
• 최종 결과:
  시작점 (0,0)부터 우측 하단 (numRows-1, numCols-1)까지 이동하는 데 필요한 최소 비용을 반환합니다.

이 방식은 비용이 0 또는 1인 경우에 매우 효율적인 0-1 BFS를 활용하여 최단 경로 문제를 해결하는 전형적인 방법입니다.

Approach 4: Depth-First Search + Breadth-First Search

• 9ms, 20.05MB
• Complexity
  • Let $n$ be the number of rows and $m$ be the number of columns in the grid.
  • Time Complexity: $O(n \cdot m)$
  • Space Complexity: $O(n \cdot m)$

class Solution {
private:
    // Direction vectors: right, left, down, up (matching grid values 1,2,3,4)
    const vector<vector<int>> dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

public:
    int minCost(vector<vector<int>>& grid) {
        int numRows = grid.size(), numCols = grid[0].size(), cost = 0;

        // Track minimum cost to reach each cell
        vector<vector<int>> minCost(numRows, vector<int>(numCols, INT_MAX));

        // Queue for BFS part - stores cells that need cost increment
        queue<pair<int, int>> queue;

        // Start DFS from origin with cost 0
        dfs(grid, 0, 0, minCost, cost, queue);

        // BFS part - process cells level by level with increasing cost
        while (!queue.empty()) {
            cost++;
            int levelSize = queue.size();

            while (levelSize-- > 0) {
                auto [row, col] = queue.front();
                queue.pop();

                // Try all 4 directions for next level
                for (int dir = 0; dir < 4; dir++) {
                    dfs(grid, row + dirs[dir][0], col + dirs[dir][1], minCost,
                        cost, queue);
                }
            }
        }

        return minCost[numRows - 1][numCols - 1];
    }

private:
    // DFS to explore all reachable cells with current cost
    void dfs(vector<vector<int>>& grid, int row, int col,
             vector<vector<int>>& minCost, int cost,
             queue<pair<int, int>>& queue) {
        if (!isUnvisited(minCost, row, col)) return;

        minCost[row][col] = cost;
        queue.push({row, col});

        // Follow the arrow direction without cost increase
        int nextDir = grid[row][col] - 1;
        dfs(grid, row + dirs[nextDir][0], col + dirs[nextDir][1], minCost, cost,
            queue);
    }

    // Check if cell is within bounds and unvisited
    bool isUnvisited(vector<vector<int>>& minCost, int row, int col) {
        return row >= 0 && col >= 0 && row < minCost.size() &&
               col < minCost[0].size() && minCost[row][col] == INT_MAX;
    }
};

GPT (o3-mini-high)

이 코드는 그리드에서 시작점 (0,0)부터 목표점 (numRows‑1, numCols‑1)까지 이동하는 데 필요한 최소 비용(방향을 바꿔야 하는 횟수)을 구하는 문제를 해결합니다.
문제 조건은 각 셀에 1, 2, 3, 4의 값이 주어지며, 이 값은 셀이 기본적으로 가리키는 방향을 나타냅니다:

• 1: 오른쪽
• 2: 왼쪽
• 3: 아래쪽
• 4: 위쪽

셀의 기본 방향을 따르면 비용 없이 이동할 수 있지만, 다른 방향으로 이동하려면 비용 1이 듭니다.

이 코드에서는 DFS와 BFS를 결합한 방식(0-1 BFS와 유사한 기법)을 사용하여,
비용이 없는 이동(즉, 셀의 기본 방향을 따르는 이동)은 DFS로,
비용이 1인 이동은 BFS를 통해 단계별로 확장하면서 각 셀까지 도달하는 최소 비용을 구합니다.

---

주요 구성 요소

1. 방향 벡터

// Direction vectors: right, left, down, up (matching grid values 1,2,3,4)
const vector<vector<int>> dirs = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

• 각 인덱스는 1, 2, 3, 4에 해당하는 기본 이동 방향을 나타냅니다.
• 예를 들어, grid 셀의 값이 1이면 (1‑1 = 0) dirs[0]인 {0, 1} (오른쪽)으로 이동하는 것을 의미합니다.

---

2. 최소 비용 저장 배열과 초기 상태

int numRows = grid.size(), numCols = grid[0].size(), cost = 0;
vector<vector<int>> minCost(numRows, vector<int>(numCols, INT_MAX));
queue<pair<int, int>> queue;

• minCost: 각 셀까지 도달하는 데 필요한 최소 비용을 저장합니다. 처음에는 모든 셀을 INT_MAX로 초기화합니다.
• queue: BFS에 사용할 큐로, 비용을 1 증가시켜야 하는 경로 확장을 위해 사용됩니다.
• 시작점 (0,0)은 비용 0으로 설정하고, DFS 탐색의 출발점으로 사용됩니다.

---

3. DFS를 이용한 비용 0 이동 확장

dfs(grid, 0, 0, minCost, cost, queue);

• dfs 함수는 현재 셀에서 기본 방향(화살표 방향)을 따라 추가 비용 없이 이동할 수 있는 모든 셀을 방문합니다.
• DFS 내부에서 방문하지 않은 셀(즉, 아직 더 낮은 비용으로 방문하지 않은 셀)에 대해,
  현재 비용을 기록하고 BFS 큐에 해당 셀을 추가합니다.
• 그런 다음, 그 셀의 기본 방향으로 재귀적으로 DFS를 진행하여,
  비용을 추가하지 않고 도달할 수 있는 경로들을 모두 탐색합니다.

dfs 함수 내부 동작:

void dfs(vector<vector<int>>& grid, int row, int col,
         vector<vector<int>>& minCost, int cost,
         queue<pair<int, int>>& queue) {
    if (!isUnvisited(minCost, row, col)) return;  // 범위 내 있고, 아직 방문하지 않은지 확인
    minCost[row][col] = cost;                      // 현재 비용 기록
    queue.push({row, col});                        // BFS 큐에 추가

    // 현재 셀의 기본 방향을 따라 추가 비용 없이 이동
    int nextDir = grid[row][col] - 1;              // grid 값에 따라 인덱스 계산
    dfs(grid, row + dirs[nextDir][0], col + dirs[nextDir][1],
        minCost, cost, queue);
}

• isUnvisited 함수는 주어진 좌표가 그리드 내부에 있고 아직 방문(또는 최소 비용 갱신)되지 않았는지 확인합니다.

---

4. BFS를 이용한 비용 1 이동 확장

while (!queue.empty()) {
    cost++;
    int levelSize = queue.size();

    while (levelSize-- > 0) {
        auto [row, col] = queue.front();
        queue.pop();

        // 현재 셀에서 네 방향 모두를 고려하며 DFS 진행 (비용 +1)
        for (int dir = 0; dir < 4; dir++) {
            dfs(grid, row + dirs[dir][0], col + dirs[dir][1], minCost, cost, queue);
        }
    }
}

• BFS는 비용을 1씩 증가시키면서,
  이전 단계에서 방문된 셀들에서 “비용 1”의 이동(즉, 셀의 기본 방향을 따르지 않는 이동)을 고려합니다.
• 각 BFS 레벨에서, 큐에 들어있는 모든 셀에 대해 네 방향을 검사하고,
  DFS를 호출하여 해당 방향으로 이동 후, 기본 방향으로 추가 비용 없이 이동할 수 있는 경로를 확장합니다.
• 이렇게 함으로써,
  현재까지의 비용 +1으로 도달할 수 있는 모든 셀에 대해 최소 비용을 갱신합니다.

---

5. 최종 결과

return minCost[numRows - 1][numCols - 1];

• BFS와 DFS를 통해 그리드의 모든 셀에 대해 최소 비용을 계산한 후,
  우측 하단 셀 (목표 지점)까지 도달하는 최소 비용이 minCost[numRows‑1][numCols‑1] 에 저장됩니다.
• 이 값을 반환하여 문제의 답을 제공합니다.

---

결론

• 문제 접근:
  • DFS를 사용하여, 셀의 기본 방향을 따르는 비용 0 이동 경로를 먼저 확장합니다.
  • 그 후, BFS를 이용해 비용 1인 이동(즉, 기본 방향을 벗어난 이동)을 단계별로 처리합니다.
• 장점:
  • 비용 0인 경로는 재귀적 DFS로 빠르게 확장하여,
    추가 비용 없이 도달할 수 있는 경로들을 한 번에 탐색할 수 있습니다.
  • BFS를 통해 비용을 점진적으로 증가시키며 최단 경로를 보장합니다.
• 최종 결과:
  • 시작점 (0,0)에서 목표점까지 도달하기 위해 필요한 최소 비용(방향 변경 횟수)을 구합니다.

이 방식은 0-1 BFS와 DFS의 장점을 결합한 전형적인 방법으로,
문제에서 요구하는 “최소 비용” 경로를 효율적으로 찾아내는 알고리즘입니다.