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

++ 22.11.23 갱신

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

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

#include <cstdio>
#include <queue>
#include <cstring>
int N;
int board[125 + 2][125 + 2];

struct _st
{
	int x, y;
	int rupee;
};

struct COMP
{
	bool operator()(const _st &a, const _st &b)
	{
		return a.rupee > b.rupee;
	}
};
std::priority_queue<_st, std::vector<_st>, COMP> PQ;
int visited[125 + 2][125 + 2];


void input(int N)
{
	// init
	memset(board, 0, sizeof(board));
	PQ = {};

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
		}
	}
}


int BFS()
{
	//dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	// init
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j] = 0x7fffffff;
		}
	}
	PQ.push({ 0, 0, board[0][0] });
	visited[0][0] = 0;

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.x == N - 1 && data.y == N - 1) return visited[N - 1][N - 1];

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny] <= data.rupee + board[nx][ny]) continue;
			PQ.push({ nx, ny, data.rupee + board[nx][ny] });
			visited[nx][ny] = data.rupee + board[nx][ny];
		}
	}
	return -1;
}




int main()
{
	for (int t = 1; ;t++){
		scanf("%d", &N);
		if (N == 0) break;
		input(N);
		int ans = BFS();
		printf("Problem %d: %d\n",t, ans);
	}
	return 0;
}

1. 각 칸까지 가는데 잃는 도둑루피의 수가 다르기 때문에 우선순위 큐를 사용한다. 

2. 우선순위 큐 사용할 때 해당 칸 까지 가는 "최소 (거리 / 시간/ cost ...)"를 따져주어야 하므로 방문 배열은 무한대로 초기화 해준다. 

3. 현재 상태(data.rupee + board[nx][ny])가 이전 상태(visited[nx][ny]) 보다 더 나은 경우(cost가 더 적은 경우)에만 방문 배열을 갱신해준다. 

---

이전 풀이 및 자세한 설명..

#include <cstdio>
#include <queue>
int N;
int z_map[125 + 2][125 + 2];	// 입력받을 도둑루피맵
int chk[125 + 2][125 + 2];		// 잃는 도둑루피맵

struct _st
{
	int x;	// x좌표	
	int y;	// y좌표
	int r;	// 루피수
};

std::queue<_st> Q;	// 상태 체크할 큐


int BFS(void)
{
	int dir_x[4] = { 0, 0, 1, -1 };	// 방향벡터 
	int dir_y[4] = { 1, -1, 0, 0 };	// 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다. 
	
	// 초기상태
	Q.push({ 0, 0, z_map[0][0] });
	chk[0][0] = z_map[0][0];


	// 발전
	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];
            		// 이동할 좌표가 범위를 벗어나면 통과한다. 
			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;	
			
			int nr = chk[data.x][data.y] + z_map[nx][ny]; // 잃는 루피의 크기 비교
			if (chk[nx][ny] <= nr) continue;	// 만약 그전에 판단했던 최선의 결과보다 크거나 같으면 갱신해줄 필요가 없다
			chk[nx][ny] = nr;
			//printf("%d %d %d\n", nx, ny, nr);
			Q.push({ nx, ny , nr });
		}
	}
	return chk[N - 1][N - 1];	// (N - 1, N - 1) 좌표에서 최소 얼마를 잃는지 리턴한다.
}


void init(void)
{
	Q = {};	// 큐 초기화
	for (int i = 0; i < 125 + 2; i++) {
		for (int j = 0; j < 125 + 2; j++) {
			z_map[i][j] = 0;		// 맵초기화
			chk[i][j] = 0x7fffffff;	// 체크배열 초기화
		}
	}
}



int main()
{
	int num = 1;
	while (1) {
		scanf("%d", &N);
		if (N == 0) break;
		init();
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				scanf("%d", &z_map[i][j]);
			}
		}
		int ans = BFS();
		printf("Problem %d: %d\n", num, ans);
		num++;
	}
	return 0;
}

이 문제는 "링크가 잃을 수 밖에 없는 최소 금액"을 찾아야하기 때문에 BFS 를 사용한다. 

 

 

// main( ), init( ) 함수

먼저 테스트케이스가 여러 개일때 가장 중요한 것은 "초기화"이다. 

도둑 루피만 가득한 N * N 행렬에 대한 정보를 입력받기 전에 z_map을 0으로 초기화 한다. 또한 각 좌표로 가기까지 최소 금액을 누적해 놓을 chk배열을 아주 큰 수(int 범위에서 가장 큰 수 : 0x7fffffff)로 초기화 한다. 

 

 

// BFS ( ) 함수

먼저 초기 상태인 (0, 0) 좌표와 해당 위치에서 읽는 도둑 루피의 크기를 큐에 삽입한다. 

그리고 while 루프를 통해 큐에 있는 데이터를 하나씩 꺼내어, 동서남북 인접한 방향으로 전진할 수 있는지 탐색한다.

만약 전진할 좌표 (nx, ny)가 맵의 범위를 벗어나면 아무런 수행을 하지 않고 통과한다. 범위 안의 좌표라면 "잃을 수 밖에 없는 링크 수(nr)"를 계산한다. int nr = chk[data.x][data.y] + z_map[nx][ny] 에서 chk[data.x][data.y]는 전진 직전의 좌표까지 오면서 잃는 루피의 최소값이다. 여기에 더해주는 z_map[nx][ny]는 전진할 좌표에서 잃는 루피의 양이다. 

이렇게 계산한 nr을 chk[nx][ny]의 값과 비교하여 만약 (chk[nx][ny] <= nr)이면, 해당 경로가 아닌 다른 경로로 (nx, ny)좌표에 도달했을 때 최소값을 도출할 수 있다는 의미이므로 아무런 수행도 하지 않는다. 반면 (chk[nx][ny] > nr) 이면 (nx, ny) 좌표에 도달했을 때의 새로운 최소값이 도출되었다는 의미이므로 chk[nx][ny]의 값을 nr로 갱신시켜준다. 

그리고 {nx, ny, nr}을 큐에 삽입하여 다음 좌표를 탐색한다. 

 

중간에 (nx == N - 1 && ny == N - 1)일때 바로 최소값을 리턴하지 않는 이유는, 여러 경로로 (N - 1, N - 1) 좌표에 도달할 수 있고 그때마다 최소값의 후보가 생길 수 있기 때문이다. 따라서 큐에 있는 원소가 없어질 때 까지 while루프를 진행하고, 끝나면 chk배열의 (N - 1, N - 1) 값을 리턴해준다.