※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 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";
}