백준 1445 - 일요일 아침의 데이트(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1445

1445번: 일요일 아침의 데이트

다익스트라를 이용한 문제입니다.
비교할 값이 2개가 있기에 조심해야 되는 문제였습니다.

시작 지점에서 출발해 도착 지점까지 갈 때, 쓰레기 위를 지나는 값, 근처를 지나는 값의 최소를 출력하는 문제입니다.

쓰레기의 위치는 g로 주어지며, 근처는 상하좌우인 4방향입니다.
따라서, 쓰레기의 위치를 받을 때, 근처의 위치도 같이 표시해주면 됩니다.

먼저 함수 탐색 후, 최솟 값을 출력해야 하기에 다익스트라 알고리즘을 사용했습니다.
여기서 비교할 값은, 이동 횟수가 아닌
1. 쓰레기 위를 지나는 값이 작은 값
2. 같다면 근처를 지나는 값이 작은 값
-> 이 2가지 조건으로 비교해 더 작은 값을 가져오면 됩니다.

정리하자면, 시작 지점에서 출발해 4방향 위치를 확인합니다.
4방향 위치에서 map의 범위를 넘는 곳이 아니라면, 해당 좌표가 쓰레기 위 혹은 근처인지를 확인 후, 변수 값을 바꿔줍니다.
2가지의 변수 값을 통해, 이전에 저장되어 있는 값과 비교해서 바꿔야 한다면 바꿔줍니다.
바꿨다면 해당 좌표를 다시 큐에 넣어 탐색을 돌려줍니다.

마지막에 도착 지점은 쓰레기위 유무를 따지지 않는다고 했으니 어디에 있든 무시하고 출력해주면 됩니다.

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#define INF 987654321
#define F first
#define S second

using namespace std;

int N, M;
char map[51][51];
int near_g[51][51]; //쓰레기 위치는 2, 근처는 1
pair<int, int> Distance[51][51]; //쓰레기 위를 지날 때, 근처를 지날 때
pair<int, int> st, fin;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
priority_queue<pair<pair<int, int>, pair<int, int>>> q; // 쓰레기 위, 근처의 값, 좌표

// Distance의 값 초기화
void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			Distance[i][j] = {INF, INF};
		}
	}
}


// Distance의 값 비교 함수, 쓰레기를 지나는 갯수 -> 근처를 지나는 갯수로 비교
bool cmp(int x, int y, int cnt_gar, int cnt_near){
	if(Distance[x][y].F > cnt_gar) return true;
	else if(Distance[x][y].F == cnt_gar){
		if(Distance[x][y].S > cnt_near) return true;
		else return false;
	}
	else return false;
}

// 다익스트라 알고리즘 함수
void Dijstra(){
	reset_distance();
	Distance[st.F][st.S] = {0, 0};
	q.push({{-0, -0},st});
	while(!q.empty()){
		int x = q.top().S.F;
		int y = q.top().S.S;
		int cnt_gar = -q.top().F.F;
		int cnt_near = -q.top().F.S;
		q.pop();
		for(int i = 0; i < 4; i++){ // 근처 위치를 확인
			int xx = x + dx[i];
			int yy = y + dy[i];
			int next_gar = cnt_gar;
			int next_near = cnt_near;
			// 쓰레기 위를 지날 때
			if(near_g[xx][yy] == 2) next_gar = cnt_gar + 1;
			// 쓰레기 근처를 지날 때
			if(near_g[xx][yy] == 1) next_near = cnt_near + 1;
			if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
				// 비교 함수를 통해 값을 바꿀지를 확인
				if(cmp(xx, yy, next_gar, next_near)){
					Distance[xx][yy] = {next_gar, next_near};
					q.push({{-next_gar, -next_near},{xx, yy}});
				}
			}
		}
	}
}

void solve(){
	Dijstra();
	// 도착 지점은 어떤 값이든 상관없이 무시
	if(near_g[fin.F][fin.S] == 1) cout << Distance[fin.F][fin.S].F << " " << Distance[fin.F][fin.S].S - 1;
	else if(near_g[fin.F][fin.S] == 2) cout << Distance[fin.F][fin.S].F - 1 << " " << Distance[fin.F][fin.S].S;
   else cout << Distance[fin.F][fin.S].F << " " << Distance[fin.F][fin.S].S;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			cin >> map[i][j];
			if(map[i][j] == 'F') fin = {i, j};
			if(map[i][j] == 'S') st = {i, j};
			if(map[i][j] == 'g'){
				near_g[i][j] = 2;
				for(int k = 0; k < 4; k++){
					int xx = i + dx[k];
					int yy = j + dy[k];
					if(map[xx][yy] == 'g') continue;
					if(xx >= 1 && xx <= N && yy >= 1 && yy <= M){
						near_g[xx][yy] = 1;
					}
				}
			}
		}
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.