[G2] 백준 16920번 확장 게임 C++ 구현, 너비 우선 탐색, 플러드 필

리뷰

 

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

각 라운드 마다 플레이어 번호가 낮은 순서부터 확장할 수 있을 만큼 확장 후 최종적으로 플레이어 마다 확장한 크기만큼을 출력하는 문제

 

 

전역 변수

• N : 맵 한변의 최대 길이를 정의할 상수 변수
• P : 플레이어 관련 배열의 최대 길이를 정의할 상수 변수
• n, m : 맵의 세로/가로 변의 길이를 저장할 변수
• p : 플레이어 수를 저장할 변수
• v : 맵의 방문 여부를 저장할 배열
• S : 플레이어 당 한 턴에 이동할 수 있는 거리를 저장할 배열
• cnt : 플레이어 당 점령한 성의 개수를 저장할 배열
• Pos : 시뮬레이션 시 사용할 현재 위치와 남은 이동 횟수를 정의할 구조체
• dx, dy : 4방향 탐색을 위한 방향 배열
• qs : 플레이어 별 Pos타입의 큐를 저장할 벡터

 

함수

1. solution

void solution() {
	bool con = get_con();

	while (con) {
		for (int i = 1; i <= p; ++i) {
			floodfill(i);
		}
		con = get_con();
	}

	for (int i = 1; i <= p; ++i) cout << cnt[i] << " ";
}

 

이동할 수 있을 때 까지 라운드를 진행하기 위한 함수

 

2. get_con

bool get_con() {
	for (const auto& q : qs) {
		if (!q.empty()) return true;
	}
	return false;
}

 

더 이상 이동할 수 있는지 여부를 체크하기 위한 함수

 

3. floodfill

void floodfill(int pn) {
	queue<Pos> q;
	swap(q, qs[pn]);

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.cx, cy = pos.cy, rm = pos.rm;

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

			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny]) {
				v[nx][ny] = true;
				cnt[pn]++;

				if (nrm) q.push({ nx, ny, nrm });
				else qs[pn].push({nx, ny, S[pn]});
			}
		}
	}
}

 

너비 우선 탐색을 통해 확장을 구현하기 위한 함수

 

 

문제풀이

1. n, m, p값을 입력 받고, 플레이어 번호가 1-based-indexing으로 주어지므로 qs벡터를 p+1크기로 초기화 한다.
2. p명의 플레이어가 한 라운드에 이동할 수 있는 거리를 S배열에 입력 받아준다.(마찬가지로 1-based-indexing)
3. n*m크기의 맵 정보를 입력 받고, 현재 위치가 벽이라면 v배열에 방문 처리를 진행해 준다.
4. 플레이어 번호가 주어진 경우 방문처리 후 cnt를 증가, qs에 플레이어 번호의 큐에 좌표와 이동횟수를 push한다.
5. solution함수를 호출하여 아무 플레이어도 더 이상 확장할 수 없을 때 까지 확장을 진행해 준다.
6. 변수 con에 get_con함수를 호출한 결과값을 저장해 준다.
7. get_con함수는 qs를 순회하며 모든 큐가 비어있다면 false를, 하나의 큐라도 비지 않았다면 true를 반환한다.
8. con이 true일 경우를 조건으로 하는 while루프를 수행하고, 각 플레이어 번호를 순회해 준다.
9. 플레이어의 큐가 빈 상태라면 continue를, 비지 않았다면 floodfill함수에 플레이어 번호를 전달하여 호출한다.
10. floodfill함수는 플레이어 번호 pn을 매개변수로 전달 받는다.
11. Pos타입의 큐 q를 초기화 하고, swap함수를 통해 q와 qs[pn]을 바꾸어 준다.
12. q가 빌때까지 while루프를 수행하고, 매 루프마다 요소를 한개씩 꺼내어 준다.
13. 변수 cx, cy, rm에 현재 요소의 위치와 남은 이동 횟수를 파싱하여 저장해 준다.
14. 4방향 탐색을 진행하고 이동할 위치를 변수 nx, ny, 이동 후 남은 이동 횟수 nrm에 rm-1값을 저장해 준다.
15. 맵의 범위 내에 있으면 방문하지 않은 지역이라면 이동 후 방문처리 및 cnt[pn]을 증가시킨다.
16. nrm이 0이 아니라면 q에 이동 위치와 nrm을 push하고 0이라면 qs[pn]에 이동 위치와 S[pn]을 push한다.
17. soultion함수의 while루프가 종료되면 1~p번의 플레이어 번호에 저장된 cnt값을 공백을 기준으로 출력한다.

 

트러블 슈팅

1. 우선 순위 큐 2개를 활용하여 플레이어 번호가 낮은 순서대로 처리하도록 구현하였는데 12%에서 Fail을 받았다.
2. 플레이어 별 큐를 구현하여 낮은 플레이어 순서대로 floodfill함수를 호출하는 형식으로 바꾸어 AC를 받았다.

 

참고 사항

1. 플레이어 마다 큐를 구현하지 않고 우선순위 큐 2개로도 될 줄 알았는데 Fail을 받는 이유와 반례는 찾지 못했다.
2. 입력으로 주어지는 플레이어 번호는 1-based-indexing이므로 for문을 돌릴 때 주의를 기울이자

 

정답 코드

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

const int N = 1e3;
const int P = 10;
int n, m, p;
bool v[N][N];
int S[P];
int cnt[P];
struct Pos {
	int cx, cy, rm;
};
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
vector<queue<Pos>> qs;

void floodfill(int pn) {
	queue<Pos> q;
	swap(q, qs[pn]);

	while (!q.empty()) {
		Pos pos = q.front(); q.pop();
		int cx = pos.cx, cy = pos.cy, rm = pos.rm;

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

			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny]) {
				v[nx][ny] = true;
				cnt[pn]++;

				if (nrm) q.push({ nx, ny, nrm });
				else qs[pn].push({nx, ny, S[pn]});
			}
		}
	}
}

bool get_con() {
	for (const auto& q : qs) {
		if (!q.empty()) return true;
	}
	return false;
}

void solution() {
	bool con = get_con();

	while (con) {
		for (int i = 1; i <= p; ++i) {
			if (qs[i].empty()) continue;
			floodfill(i);
		}
		con = get_con();
	}

	for (int i = 1; i <= p; ++i) cout << cnt[i] << " ";
}

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

	cin >> n >> m >> p;
	qs.resize(p + 1);
	for (int i = 1; i <= p; ++i) cin >> S[i];

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char ch; cin >> ch;
			if (ch == '.') continue;
			else if (ch == '#') v[i][j] = true;
			else {
				int num = ch - '0';
				v[i][j] = true;
				cnt[num]++;
				qs[num].push({i, j, S[num]});
			}
		}
	}

	solution();
}