[백준] 4485 – 녹색 옷 입은

문제

4485번: 초록색이 젤다죠? (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;
}