[백준] 4574. 스도미노쿠

April 21, 2021 6 분 소요

문제 링크

[백준] 4574. 스도미노쿠

풀이 과정

시뮬레이션 문제이며, 최악의 경우 모든 경우를 다 찾아봐야 하는 완전 탐색 문제입니다.

문제 조건은 다음과 같습니다.

9X9 크기의 스도미노쿠 그리드에는 1부터 9까지의 숫자가 하나씩 써있다. 즉, 81칸 중 9칸이 미리 채워져 있다.
숫자 2개가 인접하게 쓰여져 있는 도미노를 이용해서만 그리드를 채워야 한다.
각각의 행, 열, 3X3 크기의 정사각형에는 1부터 9까지의 숫자가 단 한 번만 나타난다.

코드를 보며 설명하겠습니다.

static int[] charArrToIntArr(char[] charArr) {
    return new int[]{charArr[0] - 'A', charArr[1] - '0' - 1};
}

static int getSquareIdx(int x, int y) {
    return x / 3 * 3 + y / 3;
}

static boolean canPut(int x, int y, int num) {
    return !row[x][num] && !col[y][num] && !square[getSquareIdx(x, y)][num];
}

먼저 부가적인 기능을 하는 메소드들입니다.

charArrToIntArr : 도미노 좌표는 B2 와 같이 문자열로 주어집니다. 이를 9X9 크기의 좌표 인덱스에 맞게 변환하는 메소드입니다.
getSquareIdx : 좌표 (x, y) 가 어느 정사각형에 포함되어 있는지 그 인덱스를 반환하는 함수입니다. 각 정사각형 9개의 인덱스는 아래 그림과 같습니다.
canPut : 좌표 (x, y)에 숫자 num 을 둘 수 있는지를 체크하는 메소드입니다.
- 해당 좌표의 행, 열, 정사각형에서 숫자 num 을 사용하지 않았으면 true를,
- 사용했으면 false 를 리턴합니다.

for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    int U, V;
    int[] LU, LV;

    U = Integer.parseInt(st.nextToken());
    LU = charArrToIntArr(st.nextToken().toCharArray());
    V = Integer.parseInt(st.nextToken());
    LV = charArrToIntArr(st.nextToken().toCharArray());

    map[LU[0]][LU[1]] = U;
    map[LV[0]][LV[1]] = V;

    row[LU[0]][U] = col[LU[1]][U] = row[LV[0]][V] = col[LV[1]][V] = true;
    square[getSquareIdx(LU[0], LU[1])][U] = square[getSquareIdx(LV[0], LV[1])][V] = true;
    domino[U][V] = domino[V][U] = true;
}

문제에서 주어진 N개 만큼의 도미노들을 입력 받습니다.

도미노에 쓰여 있는 두 숫자에 대해, U와 U가 쓰여있는 좌표 LU, V와 V가 쓰여 있는 좌표 LV를 받습니다.
올바르게 변환된 좌표를 통해 2차원 맵에 표시합니다.
각 좌표가 포함된 행, 열, 정사각형에 해당 숫자가 쓰여져 있다고 체크하고, 동시에 도미노 사용 여부도 체크해줍니다.

for (int num = 1; num <= SIZE; num++) {
    int[] pos = charArrToIntArr(st.nextToken().toCharArray());

    map[pos[0]][pos[1]] = num;

    row[pos[0]][num] = col[pos[1]][num] = true;
    square[getSquareIdx(pos[0], pos[1])][num] = true;
    domino[num][num] = true;
}

9X9 스도미노쿠 그리드에 쓰여진 1부터 9까지의 숫자 위치를 입력받습니다. 위의 도미노를 입력받을 때와 동일한 작업을 실행합니다.

올바르게 변환된 좌표를 통해 2차원 맵에 표시합니다.
각 좌표가 포함된 행, 열, 정사각형에 해당 숫자가 쓰여져 있다고 체크하고, 동시에 도미노 사용 여부도 체크해줍니다.

static void dfs(int cnt) {
    if (cnt == 81) {
        found = true;
        answer.append("Puzzle " + TC + "\n");

        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                answer.append(map[i][j]);
            }
            answer.append('\n');
        }

        return;
    }

    if (found) return;

    int x = cnt / 9, y = cnt % 9;

    if (map[x][y] != 0) {
        dfs(cnt + 1);
        return;
    }

    for (int first = 1; first <= SIZE; first++) {
        if (canPut(x, y, first)) {
            row[x][first] = col[y][first] = square[getSquareIdx(x, y)][first] = true;
            map[x][y] = first;

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];

                if (!isInRange(nx, ny) || map[nx][ny] != 0) continue;

                for (int second = 1; second <= SIZE; second++) {
                    if (!domino[first][second] && !domino[second][first] && canPut(nx, ny, second)) {
                        row[nx][second] = col[ny][second] = square[getSquareIdx(nx, ny)][second] = true;
                        map[nx][ny] = second;
                        domino[first][second] = domino[second][first] = true;

                        dfs(cnt + 1);

                        row[nx][second] = col[ny][second] = square[getSquareIdx(nx, ny)][second] = false;
                        map[nx][ny] = 0;
                        domino[first][second] = domino[second][first] = false;
                    }
                }
            }

            row[x][first] = col[y][first] = square[getSquareIdx(x, y)][first] = false;
            map[x][y] = 0;
        }
    }
}

dfs 메소드 는 도미노를 둘 수 있는 모든 경우를 확인하며, 스도쿠를 풀었다면 답을 저장해두는 작업을 실행합니다. 로직은 다음과 같습니다.

cnt 가 81이면, 모든 칸을 채웠음을 의미합니다. 정답을 적어두는 StringBuilder 객체에 맵을 저장하고 리턴합니다.
아직 마지막 칸에 도달하지 못했다면, 아래 과정을 수행합니다.
1. 칸 번호 cnt 를 통해 좌표 (x, y)를 구합니다.
  - 그 칸이 이미 채워져 있다면 다음 칸으로 건너뜁니다.
2. 채워져 있지 않다면 둘 수 있는 도미노를 모두 둬봅니다.

for (int first = 1; first <= SIZE; first++) {
    if (canPut(x, y, first)) {
        row[x][first] = col[y][first] = square[getSquareIdx(x, y)][first] = true;
        map[x][y] = first;

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];

            if (!isInRange(nx, ny) || map[nx][ny] != 0) continue;

            for (int second = 1; second <= SIZE; second++) {
                if (!domino[first][second] && !domino[second][first] && canPut(nx, ny, second)) {
                    row[nx][second] = col[ny][second] = square[getSquareIdx(nx, ny)][second] = true;
                    map[nx][ny] = second;
                    domino[first][second] = domino[second][first] = true;

                    dfs(cnt + 1);

                    row[nx][second] = col[ny][second] = square[getSquareIdx(nx, ny)][second] = false;
                    map[nx][ny] = 0;
                    domino[first][second] = domino[second][first] = false;
                }
            }
        }

        row[x][first] = col[y][first] = square[getSquareIdx(x, y)][first] = false;
        map[x][y] = 0;
    }
}

위 for 문은 dfs 메소드 내에 도미노를 두는 작업을 수행합니다. 모든 비어있는 좌표 (x, y) 에 숫자 first 를 둘 수 있다면 아래 과정을 수행합니다.

행, 열, 정사각형에 숫자 first 를 사용했음을 표시합니다.
상하좌우 인접한 네 곳에 숫자 second 를 둘 수 있으면 아래 과정을 수행합니다.
1. 행, 열, 정사각형에 숫자 second 를 사용했음을 표시합니다.
2. 다음 칸으로 이동합니다.
3. 행, 열, 정사각형에 숫자 second 사용 여부를 되돌려줍니다.
행, 열, 정사각형에 숫자 first 사용 여부를 되돌려줍니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int SIZE = 9;
    static int N;
    static int[][] map;
    static boolean[][] row, col, square, domino;
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    static StringBuilder answer = new StringBuilder();
    static int TC = 0;
    static boolean found;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while ((N = Integer.parseInt(br.readLine().trim())) != 0) {
            TC++;
            found = false;
            map = new int[SIZE][SIZE];
            row = new boolean[SIZE][SIZE + 1];
            col = new boolean[SIZE][SIZE + 1];
            square = new boolean[SIZE][SIZE + 1];
            domino = new boolean[SIZE + 1][SIZE + 1];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int U, V;
                int[] LU, LV;

                U = Integer.parseInt(st.nextToken());
                LU = charArrToIntArr(st.nextToken().toCharArray());
                V = Integer.parseInt(st.nextToken());
                LV = charArrToIntArr(st.nextToken().toCharArray());

                map[LU[0]][LU[1]] = U;
                map[LV[0]][LV[1]] = V;

                row[LU[0]][U] = col[LU[1]][U] = row[LV[0]][V] = col[LV[1]][V] = true;
                square[getSquareIdx(LU[0], LU[1])][U] = square[getSquareIdx(LV[0], LV[1])][V] = true;
                domino[U][V] = domino[V][U] = true;
            }

            st = new StringTokenizer(br.readLine());

            for (int num = 1; num <= SIZE; num++) {
                int[] pos = charArrToIntArr(st.nextToken().toCharArray());

                map[pos[0]][pos[1]] = num;

                row[pos[0]][num] = col[pos[1]][num] = true;
                square[getSquareIdx(pos[0], pos[1])][num] = true;
                domino[num][num] = true;
            }

            dfs(0);
        }

        System.out.println(answer);
    }

    static void dfs(int cnt) {
        if (cnt == 81) {
            found = true;
            answer.append("Puzzle " + TC + "\n");

            for (int i = 0; i < SIZE; i++) {
                for (int j = 0; j < SIZE; j++) {
                    answer.append(map[i][j]);
                }
                answer.append('\n');
            }

            return;
        }

        if (found) return;

        int x = cnt / 9, y = cnt % 9;

        if (map[x][y] != 0) {
            dfs(cnt + 1);
            return;
        }

        for (int first = 1; first <= SIZE; first++) {
            if (canPut(x, y, first)) {
                row[x][first] = col[y][first] = square[getSquareIdx(x, y)][first] = true;
                map[x][y] = first;

                for (int d = 0; d < 4; d++) {
                    int nx = x + dx[d], ny = y + dy[d];

                    if (!isInRange(nx, ny) || map[nx][ny] != 0) continue;

                    for (int second = 1; second <= SIZE; second++) {
                        if (!domino[first][second] && !domino[second][first] && canPut(nx, ny, second)) {
                            row[nx][second] = col[ny][second] = square[getSquareIdx(nx, ny)][second] = true;
                            map[nx][ny] = second;
                            domino[first][second] = domino[second][first] = true;

                            dfs(cnt + 1);

                            row[nx][second] = col[ny][second] = square[getSquareIdx(nx, ny)][second] = false;
                            map[nx][ny] = 0;
                            domino[first][second] = domino[second][first] = false;
                        }
                    }
                }

                row[x][first] = col[y][first] = square[getSquareIdx(x, y)][first] = false;
                map[x][y] = 0;
            }
        }
    }

    static int[] charArrToIntArr(char[] charArr) {
        return new int[]{charArr[0] - 'A', charArr[1] - '0' - 1};
    }

    static int getSquareIdx(int x, int y) {
        return x / 3 * 3 + y / 3;
    }

    static boolean canPut(int x, int y, int num) {
        return !row[x][num] && !col[y][num] && !square[getSquareIdx(x, y)][num];
    }

    static boolean isInRange(int x, int y) {
        return x >= 0 && x < SIZE && y >= 0 && y < SIZE;
    }
}

Twitter Facebook LinkedIn

김무성

[백준] 4574. 스도미노쿠

문제 링크

풀이 과정

코드

공유하기

댓글남기기

참고

[프로그래머스] 67256. 키패드 누르기

[프로그래머스] 72410. 신규 아이디 추천

[프로그래머스] 81301. 숫자 문자열과 영단어

[JavaScript] 문자열을 정수로 변환하는 세 가지 방법