글 읽기 - 백트레킹 초기화 질문입니다.

bsy1343 5년 전 1

문제를 풀고 정답은 맞았지만 조금 의아했던 부분이 있어서 질문드립니다.

54번째 row에서 백트레킹 초기화를 안해도 예제와 반례등의 답은 제대로 나오는데

저기서 초기화 0을 안하고, 답안 제출시 틀립니다.

초기화를 안했을때 어떠한 이유로 답이 틀리게 되는걸까요?

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

public class Main {
	static int[][] Map = new int[9][9];
	static LinkedList<Node> list = new LinkedList<>();
	static class Node {
		int x, y;
		Node(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for (int i = 0; i < 9; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++) {
				Map[i][j] = Integer.parseInt(st.nextToken());
				if (Map[i][j] == 0) {
					list.add(new Node(i, j));
				}
			}
		}
		
		backTracking(0);
	}
	
	static void log() {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				System.out.print(Map[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	static boolean backTracking(int cnt) {
		if (list.size() == cnt) {
			log();
			return true;
		}
		int sx = list.get(cnt).x;
		int sy = list.get(cnt).y;
		for (int n = 1; n < 10; n++) {
			if (isSetting(sx, sy, n)) {
				Map[sx][sy] = n;
				if (backTracking(cnt+1)) {
					return true;
				}
				// Map[sx][sy] = 0;
			}
		}
		
		return false;
	}
	
	static boolean isSetting(int x, int y, int n) {
		if (chkCol(x, n) && chkRow(y, n) && chkBox(x, y, n)) {
			return true;
		}
		return false;
	}

	static boolean chkCol(int x, int n) {
		for (int i = 0; i < 9; i++) {
			if (Map[x][i] == n) {
				return false;
			}
		}
		return true;
	}

	static boolean chkRow(int y, int n) {
		for (int i = 0; i < 9; i++) {
			if (Map[i][y] == n) {
				return false;
			}
		}
		return true;
	}

	static boolean chkBox(int x, int y, int n) {
		int sx = x / 3 * 3;
		int sy = y / 3 * 3;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (Map[i+sx][j+sy] == n) {
					return false;
				}
			}
		}
		return true;
	}
}

djm03178 5년 전 1

초기화를 하지 않은 것 때문에 백트래킹의 이전 좌표들에서 원래 넣어볼 수 있는 값을 넣어보지 못하게 될 수 있습니다.

bsy1343 5년 전 1

혹시 그 경우의 예를 가르쳐 주실수 있을까요?

그 부분이 잘 이해가 가지 않아서요.. 백트레킹은 항상 알았다 싶다가도 모르겠더라구요...

djm03178 5년 전 3

스도쿠는 하나만 틀어져도 답이 쫙 바뀌기 때문에 완전한 예제를 드리기는 좀 어렵네요.

대략적인 예를 들어서, 1행에 1열, 5열이 처음에 비어있고, 1열은 1, 3이 가능하고 5열은 2, 3이 가능하다고 해봅시다. 처음에 1열에 1을 채웠는데 5열에는 2, 3을 차례대로 채워봤지만 마지막까지 채우는 데에 실패했다고 합시다. 그러면 다시 1열로 돌아와서 이번에는 3을 시도해봐야 하는데, 아까 5열에 채워두고 떠난 3이 그대로 남아있어서 1열에 3을 채워보지도 못하고 check에 걸리게 됩니다.

bsy1343 5년 전 0

오오, 이해했어요~!!!!

매번 감사드립니다~~!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

백트레킹 초기화 질문입니다.

bsy1343 5년 전 1

djm03178 5년 전 1

bsy1343 5년 전 1

djm03178 5년 전 3

bsy1343 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말