[백준][C++] 4485번: 녹색 옷 입은 애가 젤다지? 풀이

 

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

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

 

(0,0)에서 출발해 (N-1,N-1)까지 갈 수 있는 경로 중 최소 비용을 구하는 문제이다.

 

모든 경로를 탐색해야 하기도 하고 최대 크기가 125X125으로 다 도는데 얼마 안 걸리겠다 싶어 완전 탐색으로 풀어보았다.

 

먼저 필요한 자료구조로는 

1. 동굴을 저장할 2차원 배열

2. 각 좌표로 갈 수 있는 최소 비용을 저장할 2차원 배열

3. 좌표를 넣을 큐

 

풀이로직으로는

1. (0,0)을 큐에 삽입

2. 큐에서 꺼낸 좌표와 인전합 좌표들을 돌아 좌표까지 가는 최소 비용이 갱신이 되면 갱신이 된 좌표를 큐에 삽입

-> 최소 비용이 아닌 경로는 굳이 탐색할 필요가 없기에

3. 큐가 빌 때까지 1,2번 반복

 

#include <iostream>
#include <queue>

using namespace std;

int map[126][126];
int d[126][126];
int n;

// 상 하 좌 우 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void bfs() {
	queue<pair<int, int>> q;
	// 1.(0,0)부터 시작 
	q.push(make_pair(0,0));
	d[0][0] = map[0][0];
	// 3. 큐가 빌 때까지 
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		// 2. 상하좌우 인접한 좌표 
		for(int i=0; i<4; i++) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];
			if(next_x<0 || next_x>=n || next_y<0 || next_y>=n) continue;
			// 2. 최소 거리가 갱신되면 큐에 삽입 
			if(d[next_x][next_y] > d[x][y] + map[next_x][next_y]) {
				d[next_x][next_y] = d[x][y] + map[next_x][next_y];
				q.push(make_pair(next_x, next_y));
			}
		}
	}
}

int main(void) {
	int num;
	
	while(true) {
		cin >> n;
		if(n==0) break;
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				d[i][j] = 999;
				cin >> map[i][j];
			}
		}
		num++;
		
		bfs();
		
		printf("Problem %d: %d\n", num, d[n-1][n-1]);
	}
}

 

 

맵 좌표의 비용이 0~9이기에 다익스트라로도 풀 수 있다 한다.

다음 풀이 돌 때는 다익스트라로도 풀어보자.