JUINTINATION
백준 4574번: 스도미노쿠 본문
문제
https://www.acmicpc.net/problem/4574
4574번: 스도미노쿠
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가
www.acmicpc.net
풀이
스도미노쿠는 스도쿠와 도미노를 혼합한 게임으로 9 x 9 크기의 보드에 1부터 9까지 숫자가 1개씩 쓰여져 있고, 나머지 72칸은 도미노 타일 36개로 채워야 합니다. 도미노 타일은 1부터 9까지 서로 다른 숫자의 쌍(1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ... , 8 + 9)이 모두 포함되어 있습니다. 이때 1+2와 2+1은 따로 구분하지 않습니다. 모든 도미노 타일은 회전 시킬 수 있으며 3 × 3 크기의 정사각형의 경계에 걸쳐서 놓을 수도 있습니다.
코드
C언어
2차원 정수 배열 arr로 9 x 9 크기의 보드를 표현하고 visited로 a + b(혹은 b + a)쌍의 도미노 사용 여부를 확인합니다.(visited[a][b] = visited[b][a] = 1이라면 사용한 것) dfs 함수에서 보드의 (x, y)의 위치에 있는 숫자를 arr[y][x]라고 할 때 dpth는 y를, idx는 x를 의미합니다. 메인 함수에서 모든 입력을 받은 후에 아직 스도미노쿠를 완성하지 않았다는 의미로 bool형 정수 sudominoku를 0(False)으로 초기화해준 뒤에 문제 조건에 맞게 몇 번째 퍼즐인지 출력하고 dfs(0, 0)을 실행합니다. 이때 입력의 마지막 줄에 0이 하나라면 종료합니다.
먼저 arr[dpth][idx]가 0이라면(비어있는 칸이라면) i를 포함한 for문을 이용하여 1부터 9까지 숫자 중에서 넣을 수 있는 숫자를 sudoku 함수를 통해 확인합니다.이때 sudoku 함수에 대한 설명은 지난번에 작성한 스도쿠 문제에서 확인할 수 있습니다.
해당 칸에 어떤 수 i를 입력할 수 있다면 arr[dpth][idx] = i를 통해 기록하고 0과 1을 1개씩 포함한 정수 배열 dx와 dy로 도미노를 가로로 놓을지 세로로 놓을지 k를 포함한 for문을 통해 정합니다. (k = 0이면 x축으로, k = 1이면 y축으로 1칸 이동)
이동한 후의 위치(nx, ny)가 보드를 벗어나지 않았는지 확인한 후에(nx < 9 && ny < 9) arr[ny][nx]가 0이라면(비어있는 칸이라면) j를 포함한 for문을 이용하여 해당 위치에 어떤 수 j를 입력할 수 있는지 sudoku 함수를 통해 확인합니다.
해당 칸에 어떤 수 j를 입력할 수 있다면 arr[ny][nx] = j를 통해 기록하고 visited[nx][ny] = visited[nx][ny] = 1을 통해 해당 숫자쌍 도미노를 사용했다는 것을 기록합니다. 이후에 dfs 함수를 재귀적으로 실행합니다.
만약 함수가 실행되고 있던 와중에 막혀서 다시 돌아가야 하는 경우가 있을 수 있으므로 기록했던 것들을 아래에서 지워줍니다. 다시 돌아가기 전에 비어있는 칸을 건너뛰고 다음 dfs 함수를 실행하는 것을 막기 위해 if문 안에서 return합니다.
idx가 9가 됐다면 해당 y 좌표의 모든 x값을 확인한 것이므로 dfs(dpth + 1, 0)을 통해 다음 y 좌표의 처음, 즉 (0, y + 1)부터 다시 시작합니다. dpth가 9가 됐다면 모든 칸을 다 채웠다는 것이므로 스도미노쿠를 완성했다는 의미로 sudominoku의 값을 1로 지정한 뒤에 arr의 모든 값을 문제 조건에 맞게 출력한 뒤에 함수를 종료합니다.
이후에 스도미노쿠를 완성할 수 있는 다른 경우의 수가 있을 때 또 출력하지 않게 하기 위해서 sudominoku의 값이 1이라면 함수를 실행하지 않게 했습니다.
#include <stdio.h>
int n, arr[9][9], visited[10][10], sudominoku;
int sudoku(int dpth, int idx, int value) {
for (int i = 0; i < 9; i++) {
if (arr[dpth][i] == value) {
return 0;
}
if (arr[i][idx] == value) {
return 0;
}
}
int row = (dpth / 3) * 3;
int col = (idx / 3) * 3;
for (int i = row; i < row + 3; i++) {
for (int j = col; j < col + 3; j++) {
if (arr[i][j] == value) {
return 0;
}
}
}
return 1;
}
void dfs(int dpth, int idx) {
if (sudominoku) return;
if (idx == 9) {
dfs(dpth + 1, 0);
return;
}
if (dpth == 9) {
sudominoku = 1;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
printf("%d", arr[i][j]);
}
printf("\n");
}
return;
}
int dx[] = { 0, 1 };
int dy[] = { 1, 0 };
if (arr[dpth][idx] == 0) {
for (int i = 1; i <= 9; i++) {
if (sudoku(dpth, idx, i)) {
arr[dpth][idx] = i;
for (int k = 0; k < 2; k++) {
int nx = idx + dx[k];
int ny = dpth + dy[k];
if (nx < 9 && ny < 9 && arr[ny][nx] == 0) {
for (int j = 1; j <= 9; j++) {
if (i != j && !visited[i][j] && sudoku(ny, nx, j)) {
arr[ny][nx] = j;
visited[i][j] = visited[j][i] = 1;
dfs(dpth, idx + 1);
arr[ny][nx] = 0;
visited[i][j] = visited[j][i] = 0;
}
}
}
}
arr[dpth][idx] = 0;
}
}
return;
}
dfs(dpth, idx + 1);
}
main() {
int cnt = 1;
while (1) {
scanf("%d", &n);
if (n == 0) break;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
arr[i][j] = visited[i + 1][j + 1] = 0;
}
}
for (int i = 0; i < n; i++) {
int u, v, lu, lv;
char tmp1, tmp2;
scanf("%d %c%d %d %c%d", &u, &tmp1, &lu, &v, &tmp2, &lv);
visited[u][v] = visited[v][u] = 1;
arr[tmp1 - 'A'][lu - 1] = u;
arr[tmp2 - 'A'][lv - 1] = v;
}
getchar();
for (int i = 1; i <= 9; i++) {
int num;
char tmp;
scanf("%c%d ", &tmp, &num);
arr[tmp - 'A'][num - 1] = i;
}
sudominoku = 0;
printf("Puzzle %d\n", cnt++);
dfs(0, 0);
}
}자바
위의 C언어를 이용한 풀이와 동일한 방법으로 다른 점이라면 Stringbuilder를 이용하여 한꺼번에 출력한다는 것입니다.
위의 코드는 스도미노쿠가 완성될 때마다 완성된 보드를 출력하지만 이 코드는 마지막에 0이 입력이 되면 한꺼번에 출력합니다.
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] arr;
static boolean sudominoku;
static boolean[][] visited;
static StringBuilder sb = new StringBuilder();
public static boolean sudoku(int dpth, int idx, int value) {
for (int i = 0; i < 9; i++) {
if (arr[dpth][i] == value) {
return false;
}
if (arr[i][idx] == value) {
return false;
}
}
int row = (dpth / 3) * 3;
int col = (idx / 3) * 3;
for (int i = row; i < row + 3; i++) {
for (int j = col; j < col + 3; j++) {
if (arr[i][j] == value) {
return false;
}
}
}
return true;
}
public static void dfs(int dpth, int idx) {
if (sudominoku) return;
if (idx == 9) {
dfs(dpth + 1, 0);
return;
}
if (dpth == 9) {
sudominoku = true;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(arr[i][j]);
}
sb.append('\n');
}
return;
}
int[] dx = { 0, 1 };
int[] dy = { 1, 0 };
if (arr[dpth][idx] == 0) {
for (int i = 1; i <= 9; i++) {
if (sudoku(dpth, idx, i)) {
arr[dpth][idx] = i;
for (int k = 0; k < 2; k++) {
int nx = idx + dy[k];
int ny = dpth + dx[k];
if (ny < 9 && nx < 9 && arr[ny][nx] == 0) {
for (int j = 1; j <= 9; j++) {
if (i != j && !visited[i][j] && sudoku(ny, nx, j)) {
arr[ny][nx] = j;
visited[i][j] = visited[j][i] = true;
dfs(dpth, idx + 1);
arr[ny][nx] = 0;
visited[i][j] = visited[j][i] = false;
}
}
}
}
arr[dpth][idx] = 0;
}
}
return;
}
dfs(dpth, idx + 1);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cnt = 1;
while (true) {
int n = Integer.parseInt(br.readLine());
if (n == 0) break;
arr = new int[9][9];
visited = new boolean[10][10];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
String lu = st.nextToken();
int v = Integer.parseInt(st.nextToken());
String lv = st.nextToken();
visited[u][v] = visited[v][u] = true;
arr[lu.charAt(0) - 'A'][lu.charAt(1) - '1'] = u;
arr[lv.charAt(0) - 'A'][lv.charAt(1) - '1'] = v;
}
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 1; i <= 9; i++) {
String str = st.nextToken();
arr[str.charAt(0) - 'A'][str.charAt(1) - '1'] = i;
}
sudominoku = false;
sb.append("Puzzle ").append(cnt++).append("\n");
dfs(0, 0);
}
System.out.print(sb);
}
}
결론
스도쿠 문제를 풀 때 사용했던 코드를 그래프 탐색과 함께 응용하여 문제를 해결하였습니다. 문제가 길고 복잡해서 처음에 이해하기 어려웠지만 문제 조건을 천천히 다시 읽어보면서 필요한 것이 무엇인지 생각해냈습니다. 앞으로도 이런 복잡한 문제를 만났을 때 이러한 경험을 바탕으로 포기하지 않고 도전하는 사람이 되기 위해 노력해야겠습니다.
'백준 알고리즘 > 백트래킹' 카테고리의 다른 글
| 백준 16938번: 캠프 준비 (0) | 2022.07.12 |
|---|---|
| 백준 16936번: 나3곱2 (0) | 2022.07.07 |
| 백준 16945번: 매직 스퀘어로 변경하기 (0) | 2022.07.02 |
| 백준 2580번: 스도쿠 (3) | 2022.06.29 |
| 백준 9663번: N-Queen (0) | 2022.06.28 |