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

🔒[문제 url]

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

🔑알고리즘

각 지점의 rupee 갯수를 기준으로 한 Dijkstra를 진행한다.
이를 위해 탐색시 사용할 priority_queue의 정렬 기준을 만든다.

🐾부분 코드

struct Pos
{
	int rupee;
	int x;
	int y;
};
struct comp
{
	bool operator()(Pos a,Pos b)
	{
		if(a.rupee==b.rupee)
		{
			if(a.x==b.x) return a.y < b.y;
			return a.x < b.x;
		}
		return a.rupee < b.rupee;
	};
};

<구조체 선언 및 정렬 기준 설정>
rupee의 갯수와 좌표계를 담은 구조체를 선언하고, priority_queue의 정렬 기준또한 설정한다.

void ijk()
{
	priority_queue<Pos,vector<Pos>,comp> pq;
	pq.push({ -map[0][0],0,0 });
	dist[0][0] = map[0][0];

	while(!pq.empty())
	{
		int x = pq.top().x;
		int y = pq.top().y;
		int c1 = -pq.top().rupee;
		pq.pop();

		for(int i = 0; i < 4; i++)
		{
			int nx = x + dir[i].first;
			int ny = y + dir[i].second;
			int c2 = map[nx][ny] + c1;
			if(!(0<=nx&&nx<n&&0<=ny&&ny<n)) continue;

			if(dist[nx][ny] > c2)
			{
				dist[nx][ny] = c2;
				pq.push({-c2,nx,ny});
			}
		}
	}
}

<Dijkstra 함수>
(0,0)을 시작으로 Dijkstra를 진행한다.

void SOLVE()
{
	int tc = 1;
	while(cin >> n)
	{
		if(!n) break;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				cin >> map[i][j],
				dist[i][j] = 2e9;

		ijk();
		cout << "Problem " << tc++ << ": " << dist[n-1][n-1] << '\n';
	}
}

<테스트케이스 반복 함수>
각 테스트케이스를 반복한다. dist 배열 초기화에 유의한다.

🪄전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

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

typedef pair<int,int> pii;
pii dir[4] = {{-1,0},
			  {1,0},
			  {0,-1},
			  {0,1}};
int dist[126][126];
struct Pos
{
	int rupee;
	int x;
	int y;
};
struct comp
{
	bool operator()(Pos a,Pos b)
	{
		if(a.rupee==b.rupee)
		{
			if(a.x==b.x) return a.y < b.y;
			return a.x < b.x;
		}
		return a.rupee < b.rupee;
	};
};

void INPUT()
{
	IAMFAST
}

void ijk()
{
	priority_queue<Pos,vector<Pos>,comp> pq;
	pq.push({ -map[0][0],0,0 });
	dist[0][0] = map[0][0];

	while(!pq.empty())
	{
		int x = pq.top().x;
		int y = pq.top().y;
		int c1 = -pq.top().rupee;
		pq.pop();

		for(int i = 0; i < 4; i++)
		{
			int nx = x + dir[i].first;
			int ny = y + dir[i].second;
			int c2 = map[nx][ny] + c1;
			if(!(0<=nx&&nx<n&&0<=ny&&ny<n)) continue;

			if(dist[nx][ny] > c2)
			{
				dist[nx][ny] = c2;
				pq.push({-c2,nx,ny});
			}
		}
	}

}

void SOLVE()
{
	int tc = 1;
	while(cin >> n)
	{
		if(!n) break;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				cin >> map[i][j],
				dist[i][j] = 2e9;

		ijk();
		cout << "Problem " << tc++ << ": " << dist[n-1][n-1] << '\n';
	}
}

int main()
{
	INPUT();
	SOLVE();
}

🥇문제 후기

설명할 것 없는 뻔한 Dijkstra 문제였다.
pair<int,pair<int,int>>를 사용하면 굳이 정렬 기준을 따로 안 만들어도 되지만, 담을 변수가 3개 이상이면 구조체를 선언하는 편이다.
그냥 제 취향일 뿐이니 의미두지 않으셔도 됩니다!