스도쿠 문제 풀이 정리 (LeetCode 36 & 37)

1. Valid Sudoku (문제 36)

문제

• 9×9 스도쿠 보드가 주어짐.
• 빈 칸은 '.'로 표시.
• 규칙:
  1. 각 행(row) 은 1~9 중복 없음
  2. 각 열(col) 은 1~9 중복 없음
  3. 각 3×3 박스도 중복 없음
• 아직 완성되지 않아도, 현재 보드가 유효한지 검사.

---

풀이 아이디어

• 행, 열, 박스별로 이미 등장한 숫자를 기록.
• 중복이 나타나면 false, 끝까지 없으면 true.
• Set을 활용하면 중복 검사 로직이 매우 간단해짐.

Java 코드 (Set 버전)

import java.util.*;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        List<Set<Character>> rows = new ArrayList<>();
        List<Set<Character>> cols = new ArrayList<>();
        List<Set<Character>> boxes = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            rows.add(new HashSet<>());
            cols.add(new HashSet<>());
            boxes.add(new HashSet<>());
        }

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char ch = board[r][c];
                if (ch == '.') continue;

                int b = (r / 3) * 3 + (c / 3);

                if (!rows.get(r).add(ch)) return false;
                if (!cols.get(c).add(ch)) return false;
                if (!boxes.get(b).add(ch)) return false;
            }
        }
        return true;
    }
}

핵심 포인트

• (r/3)*3 + (c/3) → 3×3 박스 번호 (0~8) 계산
• Set.add(x) → 처음 넣으면 true, 이미 있으면 false 반환
• 즉, 중복 = false 로직이 한 줄로 끝난다

 

Sudoku Solver (문제 37)

문제

• 9×9 스도쿠 보드가 주어짐.
• 빈칸(.)을 스도쿠 규칙에 맞게 채워서 완성해야 함.
• 항상 해답이 존재한다고 가정.

---

풀이 아이디어 (백트래킹)

1. 보드를 순회하다가 빈칸 발견 시
2. 숫자 1~9를 넣어봄 → isValid() 체크
3. 가능하다면 재귀적으로 다음 칸 진행
4. 막히면 되돌아오기(backtrack)
5. 모든 칸이 채워지면 완성

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }

    private boolean solve(char[][] board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    for (char d = '1'; d <= '9'; d++) {
                        if (isValid(board, r, c, d)) {
                            board[r][c] = d;
                            if (solve(board)) return true;
                            board[r][c] = '.'; // backtrack
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int r, int c, char d) {
        for (int i = 0; i < 9; i++) {
            if (board[r][i] == d) return false; // 행
            if (board[i][c] == d) return false; // 열
            int boxRow = (r / 3) * 3 + i / 3;
            int boxCol = (c / 3) * 3 + i % 3;
            if (board[boxRow][boxCol] == d) return false; // 박스
        }
        return true;
    }
}

핵심 포인트

• 백트래킹(DFS): 가능한 숫자를 넣고 → 안 되면 되돌리기.
• isValid() 로직은 사실상 Valid Sudoku 문제에서 쓴 로직 그대로 재활용.
• 박스 탐색:

int boxRow = (r / 3) * 3 + i / 3;
int boxCol = (c / 3) * 3 + i % 3;

→ 박스 시작점 + offset으로 3×3 박스의 9칸 순회.

3. 두 문제의 차이

• Valid Sudoku (36번): 현재 상태가 규칙 위반인지 검사만.
• Sudoku Solver (37번): 실제로 빈칸을 채워서 완성하기.
• Solver에서는 Valid 로직을 isValid() 함수로 재활용해서 백트래킹에 적용.

마무리

스도쿠 문제 두 개는 중복 검사(Set 활용) + 백트래킹 기본기를 모두 연습할 수 있는 좋은 문제입니다.

• 36번으로 중복 검사 로직 감 잡기
• 37번에서 백트래킹까지 확장하기