[백준] 4485 – 녹색 옷 입은

문제

4485번: 초록색이 젤다죠? (acmicpc.net)

4485번: 초록색이 젤다죠?

'추천 관련글,

• 

  BOJ #2623: 음악 프로그램

• 

  (자바) 문제 세트 3

• 

  [운영체제] Virtual

• 

  덕유산

젤다의 전설 게임의 통화 단위는 루피입니다.

그러나 때때로 “도둑 루피”라는 검은색 루피가 있으며 이 루피를 획득하면 실제로 소유한 루피의 양이 줄어듭니다!
젤다의 전설 시리즈의 제왕

www.acmicpc.net

설명

BFS, 최저 비용을 활용하는 것이 전부입니다.

이것은 경로 찾기 문제이므로 dx 및 dy 배열을 생성했는지 확인하여 진행합니다.

여기서 포인트는 바로 다음 자리(nx, ny)의 숫자가 큰지 작은지를 비교하는 것입니다.

Dijkstra의 알고리즘(Dijkstra)도 사용할 수 있지만 여기서는 다루지 않습니다.

#include <iostream>
#include <queue>
using namespace std;

int N;
int graph(126)(126);
int dist(126)(126);

void bfs() {
	queue <pair<int, int>> q;

	q.push({0, 0});
	dist(0)(0) = graph(0)(0);
    
	while (!
q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

                int dx(4) = {0, 0, -1, 1};
                int dy(4) = {1, -1, 0, 0};
        
		for (int i = 0; i < 4; i++) {
		    int nx = x + dx(i);
			int ny = y + dy(i);

			if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
				if (dist(ny)(nx) > dist(y)(x) + graph(ny)(nx)) {
					dist(ny)(nx) = dist(y)(x) + graph(ny)(nx);
					q.push({ny, nx});
				}
			}
		}
	}
}

int main() {
	for (int n = 1; n <= 125; n++) {
		cin >> N;
		if (N == 0)
			break;

		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++) {
				cin >> graph(i)(j);
				dist(i)(j) = 2e9;
			}
		
		bfs();
		cout << "Problem " << n << ": " << dist(N-1)(N-1) << "\n";
	}

	return 0;
}