문제 출처

1. 문제설명

  • 동굴의 크기 N
  • N*N 크기의 맵에는 0~9까지의 가중치가 존재한다.
  • (1,1)에서 시작해 (N,N)까지의 최단 경로를 구하라



2. 알고리즘 설계

  • 가중치가 음수가 없으면서 여러개라면?
  • 다익스트라



3. 로직

  • priority_queue를 사용해 BFS 방식으로 탐색하면 된다.
  • 가중치가 적은 순서대로 pq의 앞에 쌓는다.
  • 탐색 도중 N, N을 만나면 현재까지의 weight를 출력한다.
  • 구현의 편의상 (0,0) ~ (N-1,N-1)까지로 설정하였다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 125;
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
int n;
int arr[SZ][SZ];
bool visited[SZ][SZ];


int bfs(void)
{
	priority_queue<tuple<int,int,int>> pq;
	pq.push({ -arr[0][0], 0, 0 });
	visited[0][0] = true;

	while (!pq.empty()) {
		auto cur = pq.top();
		pq.pop();

		int cy = get<1>(cur);
		int cx = get<2>(cur);
		int w = get<0>(cur);

		if (cy == n - 1 && cx == n - 1)
			return w;

		for (int dir = 0; dir < 4; dir++) {
			int ny = cy + dy[dir];
			int nx = cx + dx[dir];

			if (ny < 0 || nx < 0 || ny >= n || nx >= n)
				continue;
			if (!visited[ny][nx]) {
				pq.push({ w - arr[ny][nx], ny, nx });
				visited[ny][nx] = true;
			}
		}
	}
}

int main(void) 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

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

		fill_n(&arr[0][0], SZ * SZ, 0);
		fill_n(&visited[0][0], SZ * SZ, false);

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

		cout << "Problem " << i++ << ": " << - bfs() << '\n';
	}
	return 0;
}



5. 소감

  • tuple
    • 세가지 자료형을 담는 자료구조

    • 접근 방법

      tuple<int,int,int> Tuple;
	
get<0>(Tuple);  // 나머지 두개는 1, 2로 접근
auto [a, b, c] = Tuple  // 한번에 값 가져오는 방법
  • 굳이 tuple을 사용한 이유
    • 예전에 언급했었는데, 구조체를 사용하면 operator까지 직접 구현해야 한다.
    • pair, tuple 등을 사용하면 가장 앞에 있는 인자값 기준으로 정렬되어 삽입된다.
      • pair는 first, tuple은 0번째 값 기준
  • 전체 코드에서 볼 수 있듯이 음수값으로 값을 저장한다.
    • pq는 default가 max_heap으로, 큰 값을 기준으로 정렬된다.
    • ’~’를 씌운 값을 넣으면 min_heap의 효과가 있다.
  • 해당 문제는 weight가 0~9사이의 값이다.
    • 이렇게 weight 개수가 적은 경우 다이얼 알고리즘을 사용하면,
    • 속도 측면에서 이득을 챙길 수 있다고 한다.