[BOJ 17500 // C++] 국경

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17500번 문제인 국경이다.
문제는 아래 링크를 확인하자.

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

 

입력으로 주어지는 \(N\)의 크기가 매우 작음(4 이하)을 확인하자. 실제로 \(N=4\)인 경우 좌상단 꼭짓점에서 우하단 꼭짓점으로 한 꼭짓점을 두 번 이상 경유하지 않고 이동하는 경로의 개수는 10000개도 되지 않는다.

 

따라서, 위와 같은 모든 경로를 백트래킹으로 전부 생성해보고, BFS 등으로 각 경로가 서로 다른 동물들이 다른 영역에 포함되게끔 섬을 나누는지 확인해 문제를 해결할 수 있다.

 

칸의 경계와 칸 자체를 모두 접근해야 하므로, 코드를 작성할 때 특별히 유의하여 이를 구현하자.

 

아래는 제출한 소스코드이다.

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

int N = 5;
int visited[5][5];
char board[11][11];
int dr[4] = {0,0,1,-1};
int dc[4] = {1,-1,0,0};
bool printed;
int vis[11][11];
set<char> st;
queue<pair<int, int>> que;
bool bfs(int sR, int sC) {
	st.clear();
	vis[sR][sC] = 1;
	que.push(make_pair(sR, sC));
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		if (board[r][c] != '.') st.insert(board[r][c]);
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (board[rr][cc]) continue;
			rr += dr[i], cc += dc[i];
			if (rr < 2 || rr >= N * 2 + 1 || cc < 2 || cc >= N * 2 + 1 || vis[rr][cc]) continue;
			vis[rr][cc] = 1;
			que.push(make_pair(rr, cc));
		}
	}
	return (st.size() <= 1);
}
void solve() {
	memset(vis, 0, sizeof(vis));
	for (int r = 2; r < N * 2 + 1; r += 2) {
		for (int c = 2; c < N * 2 + 1; c += 2) {
			if (vis[r][c]) continue;
			if (!bfs(r, c)) return;
		}
	}
	printed = 1;
	cout << "yes\n";
	for (int r = 0; r < N * 2 + 3; r++) {
		for (int c = 0; c < N * 2 + 3; c++) {
			if (c % 2 == 0 && c > 0 && c < N * 2 + 1) {
				if (board[r][c] == '-' || board[r][c] == '#') cout << board[r][c] << board[r][c] << board[r][c];
				else if (board[r][c]) cout << ' ' << board[r][c] << ' ' ;
				else cout << ' ' << ' ' << ' ';
			}
			else {
				if (board[r][c]) cout << board[r][c];
				else cout << ' ';
			}
		}
		cout << '\n';
	}
}

void func(int r, int c) {
	if (r == N && c == N) {
		if (!printed) solve();
	}
	visited[r][c] = 1;
	for (int i = 0; i < 4; i++) {
		int rr = r + dr[i], cc = c + dc[i];
		if (rr < 0 || rr > N || cc < 0 || cc > N || visited[rr][cc]) continue;
		if (i < 2) board[1 + r * 2][1 + c * 2 + dc[i]] = '-';
		else board[1 + r * 2 + dr[i]][1 + c * 2] = '|';
		func(rr, cc);
		if (i < 2) board[1 + r * 2][1 + c * 2 + dc[i]] = 0;
		else board[1 + r * 2 + dr[i]][1 + c * 2] = 0;
	}
	visited[r][c] = 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int c = 0; c < N * 2 + 3; c++) board[0][c] = board[N * 2 + 2][c] = '#';
	for (int r = 0; r < N * 2 + 3; r++) board[r][0] = board[r][N * 2 + 2] = '#';
	for (int r = 1; r < N * 2 + 3; r += 2) {
		for (int c = 1; c < N * 2 + 3; c += 2) {
			board[r][c] = '+';
		}
	}
	for (int r = 2; r < N * 2 + 1; r += 2) {
		for (int c = 2; c < N * 2 + 1; c += 2) {
			cin >> board[r][c];
		}
	}

	func(0, 0);
	if (!printed) cout << "no";
}