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

문제링크: https://www.acmicpc.net/problem/4485

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

최단거리를 도출하는 문제입니다. 

 

접근방식

 

1. 일반적인 bfs 방식과 다익스트라 방식 2가지를 생각함

3. 수의 범위가 125*125로 비교적 작기 때문에 둘다 가능할 것이라고 생각함

결과적으로 둘다 ok! 다익스트라가 4ms bfs가 8ms

4. 전형적인 방식으로 구현하자!

 

문제풀이 

 

1. 우선 bfs로 구현함

일반적인 bfs 방식으로 구현이 가능

2. 다익스트라 방식은 dist배열을 생성하고 가장 작은 cost값들을 pop하면서 진행

3. 코드가 간결하니 코드를 보고 이해하는게 빠를 듯

 

아래는 bfs 방식 정답 코드

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

int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[130][130];
int dist[130][130];

void bfs() {

	queue <pair<int, int>> pq;

	pq.push(make_pair(0, 0));
	dist[0][0] = arr[0][0];
    
	while (!pq.empty()) {
		
		int y = pq.front().first;
		int x = pq.front().second;
		pq.pop();

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

			if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
				if ( dist[ny][nx] > dist[y][x] + arr[ny][nx]) {
					dist[ny][nx] = dist[y][x] + arr[ny][nx];
					pq.push(make_pair(ny, nx));
				}
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int cnt = 1;

	while (1) {
		cin >> n;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
				dist[i][j] = 2000000000;
			}
		
		bfs();
		cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
	}

	return 0;
}

 

 

아래는 다익스트라 알고리즘 방식

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

typedef struct {
	int y;
	int x;
}p;

int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[125][125];
int dist[125][125];

void dijkstra() {

	priority_queue <pair<int, pair<int, int>>> pq;
	pq.push(make_pair(-1 * arr[0][0], make_pair(0, 0)));
	dist[0][0] = arr[0][0];

	while (!pq.empty()) {
		//int cost = pq.top().first * -1;
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		pq.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + y_ar[i];
			int nx = x + x_ar[i];
			int ncost = arr[ny][nx];

			if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
				int before_v = dist[ny][nx];
				int current_v = dist[y][x] + ncost;
				if (before_v > current_v) {
					dist[ny][nx] = current_v;
					pq.push(make_pair(-1 * current_v, make_pair(ny, nx)));
				}
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int cnt = 1;

	while (1) {
		cin >> n;
		if (n == 0)
			break;

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
				dist[i][j] = 2000000000;
			}

		dijkstra();
		cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
		
	}


	return 0;
}