[G4] 백준 16469번 소년 점프 C++ 너비 우선 탐색, 플러드 필

리뷰

 

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

문제를 접근하는 방식에 아이디어가 필요했던 문제

 

 

전역 변수

• r, c : 맵의 세로/가로 크기를 저장할 변수
• map : 맵 정보를 저장할 2차원 배열
• Pos : 위치 정보를 정의할 구조체
• dx, dy : 4방향 탐색을 위한 방향 배열

 

함수

1. bfs

vector<vector<int>> bfs(int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy });
	vector<vector<int>> dist(r + 1, vector<int>(c + 1, -1));
	dist[sx][sy] = 0;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = dist[cx][cy];

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];

			if (1 <= nx && nx <= r && 1 <= ny && ny <= c && !map[nx][ny] && dist[nx][ny] == -1) {
				dist[nx][ny] = ct + 1;
				q.push({ nx, ny });
			}
		}
	}

	return dist;
}

 

현재 위치에서 시작해 맵 상의 좌표에 도달하는 최소 시간을 구하기 위한 함수

 

 

문제풀이

1. r, c값을 입력 받고, r*c크기의 맵 정보를 입력받아 map을 초기화한다.
2. 정수형 2차원 벡터 배열 dist를 3개 크기로 저장한다.
3. 3명의 악당 위치를 입력 받고, bfs함수에 좌표를 매개변수로 전달하여 호출한다.
4. bfs함수 내부에서 변수 sx, sy에 시작 위치 정보를 파싱한다.
5. Pos타입의 큐 q를 초기화 하고, 초기 위치 sx, sy를 추가한다.
6. r+1*c+1크기의 2차원 벡터 dist를 초기값 -1로 초기화하고, 시작 위치의 dist값을 0으로 저장한다.
7. q가 빌때까지 맵을 순회하며 맵 상에서 장애물이 아니면서 방문하지 않은 위치에 대한 탐색을 시작한다.
8. 각 위치까지 이동에 걸리는 최단 시간을 dist에 저장하고, dist를 리턴한다.
9. 변수 res에 bfs함수의 반환값을 전달받고, 현재 악당의 인덱스에 res를 복사한다.
10. 변수 mn을 매우 큰 값, cnt를 0으로 초기화한다.
11. r*c크기의 맵을 순회하며 변수 flag를 true, mx를 0으로 초기화한다.
12. dist를 순회하며 현재 위치에서 각 악당의 거리 중 최대값을 mx에 저장한다.
13. 만약 초기값인 -1이 있는 경우 해당 위치에 도달하지 못하는 악당이 있는 것이므로 flag를 false로 변경 후 break한다.
14. 결과적으로 flag가 false라면 continue처리를 한다.
15. mn이 mx보다 클 경우 mn을 mx로 갱신하고, cnt를 1로 초기화한다.
16. mn과 mx가 동일할 경우 cnt를 증가시킨다.
17. 마지막으로 mn이 초기값일 경우 -1을 출력한다. 초기값이 아닐 경우 mn과 cnt를 줄바꿈으로 구분하여 출력한다.

 

트러블 슈팅

1. 모든 맵을 순회하며 각 위치에 도달하는 시간 중 최대값의 최소값을 비교하려 했다가 시간 초과를 받았다.
2. 각 악당의 위치에서 맵을 순회하는 거리를 구한 후 그 시간 중 최대값의 최소값을 구하도록 수정하여 AC를 받았다.

 

참고 사항

1. 세 악당이 모일 때 걸린 시간의 최소 값 뿐만 아니라 그러한 지점의 개수도 알아야 한다.
2. 만약 세 악당이 모일 수 있는 지점이 존재하지 않는다면 -1를 출력한다.
3. 마미손의 위치는 고려할 필요가 없다.

 

정답 코드

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

int r, c;
char map[101][101];
struct Pos {
	int x, y;
};
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

vector<vector<int>> bfs(int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy });
	vector<vector<int>> dist(r + 1, vector<int>(c + 1, -1));
	dist[sx][sy] = 0;

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.x, cy = pos.y, ct = dist[cx][cy];

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];

			if (1 <= nx && nx <= r && 1 <= ny && ny <= c && !map[nx][ny] && dist[nx][ny] == -1) {
				dist[nx][ny] = ct + 1;
				q.push({ nx, ny });
			}
		}
	}

	return dist;
}

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

	cin >> r >> c;
	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			cin >> map[i][j];
			map[i][j] -= '0';
		}
	}

	vector<vector<int>> dist[3];
	for (int i = 0; i < 3; ++i) {
		int x, y; cin >> x >> y;
		auto res = bfs(x, y);
		dist[i] = res;
	}

	int mn = 2e9, cnt = 0;
	for (int i = 1; i <= r; ++i) {
		for (int j = 1; j <= c; ++j) {
			bool flag = true;
			int mx = 0;
			for (int k = 0; k < 3; ++k) {
				if (dist[k][i][j] == -1) {
					flag = false;
					break;
				}
				mx = max(mx, dist[k][i][j]);
			}

			if (!flag) continue;

			if (mn > mx) {
				mn = mx;
				cnt = 1;
			}
			else if (mn == mx) ++cnt;
		}
	}

	if (mn == 2e9) cout << -1;
	else cout << mn << "\n" << cnt;
}