개요

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

• 입력
  입력은 여러 개의 테스트 케이스로 이루어져 있다.

  각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

  이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

• 출력
  각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

접근 방식

1. 맨처음 생각했던 방식은 DFS이다. DFS방식으로 [0,0]에서 상하좌우를 탐색하며 해당 좌표까지의 최소 손실값이 현재 좌표를 거쳐서 손실 나는 총합보다 크면 현재좌표를 거치는 방식으로 갱신하는 식으로 짰다.

2. 하지만 역시나 답이 틀리게 나왔다.
   최단거리인 경우일때 계산이 아니라 그냥 순차적으로 상하좌우일때 다 계산하며 진행하다보니 의도치 않은 방향으로 갱신하며 끝나버린 것이였다.

3. 따라서 우선순위큐를 이용한 다익스트라 알고리즘을 이용해,
   각 노드의 손실값을 그래프의 가중치로 생각을 하여 ,
   [N-1,N-1]에 도달했을 때, 최저 손실을 찾게 만들면 된다.

4. 각 노드의 손실값을 그래프의 가중치로 두고 풀었으므로,
   [0,0]에서의 손실값은 미리 Loss배열과 우선순위큐에 넣어주고 시작을해야한다.

전체 코드

#include<iostream>
#include<queue>

using namespace std;
int N,INF=10'000;
//처음 입력값 배열
int Cave[126][126];
//0,0에서 최저로 잃는 코인
int Loss[126][126];
//방문 여부 처리
bool visited[126][126];

//Loss, 좌표는 x*N+y로 저장
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int dirX[4] = {-1,1,0,0};
int dirY[4] = {0,0,-1,1};

//Loss배열에 각 칸까지의 최저 손실 저장하는 함수
void SetLoss() {

	while (!pq.empty()) {
		//priority Queue. second값에는 각 칸의 정보를 N*행+열로 저장해서 썼다.
		int curNodeX = pq.top().second / N;
		int curNodeY = pq.top().second % N;
		pq.pop();
		//top값이 방문한 칸이라면 방문안한 칸 나올때까지 반복
		while (!pq.empty() && visited[curNodeX][curNodeY]) {
			int curNodeX = pq.top().second / N;
			int curNodeY = pq.top().second % N;
			pq.pop();
		}

		//방문안한 칸이므로 방문 처리
		visited[curNodeX][curNodeY] = true;

		//상하좌우 체크용
		for (int i = 0; i < 4; i++) {
			//좌표 x,y값 상하좌우에 맞게 변형
			int nextX = curNodeX + dirX[i];
			int nextY = curNodeY + dirY[i];

			//0~N-1을 벗어난다면 continue
			if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
			//이미 방문한 칸이라면 continue
			if (visited[nextX][nextY]) continue;

			//[nextX,nextY]칸의 최저 손실보다 [curNodeX, curNodeY]칸을 거쳐 [nextX,nextY]에 도달하는 손실이 더 작다면 갱신
			if (Loss[nextX][nextY] > Loss[curNodeX][curNodeY] + Cave[nextX][nextY]) {
				Loss[nextX][nextY] = Loss[curNodeX][curNodeY] + Cave[nextX][nextY];
				pq.push({ Loss[nextX][nextY], nextX * N + nextY });
			}
		}
	}
}

void Input() {
	int testCase = 1;
	while (1) {
		//매 테케마다 초기화
		fill(&Loss[0][0], &Loss[125][125], INF);
		fill(&Cave[0][0], &Cave[125][125], 0);
		fill(&visited[0][0], &visited[125][125], false);
		cin >> N;
		if (N == 0) return;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				cin >> Cave[i][j];
			}
		}
		//각 칸의 손실값을 그래프의 가중치로 생각했으므로 \
		0,0 칸의 손실값을 미리 저장하고 진행해야함
		Loss[0][0] = Cave[0][0];
		pq.push({ Cave[0][0],0 });
		SetLoss();
		cout << "Problem "<<testCase++<<": " << Loss[N - 1][N - 1]<<'\n';
	}
}

int main() {
	Input();
}

문풀후생

처음에 이 문제를 못 푼 이유는 다름아닌 우선순위 큐의 pair원소의 second값 설정을 잘못했다.

그냥 단순하게 2차원벡터의 행렬을 나타낼때 행*10+열로 생각해서
10을 나누고 나머지를 구하고 10을 곱해서 저장을 하는식으로 구현했다가
틀리고 원인을 다른데서 찾다가 시간을 많이 날렸다.

3x3 배열일때, [2][2]칸은 2*3 행 2 열로 저장이 되어야하는데
10으로 계산해버리면 10*2행 2열로 저장이되어
3x3배열을 넘어가서 쓰레기값을 불러온다
행*N+열의 형태로 저장을 해야한다!