백준_스도미노쿠_4574

// 알고리즘

1. 백트래킹

 

2. 2차원 방문배열 사용

 -> (1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, ...) 과 같이 사용할 수 있는 블록이 (x,y)형태로

     주어지기 때문에 2차원 배열 사용

 -> 기존 스도쿠처럼 하나씩 값을 변경하는 문제가 아닌 2칸의 블록 형태로 집어 넣는 문제 임.

 

3. 오른쪽 / 아래를 탐색하는 배열

 -> 왼쪽 위부터 하나 씩 채워지기 때문에 오른쪽과 아래만 탐색하면 됨.

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

public class 스도미노쿠_4574 {

	static int N;
	static boolean flag;
	static boolean[][] v;
	static int[] dr = { 0, 1 }; // 우 하
	static int[] dc = { 1, 0 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = 1;
		while (true) {
			N = Integer.parseInt(br.readLine());
			if (N == 0)
				break;

			int[][] map = new int[9][9];
			v = new boolean[10][10];
			flag = false;

			int num1, num2;
			String str1, str2;
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				num1 = Integer.parseInt(st.nextToken());
				str1 = st.nextToken();
				num2 = Integer.parseInt(st.nextToken());
				str2 = st.nextToken();

				v[num1][num2] = true;
				v[num2][num1] = true;

				map[str1.charAt(0) - 65][str1.charAt(1) - '1'] = num1;
				map[str2.charAt(0) - 65][str2.charAt(1) - '1'] = num2;
			}

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int i = 1; i <= 9; i++) {
				str1 = st.nextToken();
				map[str1.charAt(0) - 65][str1.charAt(1) - '1'] = i;
			}

			// 알고리즘
			System.out.printf("Puzzle %d\n", num++);
			cal(map, 0);

		}

	}

	private static void cal(int[][] map, int idx) {
		if (flag)
			return;
		if (idx == 81) {
			flag = true;
			print(map);
			return;
		}

		int r = idx / 9;
		int c = idx % 9;

		if (map[r][c] != 0) {
			cal(map, idx + 1);
			return;
		}
		for (int k = 0; k < 2; k++) {
			int nr = r + dr[k];
			int nc = c + dc[k];
			if (nr < 0 || nc < 0 || nr >= 9 || nc >= 9 || map[nr][nc] != 0)
				continue;
			for (int i = 1; i < 10; i++) {
				for (int j = 1; j < 10; j++) {
					if (i == j || v[i][j] || !check(j, map, nr, nc) || !check(i, map, r, c))
						continue;
					map[r][c] = i;
					v[i][j] = true;
					v[j][i] = true;
					map[nr][nc] = j;
					cal(map, idx + 1);
					map[nr][nc] = 0;
					v[i][j] = false;
					v[j][i] = false;
					map[r][c] = 0;

				}
			}
		}

	}

	private static boolean check(int idx, int[][] map, int r, int c) {

		int row = r / 3 * 3;
		int col = c / 3 * 3;

		// 3 X 3 검사
		for (int i = row; i < row + 3; i++) {
			for (int j = col; j < col + 3; j++) {
				if (map[i][j] == idx)
					return false;
			}
		}

		// 행 검사
		for (int i = 0; i < map.length; i++) {
			if (map[r][i] == idx)
				return false;
		}

		// 열 검사
		for (int i = 0; i < map.length; i++) {
			if (map[i][c] == idx)
				return false;
		}

		return true;
	}

	private static void print(int[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();

		}

	}

}

 

※ 알고리즘이나 체크함수, 탐색배열 등 문제해결에 필요한 모든 조건들은 다 생각 하고 구현했지만 탈출조건, 재귀들어갈 때를 잘 못 찾아서 고전했음. 또한 입출력처리하는 부분도 기존 문제와 다르게 까다로움. 

- 탈출조건을 생각해서 재귀를 구현하는 연습이 필요할 듯.