[백준 4485] - 녹색 옷 입은 애가 젤다지?(C++)

📕문제

---

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑 루피'라 불리는 검은색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0] 번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤 다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑 루피가 있는데, 이 칸을 지나면 해당 도둑 루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

📕입력

---

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑 루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

📕출력

---

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

 

🔎문제 풀이

• 도착지점까지 최소한의 값을 방문하는 문제이다.
• 나는 BFS를 이용해서 풀었다. 초기에는 priority_queue를 이용해서 풀었다.
  • pq에는 이때까지 축적된 값과 행렬 좌표를 넣었다.
  • pq는 축적된 값의 오름차순으로 정렬된다.
  • 그래서 가장 최적의 루트를 방문하게끔 만들었다.
• 잘못된 풀이방식..?
  • 메모리 초과 발생
  • 내 생각보다 pq가 메모리를 많이 잡아먹은것 같다.

💡수정된 풀이 방식

• 기존 풀이 방식과 거의 유사하지만 pq를 사용하지 않고, q를 사용, 이동한 좌표의 최소값[visit배열]을 갱신해줬다.
• 변수선언
  • graph : 입력 행렬
  • visit : 루피를 저장하는 배열
  • q에는 {X,Y}좌표가 들어감.
• visit 배열을 INT_MAX로 초기화한뒤[최소값을 저장하기 위함] 출발점에 해당하는 visit값을 출발점에 해당하는 루피 값으로 업데이트 해줬다.
  • visit[0][0]= graph[0][0]
• BFS진행
  • q가 완전히 empty될때까지 진행
  • 상하좌우로 탐색
    • 적절한 이동이 아니라면 pass
    • 적절한 이동이라면 visit 배열을 비교
      • 이동하려는 좌표 (tempx,tempy) / 기존 좌표 (fx,fy)
      • visit[tempx][tempy]값 (그 좌표까지 이동하는데 축적된 루피값) vs visit[fx][fy] (기존 좌표까지 이동하는데 축적된 루피값) + graph[tempx][tempy] (이동 좌표에 저장된 루피값) 을 비교한다.
        • visit[tempx][tempy] > visit[fx][fy] + graph[tempx][tempy] 라면 값을 갱신해주고 q에 넣어준다.
        • 위의 경우가 아니라면 q에 갱신할 필요가 없다.
• BFS가 끝나면 visit[n-1][n-1]에는 (n-1,n-1)까지 가는데 저장된 최소한의 루피값이 들어가게 된다.

💻코드

/*
골드4 4485 녹색 옷 입은애가 젤다지?
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <limits.h>
using namespace std;
int n,answer;
vector<vector<int>> graph;
vector<vector<int>> visit;
vector<int> result;
vector<int> x = {1, -1, 0, 0};
vector<int> y = {0, 0, 1, -1};
void print_result();
void bfs();
int main()
{
    while (1)
    {
        cin >> n;
        if (n == 0) //종료 조건
        {
            print_result(); //출력 형식 출력 
            break;
        }
        graph.assign(n, vector<int>(n, 0)); //입력 행렬 초기화
        visit.assign(n, vector<int>(n, INT_MAX)); //잃는 금액 배열 최신화
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> graph[i][j];
            }
        }
        visit[0][0]=graph[0][0]; //초기 출발 지점 금액 
        bfs();
    }
}
void print_result()
{
    for (int i = 0; i < result.size(); i++)
    {
        cout << "Problem " << i+1 << ": " << result[i] << endl;
    }
}
void bfs()
{    
    queue<pair<int,int>>pq;
    pq.push(make_pair(0, 0)); //초기 출발점 push
    while (!pq.empty())
    {
        int fx= pq.front().first;
        int fy=pq.front().second;
        // x,y 좌표 추출
        pq.pop();
        for (int i = 0; i < 4; i++)
        {
            int tempx = fx + x[i];
            int tempy = fy + y[i];
            if (tempx >= n || tempy >= n || tempx < 0 || tempy < 0)
            {
                continue;
            }
            if (visit[tempx][tempy] > visit[fx][fy]+graph[tempx][tempy]) //계속해서 갱신해주기.
            {
                pq.push(make_pair(tempx,tempy));
                visit[tempx][tempy] = visit[fx][fy]+graph[tempx][tempy];
            }
        }
    }
    result.push_back(visit[n-1][n-1]);
}

 

✔느낀점

• pq가 생각보다 메모리를 많이 잡아먹는다는 사실을 알게 되었다. 
• 내가 원하는 기준으로 정렬해주는 pq를 사용하고 싶지만, 메모리 초과로 그냥 수작업으로 계속 갱신해줬다.
• 출력 형식도 맞추기 까다로웠다. 공백 하나 차이로 출력 오류라닝..
• 만약 50%에서 틀린다면 예시로 주어지는 테스트 케이스만 정답처리된 것이니 아예 다시 짜기를..
• 녹색 옷 입 은애가 젤다인 줄 알았는데 아녔구나 ㅎㅋ