백준 4485 녹색 옷 입은 애가 젤다지? C++ 풀이

백준 4485 녹색 옷 입은 애가 젤다지? C++

✅ 문제 소개

문제 내용

젤다의 전설 게임 속 주인공은 링크입니다. 그러나 많은 사람들이 “녹색 옷 입은 애가 젤다지?”라고 착각합니다.
스트레스를 받은 링크는 도둑루피로 가득한 동굴에 들어갑니다.
링크는 동굴을 통과하며 최대한 적은 루피만 잃고 출구까지 도달해야 합니다.

✅ 테스트케이스

입력 예시

3
5 5 4
3 9 1
3 2 7
0

출력 예시

Problem 1: 20

✅ 문제 설명

동굴 구조

입력 예시에서 주어진 3×3 동굴입니다.
각 칸의 숫자는 해당 칸을 지나갈 때 잃는 루피입니다.

5	5	4
3	9	1
3	2	7

링크는 왼쪽 위(5)에서 출발해 오른쪽 아래(7)로 가야 합니다.

잘못된 경로

오른쪽 → 오른쪽 → 아래 → 아래 로만 이동하는 경우입니다.
경로: (0,0) → (0,1) → (0,2) → (1,2) → (2,2)
손해 합계: 22

5 →	5 →	4 ↓
		1 ↓
		7

더 좋은 경로

아래 → 아래 → 오른쪽 → 오른쪽 로 이동하는 경우입니다.
경로: (0,0) → (1,0) → (2,0) → (2,1) → (2,2)
손해 합계: 20

5 ↓
3 ↓
3 →	2 →	7

🔷 문제 풀이 아이디어

이 문제는 링크가 도둑루피가 가득한 동굴을 지나 최소한의 손해로 출구까지 도달하는 것이 목표입니다.
단순히 오른쪽과 아래로만 가는 것이 아니라, 더 적은 손해를 위해 되돌아가 위쪽으로 올라가거나 왼쪽으로 돌아가는 경로까지 고려해야 합니다.
이 특징 때문에, 단순히 DP로는 풀 수 없고 다익스트라를 써야 합니다.

DP(동적 계획법)의 한계

❌ DP는 현재 위치에서 오른쪽과 아래만 탐색하며 최소 손해를 계산합니다.
하지만 이 문제처럼 상하좌우 어디든 갈 수 있는 상황에서는 최적 경로를 놓칩니다.

예를 들어, 아래는 DP가 계산한 경로입니다.
모든 칸에는 원래 숫자를 표시하고, 경로를 따라간 칸에는 화살표를 붙였습니다.

3→	7→	2→	0→	1↓
2	8	0	9	1↓
1	2	1	8	1↓
9	8	9	2	0↓
3	6	5	1	5

🧾 DP 손해 합계: 20

다익스트라의 강점

✅ 다익스트라는 이미 방문한 칸이라도 더 적은 손해로 도달할 수 있다면 값을 갱신하며 탐색합니다.
상하좌우를 모두 고려하며 최적 경로를 찾기 때문에, 반드시 다익스트라를 사용해야 합니다.

아래는 다익스트라가 계산한 최적 경로입니다.

3↓	7	2→	0→	1↓
2↓	8	0↑	9	1↓
1→	2→	1↑	8	1↓
9	8	9	2	0↓
3	6	5	1	5

🧾 다익스트라 손해 합계: 19

다익스트라는 무엇인가?

다익스트라는 가장 적은 비용으로 목적지에 가는 길을 찾는 방법입니다.
원리는 간단합니다.

“지금까지 찾은 길 중에서 제일 싼 길부터 하나씩 확인해 나가면 된다.”

이렇게 하면 큐에서 꺼내는 순간, 그 칸까지 가는 최소 비용이 이미 결정됩니다.
왜냐하면 더 싼 길이 있었으면 그 길이 큐의 맨 앞에 먼저 나왔을 것이기 때문입니다.
이것이 다익스트라가 최소 비용을 보장하는 이유입니다.

다익스트라는 어떻게 움직이는가?

• 1️⃣ 시작점에서 갈 수 있는 칸들의 비용을 계산해 큐에 넣습니다.
• 2️⃣ 큐에서 가장 비용이 적은 칸을 꺼냅니다.
• 3️⃣ 그 칸에서 갈 수 있는 새로운 칸들의 비용을 계산합니다.
• 4️⃣ 더 싸게 갈 수 있으면 그 값을 새로 기록하고 큐에 넣습니다.
• 5️⃣ 이 과정을 반복하면 모든 칸을 최소 비용으로 방문하게 됩니다.

🔷 단계별 진행

🔷 0단계 — 시작

**설명**
현재 위치는 `(0,0)`이고, 지금까지 든 비용은 `5`입니다.
갈 수 있는 후보는 오른쪽 `(0,1)=5`와 아래 `(1,0)=3`입니다.
비용 계산:

• 오른쪽: `5+5=10`
• 아래: `5+3=8`

둘 중 더 싼 `8`이 있으니, `(1,0)`을 다음 탐색 대상으로 선택합니다.

**고유비용**

5★	5	4
3	9	1
3	2	7

**설명**
큐에는 `(1,0)=8`과 `(0,1)=10`이 들어 있습니다. 현재 큐의 가장 작은 값은 `8`입니다.
더 싼 길이 있었다면 큐에 먼저 나왔을 텐데 없으니, `(1,0)=8`이 최소임이 보장됩니다.

**합산비용**

5★

**설명**
현재 큐 상태: `←[ (1,0)=8 | (0,1)=10 ]←`
다음 탐색 예정: `(1,0)=8`

🔷 1단계 — (1,0)=8 선택

**설명**
현재 위치는 `(1,0)`이고, 지금까지 든 비용은 `8`입니다.
갈 수 있는 후보는 아래 `(2,0)=3`과 오른쪽 `(1,1)=9`입니다.
비용 계산:

• 아래: `8+3=11`
• 오른쪽: `8+9=17`

둘 중 더 싼 `11`이 있으니, `(2,0)`을 다음 탐색 대상으로 선택합니다.

**고유비용**

5	5	4
3★	9	1
3	2	7

**설명**
큐에는 기존의 `(0,1)=10`, 그리고 새로 발견한 `(2,0)=11`, `(1,1)=17`이 있습니다.
가장 작은 값은 여전히 `10`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로 `10`이 최소입니다.

**합산비용**

5	10
8★	17
11

**설명**
현재 큐 상태: `←[ (0,1)=10 | (2,0)=11 | (1,1)=17 ]←`
다음 탐색 예정: `(0,1)=10`

🔷 2단계 — (0,1)=10 선택

**설명**
현재 위치는 `(0,1)`이고, 지금까지 든 비용은 `10`입니다.
갈 수 있는 후보는 오른쪽 `(0,2)=4`와 아래 `(1,1)=9`입니다.
비용 계산:

• 오른쪽: `10+4=14`
• 아래: `10+9=19`

`14`가 더 작습니다. `(0,2)=14`를 큐에 넣습니다. `(1,1)=19`는 기존 `17`보다 크므로 무시합니다.

**고유비용**

5	5★	4
3	9	1
3	2	7

**설명**
큐에는 기존의 `(2,0)=11`, `(1,1)=17`, 그리고 새로 발견한 `(0,2)=14`가 있습니다.
가장 작은 값은 `11`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로 `11`이 최소입니다.

**합산비용**

5	10★	14
8	17
11

**설명**
현재 큐 상태: `←[ (2,0)=11 | (1,1)=17 | (0,2)=14 ]←`
다음 탐색 예정: `(2,0)=11`

🔷 3단계 — (2,0)=11 선택

**설명**
현재 위치는 `(2,0)`이고, 지금까지 든 비용은 `11`입니다.
갈 수 있는 후보는 오른쪽 `(2,1)=2`입니다.
비용 계산:

• 오른쪽: `11+2=13`

더 이상 아래로는 갈 수 없으니, `(2,1)=13`을 다음 탐색 대상으로 선택합니다.

**고유비용**

5	5	4
3	9	1
3★	2	7

**설명**
큐에는 기존의 `(1,1)=17`, `(0,2)=14`가 있습니다.
새롭게 발견한 `(2,1)=13`이 추가되었습니다.
큐를 보면 `13`, `14`, `17`이 있고, 가장 작은 값은 `13`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(2,1)=13`이 최소임이 보장됩니다.

**합산비용**

5	10	14
8	17
11★	13

**설명**
현재 큐 상태: `←[ (2,1)=13 | (0,2)=14 | (1,1)=17 ]←`
다음 탐색 예정: `(2,1)=13`

🔷 4단계 — (2,1)=13 선택

**설명**
현재 위치는 `(2,1)`이고, 지금까지 든 비용은 `13`입니다.
갈 수 있는 후보는 오른쪽 `(2,2)=7`입니다.
비용 계산:

• 오른쪽: `13+7=20`

다른 더 싼 후보가 없으니, `(2,2)=20`을 큐에 넣습니다.

**고유비용**

5	5	4
3	9	1
3	2★	7

**설명**
큐에는 기존의 `(0,2)=14`, `(1,1)=17`이 있습니다.
새롭게 발견한 `(2,2)=20`이 추가되었습니다.
큐를 보면 `14`, `17`, `20`이 있고, 가장 작은 값은 `14`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(0,2)=14`가 최소임이 보장됩니다.

**합산비용**

5	10	14
8	17
11	13★	20

**설명**
현재 큐 상태: `←[ (0,2)=14 | (1,1)=17 | (2,2)=20 ]←`
다음 탐색 예정: `(0,2)=14`

🔷 다익스트라 — 단계별 진행 (완결)

🔷 5단계 — (0,2)=14 선택

**설명**
현재 위치는 `(0,2)`이고, 지금까지 든 비용은 `14`입니다.
갈 수 있는 후보는 아래 `(1,2)=1`입니다.
비용 계산:

• 아래: `14+1=15`

다른 더 싼 후보가 없으니, `(1,2)=15`를 큐에 넣습니다.

**고유비용**

5	5	4★
3	9	1
3	2	7

**설명**
큐에는 기존의 `(1,1)=17`, `(2,2)=20`이 있습니다.
새롭게 발견한 `(1,2)=15`이 추가되었습니다.
큐를 보면 `15`, `17`, `20`이 있고, 가장 작은 값은 `15`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(1,2)=15`가 최소임이 보장됩니다.

**합산비용**

5	10	14★
8	17	15
11	13	20

**설명**
현재 큐 상태: `←[ (1,2)=15 | (1,1)=17 | (2,2)=20 ]←`
다음 탐색 예정: `(1,2)=15`

🔷 6단계 — (1,2)=15 선택

**설명**
현재 위치는 `(1,2)`이고, 지금까지 든 비용은 `15`입니다.
갈 수 있는 후보는 아래 `(2,2)=7`입니다.
비용 계산:

• 아래: `15+7=22`

하지만 큐에 이미 `(2,2)=20`으로 기록돼 있고, `20 < 22`이므로 무시합니다.

**고유비용**

5	5	4
3	9	1★
3	2	7

**설명**
큐에는 기존의 `(1,1)=17`, `(2,2)=20`이 있습니다.
가장 작은 값은 `17`입니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(1,1)=17`이 최소임이 보장됩니다.

**합산비용**

5	10	14
8	17	15★
11	13	20

**설명**
현재 큐 상태: `←[ (1,1)=17 | (2,2)=20 ]←`
다음 탐색 예정: `(1,1)=17`

🔷 7단계 — (1,1)=17 선택

**설명**
현재 위치는 `(1,1)`이고, 지금까지 든 비용은 `17`입니다.
갈 수 있는 후보는 아래 `(2,1)=2`와 오른쪽 `(1,2)=1`입니다.
하지만 `(2,1)=13`과 `(1,2)=15`가 이미 더 작은 비용으로 기록돼 있으므로, 아무것도 갱신되지 않습니다.

**고유비용**

5	5	4
3	9★	1
3	2	7

**설명**
큐에는 이제 `(2,2)=20`만 남아 있습니다.
더 싼 길이 있었다면 이미 큐에 있었어야 하므로, `(2,2)=20`이 최소임이 보장됩니다.

**합산비용**

5	10	14
8	17★	15
11	13	20

**설명**
현재 큐 상태: `←[ (2,2)=20 ]←`
다음 탐색 예정: `(2,2)=20`

🔷 8단계 — (2,2)=20 선택

**설명**
현재 위치는 `(2,2)`이고, 지금까지 든 비용은 `20`입니다.
목적지에 도달했으므로 탐색을 종료합니다.

**고유비용**

5	5	4
3	9	1
3	2	7★

**설명**
이제 큐가 비었고, 목적지까지 최소 비용 `20`으로 도달했습니다.
이 과정에서 매 단계마다 큐에서 가장 작은 값부터 탐색했고, 더 싼 길이 있었다면 그 순간 큐에 나타났을 것이므로 최소임이 증명됩니다.

**합산비용**

5	10	14
8	17	15
11	13	20★

**설명**
최종 최소 비용: `20`

전체코드

#include <iostream>
#include <cstring>
#include <queue>


using namespace std;

struct Node{
    int x;
    int y;
    int cost;
    
    bool operator<(const Node& node) const
    {
        return cost>node.cost;
    }
    
};

int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};

int main(void)
{
    
    int N,cnt=0;
    
    while(true)
    {
        cin>>N;
        if(N==0)
            break;
        cnt++;
        int arr[125][125]={0};
        int dis[125][125];
        priority_queue<Node> q;
        
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
                cin>>arr[i][j];
        }
        
        
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
                dis[i][j]=21000000;
        }
        dis[0][0]=arr[0][0];
        q.push({0,0,arr[0][0]});
        while(!q.empty())
        {
            int x=q.top().x;
            int y=q.top().y;
            int cost=q.top().cost;
            q.pop();
            
            for(int i=0;i<4;i++)
            {
                int nx=x+dx[i];
                int ny=y+dy[i];
                
                if(nx<0 || nx>=N || ny<0|| ny>=N)
                    continue;
                
                int next_cost=cost+arr[nx][ny];
                
                if(next_cost<dis[nx][ny])
                {
                    dis[nx][ny]=next_cost;
                    q.push({nx,ny,next_cost});
                }
            }
            
        }
        cout<<"Problem "<<cnt<<": "<<dis[N-1][N-1]<<endl;
    }

    return 0;
}

개별 코드 설명 및 보강

1. struct Node

struct Node{
    int x;
    int y;
    int cost;
    
    bool operator<(const Node& node) const
    {
        return cost > node.cost;
    }
};

• Node 구조체는 탐색 대상인 2차원 배열 내 위치를 나타내는 좌표 (x, y)와, 그 위치까지 도달하는 데 필요한 누적 비용 cost를 저장합니다.
• 이 구조체를 우선순위 큐에 넣어 최소 비용부터 처리하기 위해 비교 연산자를 오버로딩하였습니다.
• 오버로딩된 < 연산자는 비용이 작은 값이 우선순위 큐에서 먼저 나오도록 cost > node.cost 형태로 구현합니다.
• 이렇게 하면 최소힙(min-heap) 역할을 하게 되어, 항상 가장 비용이 적은 노드를 먼저 처리할 수 있습니다.
• 우선순위 큐의 기본 동작이 최대힙이기 때문에, 비용이 더 큰 노드가 우선순위가 낮도록 반대로 비교하는 것이 필요합니다.

2. 배열 선언

int arr[125][125] = {0};
int dis[125][125];

• arr 배열은 각 칸마다 존재하는 개별 비용(도둑루피 크기)를 저장하는 배열입니다.
• 입력값으로 초기화되며, 탐색 대상 동굴의 구조와 비용을 나타냅니다.
• dis 배열은 현재까지 발견한 해당 칸까지 도달하는 최소 누적 비용을 저장합니다.
• 탐색 진행 중에 지속적으로 갱신되며, 최종적으로 출구까지 도달하는 최소 비용을 찾는 데 사용됩니다.

3. 초기 설정 및 탐색 시작

dis[0][0] = arr[0][0];
q.push({0, 0, arr[0][0]});

• 출발 지점인 (0,0) 위치의 비용을 dis에 초기화합니다.
• 이 값은 처음 탐색의 시작점이 되며, 큐에 넣어 탐색을 시작할 준비가 되었다는 의미입니다.
• 우선순위 큐는 이 노드를 기반으로 최소 비용 경로 탐색을 시작합니다.

4. 큐가 빌 때까지 반복

while (!q.empty())

• 큐가 비어있다는 것은, 탐색해야 할 후보 위치가 더 이상 없음을 뜻합니다.
• 즉, 모든 가능한 경로를 확인했고, 최소 비용 경로를 찾았다는 의미입니다.
• 따라서 이 반복문은 아직 탐색할 노드가 남아 있는 동안 계속 실행됩니다.

5. 현재 최소 비용 노드 꺼내기

int x = q.top().x;
int y = q.top().y;
int cost = q.top().cost;
q.pop();

• 큐의 맨 위에 있는 노드를 꺼내 현재 위치 (x, y)와 그 위치까지 도달하는 비용 cost를 가져옵니다.
• 이 노드는 지금까지 발견한 경로 중 비용이 가장 적은 위치를 의미합니다.
• 큐에서 꺼낸 후, 그 위치를 기준으로 다음 위치 탐색을 진행합니다.

6. 상하좌우 4방향 탐색 및 유효성 검사

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

    if (nx < 0 || nx >= N || ny < 0 || ny >= N)
        continue;

• 현재 위치에서 상하좌우 네 방향을 모두 탐색하기 위해 반복문을 사용합니다.
• 각 방향으로 이동했을 때의 좌표 (nx, ny)를 계산합니다.
• 이동한 위치가 배열 범위를 벗어나면, 탐색하지 않고 건너뜁니다.
• 이렇게 범위를 벗어나는 경우를 걸러내어, 불필요한 오류와 탐색을 막습니다.

7. 다음 위치의 누적 비용 계산

int next_cost = cost + arr[nx][ny];

• 다음 위치 (nx, ny)까지 도달하는 데 드는 누적 비용을 계산합니다.
• 현재 위치까지의 비용 cost에 다음 위치의 비용 arr[nx][ny]를 더합니다.
• 이 값은 다음 위치까지 가는 경로의 새로운 비용 후보가 됩니다.

8. 더 적은 비용으로 갱신 및 큐에 추가

if (next_cost < dis[nx][ny])
{
    dis[nx][ny] = next_cost;
    q.push({nx, ny, next_cost});
}

• 만약 계산한 누적 비용 next_cost가 현재 기록된 비용 dis[nx][ny]보다 작으면,
• 해당 위치까지 도달하는 비용을 더 적은 값으로 갱신합니다.
• 그리고 이 위치를 우선순위 큐에 추가하여, 추후에 다시 이 위치를 기준으로 더 나은 경로를 찾을 기회를 만듭니다.
• 이 과정이 다익스트라 알고리즘의 핵심으로, 이미 방문한 위치라도 더 좋은 비용으로 도달 가능하다면 갱신하고 재탐색하는 방식입니다.

결론

• 이 알고리즘은 단순히 한 번 방문한 칸을 다시 방문하지 않는 것이 아니라,
• 더 낮은 비용으로 해당 칸에 도달할 수 있으면, 비용을 갱신하고 다시 큐에 넣어 더 나은 경로를 찾아가는 유연한 탐색 방식입니다.
• 우선순위 큐가 최소 비용 노드를 먼저 꺼내 처리하기 때문에, 항상 비용이 작은 경로부터 확정해 나가면서 효율적으로 최소 비용 경로를 찾습니다.
• 이 점이 다익스트라 알고리즘의 본질이며, 그리디한 접근임에도 전체 경로 최적해를 보장하는 이유입니다.