https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
스도쿠가 주어지고 빈칸을 채우는 문제입니다.
일단 스도쿠를 완성하기 위한 조건으로
3*3 구역, 가로, 세로에 모두 다른 숫자가 와야합니다.
우선 빈칸이 0으로 되어있기때문에 ArrayList에 빈칸의 좌표를 모두 넣습니다.
그런 다음 이 빈칸들을 가지고 백트래킹을 돌립니다.
현재 좌표에서 1~9를 모두 넣어보고 조건에 맞으면 다음 좌표로 넘어가는 식으로 계속 탐색해주시면 되겠습니다.
모든 빈칸을 다 채웠을 때 출력해주시면 됩니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 | import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static StringTokenizer st; static char div[][] = { { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' }, { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' }, { 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c' }, { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'd', 'd', 'd', 'e', 'e', 'e', 'f', 'f', 'f' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' }, { 'g', 'g', 'g', 'h', 'h', 'h', 'i', 'i', 'i' } }; static boolean cols[][] = new boolean[9][10]; static boolean rows[][] = new boolean[9][10]; static boolean visit[][] = new boolean[9][10]; static int list[][] = new int[9][9]; static ArrayList<int[]> e = new ArrayList<>(); static boolean chk; static void dfs(int idx) { if (idx == e.size()) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { System.out.print(list[i][j] + " "); } System.out.println(); } chk = true; return; } int x = e.get(idx)[0]; int y = e.get(idx)[1]; for (int i = 1; i <= 9; i++) { if (rows[x][i] || cols[y][i] || visit[div[x][y] - 'a'][i]) continue; rows[x][i] = true; cols[y][i] = true; visit[div[x][y] - 'a'][i] = true; list[x][y] = i; dfs(idx + 1); if (chk) return; list[x][y] = 0; rows[x][i] = false; cols[y][i] = false; visit[div[x][y] - 'a'][i] = false; } } static void input() throws Exception { for (int i = 0; i < 9; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < 9; j++) { list[i][j] = Integer.parseInt(st.nextToken()); if (list[i][j] == 0) { e.add(new int[] { i, j }); } else { cols[j][list[i][j]] = true; rows[i][list[i][j]] = true; visit[div[i][j] - 'a'][list[i][j]] = true; } } } } public static void main(String[] args) throws Exception { input(); dfs(0); } } | cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 15650 N 과 M (2) (0) | 2021.01.26 |
|---|---|
| boj 15649 N 과 M (1) (0) | 2021.01.26 |
| boj 1759 암호 만들기 (0) | 2021.01.22 |
| boj 1062 가르침 (0) | 2021.01.22 |
| boj 9663 N-Queen (0) | 2021.01.22 |