[백준] 2580.스도쿠 / BackTracking

@BackTracking / 1h 4m

40분만에 풀었는데 시간초과 떠서 그거 잡느라 좀 오래 걸림

 

문제 링크

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

 

구현 포인트

원래 check라는 함수를 두고 모든 칸을 다 채운 후 가로줄, 세로줄, 3*3칸에 중복되는 숫자가 없을 때에만 맵을 출력하고 종료하게 했다.

그런데 이 중복체크를 안 해도 풀린다!

 

1. 3차원 visit 사용하기

visit[행][열][1부터 9까지의 값]

으로 그 칸에 들어갈 수 없는 값들에 대해 visit을 체크한다.

예를 들면 0,0 칸에 보면 1을 제외한 모든 값이 이미 같은 행에 들어 있으므로

visit[0][0][1]을 제외한 visit[0][0][2]부터 visit[0][0][9]는 체크가 되어있다.

 

2. int형으로 visit 체크하기

이 문제도 포인트는 N-Queen에서 사용한 방법과 같은, int형으로 visit을 체크하는 것이다.

 

visit 체크하고

BackTracking

visit 체크 지우기

 

boolean형으로 이렇게 하게 되면, 기존에 체크되어 있던 값까지 지워지게 된다.

그래서 체크할때는 +1, 지울때는 -1을 해주면

값이 양수이면 이미 체크된 것으로 볼 수 있기 때문에, 지금 체크를 지운다 해도 이전 visit에 영향을 미치지 않는다.

 

이 1, 2번 방법을 사용하면

가능한 값만 넣기 때문에 굳이 중복체크를 하지 않아도 풀린다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main_200908 {
	
	static class Node {
		int x, y;
		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	static int N, map[][], visit[][][];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		map = new int[9][9];
		for (int i = 0; i < 9; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++)
				map[i][j] = Integer.parseInt(st.nextToken());
		}
		
		visit = new int[9][9][10];
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++)
				if (map[i][j] != 0)
					marking(i, j, map[i][j], 1);
		
		backTracking(0);
	}

	private static void marking(int x, int y, int val, int count) {
		int xStart = x / 3 * 3;
		int yStart = y / 3 * 3;

		for (int k = 0; k < 9; k++) {
			visit[x][k][val] += count;
			visit[k][y][val] += count;
		}
		
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				visit[xStart + i][yStart + j][val] += count;
	}

	private static boolean backTracking(int num) {
		Node temp = findStart(num / 9);
		int x = temp.x;
		int y = temp.y;
		if (temp.x == -1) {
			print();
			return true;
		}
		
		for (int i = 1; i <= 9; i++) {
			if (visit[x][y][i] > 0) continue;
			
			marking(x, y, i, 1);
			map[x][y] = i;
			if (backTracking(x * 9 + y + 1)) return true;
			
			marking(x, y, i, -1);
			map[x][y] = 0;
		}
		return false;
	}

	private static void print() {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				sb.append(map[i][j] + " ");
			sb.append("\n");
		}
		System.out.println(sb);
	}

	private static Node findStart(int x) {
		for (int i = x; i < 9; i++)
			for (int j = 0; j < 9; j++)
				if (map[i][j] == 0)
					return new Node(i, j);
		return new Node(-1, -1);
	}
}

+ BackTracking 함수를 boolean형으로 했는데,

void로 바꾸니까 틀렸습니다가 떴다.

 

이유는, boolean형으로 하면 딱 한번만 돌고 종료되는데,

void의 경우 가능한 모든 경우를 출력하기 때문!

그래서 void로 쓰고싶다면 그냥 return이 아니라 System.exit(0);을 써서 딱 한번만 출력하게 해 줘야 한다.

이렇게!

private static void backTracking(int num) {
		Node temp = findStart(num / 9);
		int x = temp.x;
		int y = temp.y;
		if (temp.x == -1) {
			print();
			System.exit(0);
		}
		
		for (int i = 1; i <= 9; i++) {
			if (visit[x][y][i] > 0) continue;
			
			marking(x, y, i, 1);
			map[x][y] = i;
			backTracking(x * 9 + y + 1);
			
			marking(x, y, i, -1);
			map[x][y] = 0;
		}
}

개인적으로는 boolean형이 더 나은 것 같다.

 

처음에는 좀 답답했는데

풀고 나니 좋은 문제라고 생각함!

끗!