[BOJ2580] 스도쿠 (Java, 백트래킹, 비트 마스크)알고리즘/완전 탐색2025. 1. 14. 20:10
Table of Contents
반응형
문제 링크
https://www.acmicpc.net/problem/2580
풀이
- 백트래킹, 비트 마스킹으로 문제 해결
문제를 한번만 읽고 풀다가 유효성 검사에서 3 * 3 그리드를 누락하여 "틀렸습니다"를 맛 보았다..🥹
스도쿠의 필드가 0인 영역을 채울 때 유효성 검사를 총 3가지를 수행해야 했다
① 행
② 열
③ 3 * 3 그리드 영역
rows, cols, boxes 각 배열을 사용하여 비트 마스킹을 표현하고, 유효성 검사를 하도록 하였다
private static long[] rows;
private static long[] cols;
private static long[] boxes;
입력 데이터 초기화시
값이 0인 경우 리스트에 좌표 정보를 담고, 나머지의 경우 비트 마스킹 표기를 할 수 있도록 하였다.
이때 3 * 3 그리드 영역의 경우 아래와 같이 그룹을 나눠서 비트 마스킹 정보를 저장하도록 하였다
pos = (i / 3 ) * 3 + (j / 3)
boxes[pos] |= 1L << value;
0 | 1 | 2 |
3 | 4 | 5 |
6 | 7 | 8 |
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int v = inputProcessor.nextInt();
int pos = (i / 3) * 3 + (j / 3);
if(v == 0) {
points.add(new int[] {i, j});
continue;
}
maps[i][j] = v;
rows[i] |= 1L << v;
cols[j] |= 1L << v;
boxes[pos] |= 1L << v;
}
}
리스트에 0에 해당 하는 좌표 정보가 저장되어 있기 때문에
idx = 0부터 시작해서 순차적으로 재귀함수를 호출하여 points.size()와 같아졌을때 유효성 검사를 수행하고 최종 정답을 기록한다
이때 유효성 검사를 수행할 때 마찬가지로 행, 열, 3 * 3 그리드 모두 확인해야 한다
비트 마스킹 관련
shift 연산을 하게 되면 기본적으로 아래와 같다
- 1 << 1 은 10(2진수) , 2(10진수)
- 1 << 2 는 100(2진수), 4(10진수)
(이하 생략)
방문 여부를 표시할 때 or 연산 사용
rows[x] |= (1 << num)
방문 여부를 해재를 할 때 and와 not 연산 사용
rows[x] &= ~(1 << num)
예로 num = 1일때
1 << 1 은 10(2진수) , 2(10진수) 이 되어 rows[x]에 방문 표시 된다
그리고 방문 해제를 할 때
~(1 << 1) 은 01(2진수), 1(10진수)가 되어 and 연산을 통해 rows[x]에 방문 해제 표시 된다
마지막 1 ~ 9 비트 전부 켜져있는지 확인할 때
- 1 << 10 = 10/000/000/000
- (1 << 10) -1 = 1/111/111/111 이 되는데 마지막에 0번 비트가 켜져 있다
- 그러므로 -1을 한번 더 해주면 (1 << 10) - 2 = 1/111/111/110 이 되어 유효성 검사를 올바르게 할 수 있다
제출 코드
import java.util.*;
import java.io.*;
public class Main {
private static StringBuilder sb = new StringBuilder();
private static InputProcessor inputProcessor = new InputProcessor();
public static void main(String[] args) {
input();
pro();
output();
}
private static final int N = 9;
private static final long allComplete = (1 << 10) - 2;
private static int[][] maps;
private static long[] rows;
private static long[] cols;
private static long[] boxes;
private static List<int[]> points;
private static boolean finished = false;
private static void input() {
maps = new int[N][N];
rows = new long[N];
cols = new long[N];
boxes = new long[N]; // 서브 그리드 3 * 3
points = new ArrayList<>();
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int v = inputProcessor.nextInt();
int pos = (i / 3) * 3 + (j / 3);
if(v == 0) {
points.add(new int[] {i, j});
continue;
}
maps[i][j] = v;
rows[i] |= 1L << v;
cols[j] |= 1L << v;
boxes[pos] |= 1L << v;
}
}
}
private static void pro() {
backTracking(0);
}
private static void backTracking(int idx) {
if(finished) return;
if(idx == points.size()) {
boolean isValid = true;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
int pos = (i / 3) * 3 + (j / 3);
if(rows[i] != allComplete || cols[j] != allComplete || boxes[pos] != allComplete) {
isValid = false;
break;
}
}
}
if(isValid) {
finished = true;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
sb.append(maps[i][j]).append(" ");
}
sb.append("\n");
}
}
return;
}
int[] point = points.get(idx);
int x = point[0];
int y = point[1];
int pos = (x / 3) * 3 + (y / 3);
for(int i = 1; i <= N; i++) {
long flag = 1L << i;
// 행, 열, 그리드 안에서 flag 사용여부
if((rows[x] & flag) != 0
|| (cols[y] & flag) != 0
|| (boxes[pos] & flag) != 0) continue;
rows[x] |= flag;
cols[y] |= flag;
boxes[pos] |= flag;
maps[x][y] = i;
backTracking(idx + 1);
maps[x][y] = 0;
rows[x] &= ~flag;
cols[y] &= ~flag;
boxes[pos] &= ~flag;
}
}
private static void output() {
try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
bw.write(sb.toString());
bw.flush();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
private static class InputProcessor {
private BufferedReader br;
private StringTokenizer st;
public InputProcessor() {
this.br = new BufferedReader(new InputStreamReader(System.in));
}
public String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return st.nextToken();
}
public String nextLine() {
String result = "";
try {
result = br.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return result;
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
}
}
반응형
'알고리즘 > 완전 탐색' 카테고리의 다른 글
[BOJ10597] 순열장난 (Java, 백트래킹) (0) | 2025.01.17 |
---|---|
[BOJ2661] 좋은 수열 (Java, 백트래킹) (1) | 2025.01.15 |
[BOJ19236] 청소년 상어 (Java, 백트래킹, 시뮬레이션) (0) | 2025.01.06 |
[BOJ20166] 문자열 지옥에 빠진 호석 (완전탐색, DFS) (0) | 2023.08.31 |
[BOJ20164] 홀수 홀릭 호석 (완전탐색) (0) | 2023.08.30 |
@leejinwoo1126 :: 천천히 하나씩
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!