[백준] 4485 녹색 옷 입은 애가 젤다지?

문제 설명

링크가 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 할 때, 잃을 수 있는 최소 금액을 return

https://www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

 

문제 풀이법

bfs를 통해 문제를 풀면된다

 

map을 담아놓을 배열 board, 그리고 최소 소지금을 담을 배열 arr가 필요하다

큐를 사용해 bfs를 돌리는 것은 똑같으나 주의해야할 조건문은 링크가 최소 금액으로 통과해야하기 때문에 매번 '최소'가 되는 값을 찾아서 업데이트 해주어야 한다

 

최소 금액을 업데이트하면서 큐에 더이상 값이 남아 있지않으면 맵의 끝까지 간 것이므로 맵 끝에 있는 값을 출력해주면 된다

 

 

소스 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <limits.h>
#include <cstring>

using namespace std;

int board[126][126];
int arr[126][126];

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

void init(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = 0;
            arr[i][j] = INT_MAX;
        }
    }
}

void bfs(int n) {

    queue<pair<int, int>> q;

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

    while(!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;

        q.pop();

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

            if (ny < 0 || nx < 0 || ny >= n || nx >= n)
                continue;
            
            if (arr[ny][nx] > arr[y][x] + board[ny][nx]) {
                arr[ny][nx] = arr[y][x] + board[ny][nx];
                q.push({ny, nx});
            }
        }
    }

}


int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int idx = 1;
    
    while (1) {
        int n;
        cin >> n;

        if (n == 0)
            break;

        init(n);
        
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                cin >> board[i][j];
        }

        bfs(n);

        cout << "Problem " << idx << ": " << arr[n - 1][n - 1] << endl;

        idx++;
    }

}