[SWEA] D2 - 1974번 | 스도쿠 검증

🔍 문제 보러 가기

입력으로 9 X 9 크기의 스도쿠 퍼즐의 숫자들이 주어졌을 때, 위와 같이 겹치는 숫자가 없을 경우, 1을 정답으로 출력하고 그렇지 않을 경우 0 을 출력한다.

내 코드

package D2;

import java.util.*;

public class N1974 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int T = scanner.nextInt();
		int N = 9;
		
		StringBuilder result = new StringBuilder();
		
		for (int t = 1; t <= T; t++) {
			int[][] arr = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = scanner.nextInt();
				}
			}
		
			result.append(String.format("#%d %d\n", t, solution(arr, N)));
		}
		System.out.print(result);
		scanner.close();
	}
	
	public static int solution(int[][] arr, int N) {
		
		// 가로 탐색 
		for (int i = 0; i < N; i++) {
			// 정답이 아닌 경우 0을 리턴하고 함수 종료
			if (finder(arr[i]) == 0) {
				return 0;
			}
		}
		
		// 세로 탐색 
		for (int i = 0; i < N; i++) {
			
			// 1열을 1차원 배열로 만들어서 검사
			int[] line = new int[N];
			for (int x = 0; x < arr.length; x++) {
				line[x] = arr[x][i];
			}
			
			// 정답이 아닌 경우 0을 리턴하고 함수 종료
			if (finder(line) == 0) {
				return 0;
			}
		}
		
		// 격자 탐색 
		for (int i = 0; i < arr.length; i += 3) {
			for (int j = 0; j < arr.length; j += 3) {
				
				// 한 격자를 1차원 배열로 만들어서 검사
				int[] line = new int[N];
				int index = 0;
				
				for (int x = 0; x < 3; x++) {
					for (int y = 0; y < 3; y++) {
						line[index++] = arr[i + x][j + y];
					}
				}
				
				// 정답이 아닌 경우 0을 리턴하고 함수 종료
				if (finder(line) == 0) {
					return 0;
				}
			}
		}
		
		// 모든 검사를 통과했으므로 정답 스도쿠이므로 1을 리턴
		return 1;
	}
	
	// 1차원 배열에서 탐색, 정답이면 1,정답이 아니면 0
	public static int finder(int[] line) {
		
		int[] arr = new int[10]; // 0 - 9 (1부터 9만 사용)
		
		for (int i = 0; i < line.length; i++) {
			arr[line[i]] += 1;
		}		
		
		// 모든 숫자가 1개씩 들어있는지 확인
		for (int i = 1; i < arr.length; i++) {
			// 숫자 i 가 없거나 1개 초과로 들어있는 경우는 틀린 스도쿠이므로 0 리턴
			if (arr[i] == 0 || arr[i] > 1) {
				return 0;
			}
		}
		
		return 1;
	}
}

접근 방법

1. 가로 탐색, 세로 탐색, 격자 탐색 순으로 진행한다.

2. 각 행(열, 격자)에서 각 숫자가 1번씩 나오는지를 확인하기 위해서 배열을 선언해서 사용한다.

3. 각 행(열, 격자)을 순회하면서 숫자에 해당하는 인덱스의 배열 값에 1 증가시킨다.

4. 해당 배열을 순회하면서 비어있거나 1 초과로 들어있는지 확인한다. 해당 경우는 틀린 스도쿠이므로 0을 리턴한다.

5. 세로 탐색, 격자 탐색인 경우 1차원 배열로 추출해 탐색을 진행한다.

개선 코드

package D2;

//SWEA D2 1974번 "스도쿠 검증" 문제 풀이 개선

import java.util.*;

public class N1974_b {
	
	public static final int N = 9;
	public static final int n = 3;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int T = scanner.nextInt();
		
		StringBuilder result = new StringBuilder();
		
		for (int t = 1; t <= T; t++) {
			int[][] arr = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					arr[i][j] = scanner.nextInt();
				}
			}
		
			result.append(String.format("#%d %d\n", t, solution(arr)));
		}
		System.out.print(result);
		scanner.close();
	}
	
	public static int solution(int[][] arr) {
		
		// 가로 탐색 
		for (int i = 0; i < N; i++) {
			// 정답이 아닌 경우 0을 리턴하고 함수 종료
			if (findLine(arr[i]) == 0) {
				return 0;
			}
		}
		
		// 세로 탐색 
		for (int i = 0; i < N; i++) {
			
			// 1열을 1차원 배열로 만들어서 검사
			int[] line = new int[N];
			for (int x = 0; x < N; x++) {
				line[x] = arr[x][i];
			}
			
			// 정답이 아닌 경우 0을 리턴하고 함수 종료
			if (findLine(line) == 0) {
				return 0;
			}
		}
		
		// 격자 탐색 
		for (int i = 0; i < arr.length; i += 3) {
			for (int j = 0; j < arr.length; j += 3) {
				
				int[] grid = getGrid(arr, i , j);
				
				// 정답이 아닌 경우 0을 리턴하고 함수 종료
				if (findLine(grid) == 0) {
					return 0;
				}
			}
		}
		
		// 모든 검사를 통과했으므로 정답 스도쿠이므로 1을 리턴
		return 1;
	}
	
	// 1차원 배열에서 탐색, 정답이면 1,정답이 아니면 0
	public static int findLine(int[] line) {
		
		boolean[] seen = new boolean[10]; // 1부터 9까지 사용 여부 확인 
		
		for(int num : line) {
			if (seen[num]) {
				return 0;
			}
			seen[num] = true;
		}
		
		return 1;
	}
	
	// 3 x 3 격자 배열을 1차원 배열로 추출
	public static int[] getGrid(int[][] arr, int i, int j) {
		
		int[] line = new int[N];
		int index = 0;
		
		for (int x = 0; x < n; x++) {
			for (int y = 0; y < n; y++) {
				line[index++] = arr[i + x][j + y];
			}
		}
		return line;
	}
}

point

1. 숫자 중복을 빠르게 확인할 수 있도록 개선

   boolean 타입의 배열 seen을 크기 10으로 선언한다. 이때 배열의 인덱스 1부터 9까지의 부분을 사용한다.

   (seen[1] == true : 1 있음, seen[1] == false : 1 없음)

   인수로 받은 1차원 배열을 순회하면서 해당 값의 중복여부를 확인한다. 확인한 값이 true인 경우 중복된 경우이므로 바로 0을 리턴하고 함수를 종료한다.

2. 가독성 향상 - 격자 추출하는 부분을 메서드 분리했다.