[c++] 백준 14497, 주난의 난(難)

배군 14497

🌲 문제 요약

주난이의 점프 한 번은 한 겹의 친구들을 쓰러뜨릴 수 있다고 할 때, 주난이가 초코바를 훔친 범인을 잡기 위해선 최소 몇 번의 점프가 필요한지 구하는 문제.

🌲 문제 풀이

주난이의 위치를 배열 visited와 큐 q에 저장한 뒤, a[y2][x2]의 값이 0이 되기 전까지, 한 번의 점프 이후 상황을 반복적으로 확인한다.
배열 a를 탐색하는 과정에서 a[ny][nx]의 값이 0이 아니라면, a[ny][nx]에 1을 저장하고, 해당 위치를 visited와 큐 tmp에 저장한다. 한 번의 점프가 끝날 때마다 q에 tmp를 복사하고 turn의 값을 1만큼 증가시킨다.
반복이 종료되면, turn의 값을 출력한다.

🌲 주의

한 번의 점프가 끝날 때마다, 큐 tmp를 새로이 선언해 주어야 한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
#define y1 sub
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, y1, x1, y2, x2, y, x, visited[305][305], turn;
char a[305][305];
queue<pair<int, int>> q;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> m;
	cin >> y1 >> x1 >> y2 >> x2;
	y1--, x1--, y2--, x2--;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	visited[y1][x1] = 1;
	q.push({y1, x1});
	while (a[y2][x2] != '0') {
		memset(visited, 0, sizeof(visited));
		queue<pair<int, int>> tmp;
		while (q.size()) {
			tie(y, x) = q.front(); q.pop();
			for (int i = 0; i < 4; i++) {
				int ny = y + dy[i];
				int nx = x + dx[i];
				if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue;
				if (a[ny][nx] == '0') {
					visited[ny][nx] = 1;
					q.push({ny, nx});
				}
				else {
					a[ny][nx] = '0';
					visited[ny][nx] = 1;
					tmp.push({ny, nx});
				}
			}
		}
		q = tmp;
		turn++;
	}
	cout << turn << '\n';
	
	return 0;
}