[G2] 백준 1445번 일요일 아침의 데이트 C++ 다익스트라

리뷰

 

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

문제는.. 어렵진 않은데 자잘한 실수라던가 지문을 제대로 읽지 않아 발생할 문제가 많다.

 

 

전역 변수

• n, m : 맵의 세로/가로 길이를 저장할 변수
• sx, sy, ex, ey : 시작 및 도착 위치의 좌표를 저장할 변수
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 좌표 정보 x, y, 쓰레기를 밟은 횟수 g, 쓰레기 근처를 지나간 횟수 ng를 정의할 구조체, 기본적으로 g를 기준으로 오름차순 정렬하고, g가 동일한 경우엔 ng를 기준으로 오름차순 정렬한다.

 

함수

1. dijkstra

pair<int, int> dijkstra()

 

다익스트라를 통해 출발지에서 목적지까지 쓰레기를 밟거나 근처를 지나는 최소를 구하는 함수

1. Pos 타입의 우선순위 큐 pq를 초기화 하고, 시작 위치 및 쓰레기를 밟거나 지난 횟수를 모두 0으로 push해준다.
2. 2차원 pii타입의 벡터 dist를 n * m크기로, 값은 둘 다 매우 큰 값으로 초기화를 해준다.
3. 시작 위치의 dist값을 0, 0으로 초기화를 해준다.
4. pq가 빌 때 까지 while 루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
5. 기저 조건으로 만약 도착 지점에 도달한 경우 쓰레기를 밟은 횟수 cg, 지나간 횟수 cng를 리턴해 준다.
6. 4방향 탐색을 진행하고, 맵의 범위 안에 있다면 이동을 진행해 준다.
7. 만약 이동한 위치가 쓰레기라면 쓰레기를 밟은 횟수 ng를 1만큼 증가시켜 준다.
8. 만약 이동한 위치가 빈 땅이고 도착지가 아니라면 이동한 위치에서 4방향 탐색을 진행해 준다.
9. 인접한 칸 중 쓰레기가 하나라도 있다면 쓰레기 옆을 지나간 횟수 nng를 1만큼 증가시켜 준다.
10. 이후 이동한 위치의 dist의 first값이 ng보다 크다면 dist의 ng, nng를 갱신 후 pq에 push해준다.
11. dist의 first값이 ng와 같다면 dist의 second값과 nng를 비교하여 크다면 갱신 후 pq에 push해준다.

 

2. print

void print(int x, int y, int g, int ng)

 

디버깅용 함수

 

문제풀이

1. n, m값을 입력 받고, n * m크기의 맵을입력 받아준다.
2. 입력된 값이 'g'일 경우 lst배열엔 1로 저장해 주고, 'F', 'S'일 경우 sx, sy, ex, ey에 각각의 좌표를 저장해 준다.
3. dijkstra함수를 호출하고 받은 리턴 값을 pii타입의 result로 저장해 준다.
4. result의 first와 second를 공백을 기준으로 순차로 출력해 준다.

 

트러블 슈팅

1. 자잘한 실수가 되게 많았다, 이동 후 쓰레기를 찾는 로직에서 방향 배열의 인덱스를 j가 아닌 i로 했었다.
2. 빈 땅이면서 목표 지점이 아닌 경우를 체크할 때 ||이 아닌 &&로 연산하여 개수를 카운트 하지 않는 상황이 있었다.
3. 쓰레기를 밟았을 때도 인접한 칸에 쓰레기가 있을 경우도 쓰레기를 올려주어 개수가 맞지 않는 상황이 있었다.
4. 인접한 칸에 쓰레기가 여러개 있을 경우 쓰레기의 개수만큼 값을 올려주어 개수가 맞지 않는 상황이 있었다.
5. 위 내용을 모두 고치고 제출하였더니 AC를 받게 되었다.

 

참고 사항

• 시작 및 도착 지점은 비어있는 칸이 아니다.
• 우선 순위는 쓰레기를 밟은 횟수, 쓰레기를 지나간 횟수를 기준으로 오름차순 정렬해 주어야 한다.

 

정답 코드

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

int n, m, sx, sy, ex, ey;
int lst[50][50];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int x, y, g, ng;
	bool operator<(const Pos& other) const {
		if (g == other.g) return ng > other.ng;
		return g > other.g;
	}
};

void print(int x, int y, int g, int ng) {
	cout << "\n";
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (x == i && y == j) cout << '#';
			else if (ex == i && ey == j) cout << "@";
			else cout << lst[i][j];
		}
		cout << "\n";
	}
	cout << "쓰레기를 지난 횟수 : " << g << " 쓰레기 옆을 지난 횟수 : " << ng << "\n";
}

pair<int, int> dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ sx, sy, 0, 0 });
	vector<vector<pair<int, int>>> dist(n, vector<pair<int, int>>(m, {2e9, 2e9}));
	dist[sx][sy] = { 0, 0 };

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cg = pos.g, cng = pos.ng;
		//print(cx, cy, cg, cng);
		if (cx == ex && cy == ey) return { cg, cng };

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i], ng = cg, nng = cng;
			
			if (0 <= nx && nx < n && 0 <= ny && ny < m) {
				if (lst[nx][ny]) ng++;
				else if (nx != ex || ny != ey){
					for (int j = 0; j < 4; ++j) {
						int nnx = nx + dx[j], nny = ny + dy[j];
						if (0 <= nnx && nnx < n && 0 <= nny && nny < m && lst[nnx][nny]) {
							nng++;
							break;
						}
					}
				}
				
				if (dist[nx][ny].first > ng) {
					dist[nx][ny].first = ng;
					dist[nx][ny].second = nng;
					pq.push({ nx, ny, ng, nng });
				}
				else if (dist[nx][ny].first == ng && dist[nx][ny].second > nng) {
					dist[nx][ny].second = nng;
					pq.push({ nx, ny, ng, nng });
				}
			}
		}
	}
	return { -1, -1 };
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		string s; cin >> s;
		for (int j = 0; j < m; ++j) {
			if (s[j] == 'g') lst[i][j] = 1;
			else if (s[j] == 'F') sx = i, sy = j;
			else if (s[j] == 'S') ex = i, ey = j;
		}
	}
	pair<int, int> result = dijkstra();
	cout << result.first << " " << result.second;
}