[프로그래머스] Level 3. 경주로 건설

https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

 

 

해결 방법

일반적인 다익스트라로 풀면 안된다. 일반적인 다익스트라로 풀경우, 몇 가지 테스트에서 실패가 나온다.

🚩 문제의 핵심:

✅ 1. 같은 좌표라도 "어떤 방향"으로 도착했는지가 중요하다!

• 같은 지점 (x, y)에 도착했다고 해도, "어떤 방향으로 왔는가"에 따라 앞으로 이동할 때 비용이 달라질 수 있다.

📍 예시:

• (0,0) → (0,1) → (1,1)로 이동하는 상황을 생각해보자. 1️⃣ 수평 이동: (0,0) → (0,1) (오른쪽으로 이동, 비용 +100)
  2️⃣ 수직으로 꺾기: (0,1) → (1,1) (아래로 이동, 코너 비용 +500 추가)
• 이 경우, (1,1)에 도착한 것은 동일하지만, 왼쪽에서 온 경우와 위쪽에서 온 경우는 이후의 경로에서 추가 비용이 다르게 발생한다. 
• 일반적인 다익스트라의 경우, 값이 동일하다면 왼쪽에서 왔는지 오른쪽에서 왔는지를 크게 구분하지않는다. 따라서 네 방향 각각의 경우에 대해 저장을 해둔다.

✅ 2. dist[x][y]만 사용하면 발생하는 문제점

• 기존의 다익스트라의 경우, dist[x][y] 값만을 저장한다(행렬이므로). 이는 (0,0) 에서 (x,y) 로 이동할때의 최단거리이다. 하지만 이는  방향정보를 무시한 비용이기 때문에, 다음 경로에 영향을 줄 수 있다.

❌ 문제 상황:

• 어떤 경로 A가 (x, y)에 더 적은 비용으로 도착했더라도,
  이후 경로가 더 많은 코너 비용을 발생시킬 수 있다.
• 반대로, 경로 B는 (x, y)에 도착할 때 비용이 더 크지만,
  이후로는 직선으로 더 효율적인 경로가 가능할 수 있다.

즉, 지점의 최소 비용만 비교하면 잘못된 경로를 선택할 가능성이 있다.

 

vector<vector<vector<int>>> dist(n, vector<vector<int>>(n, vector<int>(4, INT_MAX)));

 

 

dist[x][y][dir]의 의미:

• x, y : 현재 좌표
• dir : 이 좌표에 도달한 방향 (0: 위, 1: 아래, 2: 왼쪽, 3: 오른쪽)
• dist[x][y][dir] : 해당 방향으로 (x, y)에 도달했을 때의 최소 비용

📌 이 구조의 장점:

1. 방향별 최소 비용을 개별 관리:  같은 좌표라도 도달한 방향에 따라 최소 비용을 따로 저장.
2. 정확한 비교 가능: 새로운 경로로 도착할 때, 같은 방향으로 도달한 비용만 비교하므로 정확한 최적화 가능.
3. 최종 결과 계산: 마지막 지점에서 4가지 방향 중 최소 비용을 선택하면 정답이 된다.

 

#include <string>
#include <vector>
#include <climits>
#include <queue>
#include <iostream>

using namespace std;

struct Node {
    int x, y, cost, dir; // dir: 0=up, 1=down, 2=left, 3=right
    bool operator<(const Node& other) const {
        return cost > other.cost; // 최소 힙을 위해 반대로 설정
    }
};

int dx[4] = {-1, 1, 0, 0}; // 상, 하, 좌, 우
int dy[4] = {0, 0, -1, 1};

int solution(vector<vector<int>> board) {
    int n = board.size();
    vector<vector<vector<int>>> dist(n, vector<vector<int>>(n, vector<int>(4, INT_MAX)));
    priority_queue<Node> pq;

    // 시작점에서 상하좌우로 출발
    for (int dir = 0; dir < 4; dir++) {
        int nx = dx[dir];
        int ny = dy[dir];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 0) {
            pq.push({nx, ny, 100, dir});
            dist[nx][ny][dir] = 100;
        }
    }

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();

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

            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 0) {
                int newCost = cur.cost + 100;
                if (cur.dir != dir) { // 방향 전환 시 코너 비용 추가
                    newCost += 500;
                }

                if (newCost < dist[nx][ny][dir]) {
                    dist[nx][ny][dir] = newCost;
                    pq.push({nx, ny, newCost, dir});
                }
            }
        }
    }

    // 도착점의 4가지 방향 중 최소값 선택
    int result = INT_MAX;
    for (int dir = 0; dir < 4; dir++) {
        result = min(result, dist[n - 1][n - 1][dir]);
    }

    return result;
}

 

다익스트라 외에도 다양한 방법으로 이 문제를 풀 수 있다. 아래는 각 방법들과 장단점이다. 이 문제에서는 다익스트라와 a* 알고리즘이 가장 적합하다고 한다. (feat.GPT)

✅ 알고리즘 효율

알고리즘	특징	장점	단점
다익스트라	최단 거리 알고리즘	모든 상황에서 정확	느린 탐색 가능성
A*	휴리스틱 기반 최단 경로	빠른 탐색	휴리스틱 정확도 중요
BFS (0-1 BFS)	가중치 기반 BFS	간단하고 빠름	복잡한 비용 처리 어려움
DP	최적화된 상태 저장	누락 없이 계산	큰 그래프에서는 비효율

 

 

✅ A* 알고리즘으로 풀어보기

 

#include <vector>
#include <queue>
#include <climits>
#include <cmath>
#include <iostream>
using namespace std;

struct Node {
    int x, y, cost, dir;
    int priority; // g + h
    bool operator<(const Node& other) const {
        return priority > other.priority; // 최소 우선순위
    }
};

int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1};

int heuristic(int x, int y, int n) {
    return (n - 1 - x) + (n - 1 - y); // 맨해튼 거리
}

int solution(vector<vector<int>> board) {
    int n = board.size();
    vector<vector<vector<int>>> dist(n, vector<vector<int>>(n, vector<int>(4, INT_MAX)));
    priority_queue<Node> pq;

    for (int dir = 0; dir < 4; dir++) {
        int nx = dx[dir];
        int ny = dy[dir];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 0) {
            int cost = 100;
            pq.push({nx, ny, cost, dir, cost + heuristic(nx, ny, n)});
            dist[nx][ny][dir] = cost;
        }
    }

    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();

        if (cur.x == n - 1 && cur.y == n - 1) {
            return cur.cost;
        }

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

            if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 0) {
                int newCost = cur.cost + 100;
                if (cur.dir != dir) newCost += 500;

                if (newCost < dist[nx][ny][dir]) {
                    dist[nx][ny][dir] = newCost;
                    pq.push({nx, ny, newCost, dir, newCost + heuristic(nx, ny, n)});
                }
            }
        }
    }

    return -1;
}

 

 

마무리하며

다익스트라 뿐 아니라, A* 알고리즘을 공부해보는 좋은 기회가 되었다. 일반적인 다익스트라에서 , 방향성까지 고려할때 어떤식으로 확장이 되는지를 배웠다. 다음에 비슷한 문제가 나오면 풀 수 있..었으면 좋겠다!

게시글의 길이가 문제의 난이도를 나타내는것 같아서 재미있다