취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1445번 문제인 일요일 아침의 데이트이다.
문제는 아래 링크를 확인하자.

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

Dijkstra 알고리즘의 가중치를 (쓰레기를 밟은 횟수, 쓰레기 옆을 지난 횟수)의 순서쌍으로 설정해 적용하면 문제를 해결할 수 있다.

다음 문제 조건에 유의하자.

만약 어떤 칸이 비어있는데, 인접한 칸에 쓰레기가 있으면 쓰레기 옆을 지나는 것이다.

즉, 쓰레기가 서로 인접해있는 경우 쓰레기가 있는 칸은 "비어있는" 칸이 아니므로 해당 쓰레기가 있는 칸을 지나는 경로는 해당 칸에서 쓰레기가 있는 칸을 지난 횟수만 증가가고 쓰레기 옆을 지나는 횟수는 증가하지 않는다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int R, C;
int sR, sC, eR, eC;
string board[50];
pair<int, int> dist[50][50];
bool visited[50][50];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void dijkstra() {
	priority_queue<pair<pair<int, int>, pair<int, int>>> pq; // (가중치,노드)
	pq.push(make_pair(make_pair(-1, 0), make_pair(sR, sC)));
	dist[sR][sC] = make_pair(1, 0);
	while (!pq.empty()) {
		auto d = pq.top().first, cur = pq.top().second;
		d.first *= -1, d.second *= -1;
		pq.pop();
		if (dist[cur.first][cur.second] < d) continue;
		for (int i = 0; i < 4; i++) {
			int rr = cur.first + dr[i], cc = cur.second + dc[i];
			if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
			if (board[rr][cc] == 'g') {
				pair<int, int> tmp = d; tmp.first++;
				if (dist[rr][cc] == make_pair(0, 0) || tmp < dist[rr][cc]) {
					dist[rr][cc] = tmp;
					tmp.first *= -1, tmp.second *= -1;
					pq.push(make_pair(tmp,make_pair(rr,cc)));
				}
			}
			else if (board[rr][cc] == 'h') {
				pair<int, int> tmp = d; tmp.second++;
				if (dist[rr][cc] == make_pair(0, 0) || tmp < dist[rr][cc]) {
					dist[rr][cc] = tmp;
					tmp.first *= -1, tmp.second *= -1;
					pq.push(make_pair(tmp, make_pair(rr, cc)));
				}
			}
			else {
				pair<int, int> tmp = d;
				if (dist[rr][cc] == make_pair(0, 0) || tmp < dist[rr][cc]) {
					dist[rr][cc] = tmp;
					tmp.first *= -1, tmp.second *= -1;
					pq.push(make_pair(tmp, make_pair(rr, cc)));
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		string& s = board[r];
		cin >> s;
		for (int c = 0; c < C; c++) {
			if (s[c] == 'S') sR = r, sC = c;
			else if (s[c] == 'F') eR = r, eC = c;
		}
	}
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			if (board[r][c] == 'g') {
				for (int i = 0; i < 4; i++) {
					int rr = r + dr[i], cc = c + dc[i];
					if (rr < 0 || rr >= R || cc < 0 || cc >= C) continue;
					if (board[rr][cc] == 'g') continue;
					board[rr][cc] = 'h';
				}
			}
		}
	}
	board[eR][eC] = '.';

	dijkstra();

	cout << dist[eR][eC].first - 1 << ' ' << dist[eR][eC].second;
}