[G5] 백준 23352번 방탈출 C++ 너비 우선 탐색, 플러드 필, 브루트포스 알고리즘

리뷰

 

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

가장 긴 경로를 찾고, 시작점과 끝점의 정수 합이 가장 큰 결과를 구하는 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• a : 맵 정보를 저장할 2차원 배열
• v : 방문 여부를 체크할 2차원 배열
• n, m : 맵의 세로/가로 길이를 저장할 변수
• dx, dy : 4방향 탐색을 위한 방향 배열
• Pos : 현재 위치와 누적 거리를 정의할 구조체

 

함수

1. flood_fill

pair<int, int> flood_fill(int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy, 0 });
	v[sx][sy] = true;
	int len = 0;
	int f = a[sx][sy];
	int l = a[sx][sy];

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.cx, cy = pos.cy, cl = pos.cl;
		if (cl > len) {
			len = cl;
			l = a[cx][cy];
		}
		else if (cl == len) l = max(l, a[cx][cy]);

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

			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && a[nx][ny]) {
				v[nx][ny] = true;
				q.push({ nx, ny, cl + 1 });
			}
		}
	}
	return { len, f + l };
}

 

갈 수 있는 모든 방을 방문하고, 가장 긴 거리와 시작점과 끝 점에 적힌 정수의 합의 최대값을 반환하는 함수

 

 

문제풀이

1. n, m값을 입력 받고, n*m크기의 맵 정보를 입력 받아 a배열을 초기화한다.
2. 변수 mx, ml을 0으로 초기화 하고, n*m크기의 맵으 순회한다.
3. 만약 현재 위치가 0일 경우 탐색하지 않고 continue처리한다.
4. memset함수를 통해 v배열을 false로 초기화한다.
5. flood_fill함수에 현재 x, y좌표를 매개변수로 전달하여 호출한다.
6. flood_fill함수 내부에선 변수 sx, sy에 시작점의 위치를 파싱한다.
7. Pos타입의 큐 q를 초기화 하고, sx, sy, 0을 push한다.
8. v[sx][sy]에 true를 저장해 시작점에 방문 처리를 한다.
9. 변수 len을 0, f, l을 a[sx][sy]로 초기화한다.
10. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 꺼내 변수 cx, cy, cl에 파싱한다.
11. 만약 cl이 len보다 클 경우 len을 cl로 변경하고, l을 a[cx][cy]로 변경한다.
12. 만약 cl이 len과 동일할 경우 l을 a[cx][cy]와 비교해 더 큰 값을 l에 저장한다.
13. 4방향 탐색을 수행하고, 이동할 위치가 맵의 범위 안이면서, 방문하지 않았고, 0이 아닐 경우 이동을 수행한다.
14. 이동 후엔 v[nx][ny]를 true로 저장해 방문 처리를 하고 nx, ny, cl+1을 q에 push한다.
15. 모든 탐색을 마친 후 len, f+l을 반환하고, 변수 res에 flood_fill함수의 리턴값을 저장한다.
16. res.first가 ml보다 클 경우 ml을 res.first, mx를 res.second로 저장한다.
17. 만약 res.first가 ml과 같은 경우 mx와 res.second를 비교하여 더 큰값을 mx에 저장한다.
18. mx에 저장된 값을 출력한다.

 

트러블 슈팅

없음

 

 

참고 사항

1. 만약 비밀번호를 만들 수 없는 경우 0을 출력한다. 라는 조건이 있어 mx의 초기값을 0으로 잡았다.
2. 가장 긴 경로가 여러 개라면, 시작 방과 끝 방에 적힌 숫자의 합이 가장 큰 값이 비밀번호가 된다.

 

정답 코드

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

const int N = 50;
int a[N][N];
bool v[N][N];
int n, m;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
struct Pos {
	int cx, cy, cl;
};

pair<int, int> flood_fill(int sx, int sy) {
	queue<Pos> q;
	q.push({ sx, sy, 0 });
	v[sx][sy] = true;
	int len = 0;
	int f = a[sx][sy];
	int l = a[sx][sy];

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.cx, cy = pos.cy, cl = pos.cl;
		if (cl > len) {
			len = cl;
			l = a[cx][cy];
		}
		else if (cl == len) l = max(l, a[cx][cy]);

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

			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && a[nx][ny]) {
				v[nx][ny] = true;
				q.push({ nx, ny, cl + 1 });
			}
		}
	}
	return { len, f + l };
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}

	int mx = 0, ml = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (!a[i][j]) continue;
			memset(v, false, sizeof(v));
			auto res = flood_fill(i, j);
			if (res.first > ml) {
				ml = res.first;
				mx = res.second;
			}
			else if (res.first == ml) mx = max(mx, res.second);
		}
	}
	cout << mx;
}