[BOJ 14497] 주난의 난(c++)

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

문제 개요

N×M 크기의 교실에서 주난이가 상하좌우로 파동을 퍼뜨려 범인을 잡는 문제입니다. 파동은 장애물(친구들)을 만날 때까지 계속 퍼져나가며, 한 번의 점프가 한 겹의 친구들을 쓰러뜨립니다. 주난이의 위치에서 범인의 위치까지 도달하는 데 필요한 최소 점프 횟수를 구해야 합니다.

• (1 ≤ N, M ≤ 300)

---

문제 풀이

이 문제는 다익스트라(우선순위 큐 BFS) 로 해결하였습니다.

핵심 아이디어는 다음과 같습니다.

• 파동이 퍼져나갈 때, 빈 공간(0)을 지나는 것은 비용이 0이고, 친구(1 또는 #)를 만나면 비용이 1(점프 1회) 발생합니다.
• 즉, 이동 비용이 0 또는 1인 최단 경로 문제이므로 우선순위 큐(최소 힙)를 사용하는 다익스트라로 해결할 수 있습니다.
• 출발점에서 상하좌우로 탐색하며, 해당 칸이 빈 칸이면 현재 점프 횟수 유지, 친구가 있는 칸이면 점프 횟수를 1 증가시켜 큐에 삽입합니다.
• 범인(#)의 위치에 도달했을 때의 점프 횟수를 출력합니다.

---

코드

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

class node {
public:
	int x, y, cnt;
	bool operator < (const node& other) const {
		return cnt > other.cnt;
	}
};

int n, m;
char coord[301][301];
bool visit[301][301];

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

int bfs(int sx, int sy, int ex, int ey) {
	priority_queue<node> pq;
	pq.push({ sx, sy, 0 });
	visit[sx][sy] = true;
	while (!pq.empty()) {
		int x = pq.top().x;
		int y = pq.top().y;
		int cnt = pq.top().cnt;
		if (x == ex && y == ey) return cnt;
		pq.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || ny < 1 || nx > n || ny > m || visit[nx][ny]) continue;
			visit[nx][ny] = true;
			int ncnt = cnt;
			if (coord[nx][ny] != '0') ncnt++;
			pq.push({ nx, ny, ncnt});
		}
	}
	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int sx, sy, ex, ey;
	cin >> n >> m >> sx >> sy >> ex >> ey;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> coord[i][j];
		}
	}
	int res = bfs(sx, sy, ex, ey);
	cout << res << '\n';
	return 0;
}