[SW Expert Academy] - (D2)1974. 스도쿠 검증

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Psz16AYEDFAUq&categoryId=AV5Psz16AYEDFAUq&categoryType=CODE

SW Expert Academy

 

코드

import java.util.Scanner;

public class Solution {

	static int map[][];
	static boolean flag[];

	/* 행(가로) 체크 */
	public static boolean checkRow(int i) {
		flag = new boolean[9];

		for(int j=0; j<9; j++) {
			if(flag[map[i][j]-1]) {	// 현재 값에 해당하는 flag[]배열이 true인경우 -> 중복된 경우.
				return false;
			}
			flag[map[i][j]-1] = true; // 해당 값이 처음 체크되는 경우(false) -> true로 설정
		}
		return true;
	}

	/* 열(세로) 체크 */
	public static boolean checkCol(int i) {
		flag = new boolean[9];

		for(int j=0; j<9; j++) {
			if(flag[map[j][i]-1]) {	// 현재 값에 해당하는 flag[]배열이 true인경우 -> 중복된 경우.
				return false;
			}
			flag[map[j][i]-1] = true; // 해당 값이 처음 체크되는 경우(false) -> true로 설정
		}
		return true;
	}

	/* 3x3 격자 체크 */
	public static boolean checkGrid(int x, int y) {
		flag = new boolean[9];
		int nx = x + 3;
		int ny = y + 3;

		for(int i=x; i<nx; i++) {
			for(int j=y; j<ny; j++) {
				if(flag[map[i][j]-1]) {
					return false;
				}
				flag[map[i][j]-1] = true;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		int T = scan.nextInt();

		for(int tc=1; tc<=T; tc++) {
			map = new int[9][9];
			boolean flag = true;

			for(int i=0; i<9; i++) {
				for(int j=0; j<9; j++) {
					map[i][j] = scan.nextInt();
				}
			}

			/* 행 체크 */
			for(int i=0; i<9; i++) {
				if(!checkRow(i)) {
					System.out.println("#" + tc + " " + 0);
					flag = false;
					break;
				}
			}

			if(!flag) continue;

			/* 열 체크 */
			for(int i=0; i<9; i++) {
				if(!checkCol(i)) {
					System.out.println("#" + tc + " " + 0);
					flag = false;
					break;
				}
			}

			if(!flag) continue;

			/* 3x3 격자 체크 */
			Outter: for(int i=0; i<=6; i+=3) {
				for(int j=0; j<=6; j+=3) {
					if(!checkGrid(i, j)) {
						System.out.println("#" + tc + " " + 0);
						flag = false;
						break Outter;
					}
				}
			}
			
			// 위 과정에서 flag가 false인 경우 -> 중복된 경우이므로 continue, 아닐경우 1 출력
			if(!flag) continue;
			System.out.println("#" + tc + " " + 1);
		}

		scan.close();
	}
}

 

풀이

문제에서 확인해야 할 곳은 3가지이다.

 

위와 같이 9X9 격자판에서 가로와 세로, 3X3의 그리드 격자를 따져봐야 한다.

 

각각 판단할때 boolean flag[] 라는 1차원 배열을 활용해서 체크를 했다.

 

1  2  3  4  5  6  7  8  9

 

가로가 위와같이 있을때, 각 값에 -1(배열은 0부터 시작하므로)에 해당하는 flag[] 배열의 요소가 true인 경우와 false인 경우로 나눠서 풀었다.

 

기본값은 false이므로, 초기에는 false이고 9개씩 숫자를 반복하면서 해당 요소를 인덱스로 하는 flag 배열의 값을 true로 설정하고, 만약 해당 값이 이미 true인 경우는 중복된 수이므로 0을 출력해준다.

 

 

위 가로, 세로를 체크하는 코드는 다음과 같다.

	/* 행(가로) 체크 */
	public static boolean checkRow(int i) {
		flag = new boolean[9];

		for(int j=0; j<9; j++) {
			if(flag[map[i][j]-1]) {	// 현재 값에 해당하는 flag[]배열이 true인경우 -> 중복된 경우.
				return false;
			}
			flag[map[i][j]-1] = true; // 해당 값이 처음 체크되는 경우(false) -> true로 설정
		}
		return true;
	}

	/* 열(세로) 체크 */
	public static boolean checkCol(int i) {
		flag = new boolean[9];

		for(int j=0; j<9; j++) {
			if(flag[map[j][i]-1]) {	// 현재 값에 해당하는 flag[]배열이 true인경우 -> 중복된 경우.
				return false;
			}
			flag[map[j][i]-1] = true; // 해당 값이 처음 체크되는 경우(false) -> true로 설정
		}
		return true;
	}
    
    
                        // main 함수
    			/* 행 체크 */
			for(int i=0; i<9; i++) {
				if(!checkRow(i)) {
					System.out.println("#" + tc + " " + 0);
					flag = false;
					break;
				}
			}

			if(!flag) continue;

			/* 열 체크 */
			for(int i=0; i<9; i++) {
				if(!checkCol(i)) {
					System.out.println("#" + tc + " " + 0);
					flag = false;
					break;
				}
			}

			if(!flag) continue;

continue 부분은, 이미 중복된 수로 인해 flag값이 false로 변경된 경우 빠르게 다음으로 넘어가고자 추가했다.

 

 

생각을 좀 해야하는 부분은 3X3의 그리드 격자 부분이다.

먼저 코드부터 보면 다음과 같다.

	/* 3x3 격자 체크 */
	public static boolean checkGrid(int x, int y) {
		flag = new boolean[9];
		int nx = x + 3;
		int ny = y + 3;

		for(int i=x; i<nx; i++) {
			for(int j=y; j<ny; j++) {
				if(flag[map[i][j]-1]) {
					return false;
				}
				flag[map[i][j]-1] = true;
			}
		}
		return true;
	}
    
    
    			/* 3x3 격자 체크 */
			Outter: for(int i=0; i<=6; i+=3) {
				for(int j=0; j<=6; j+=3) {
					if(!checkGrid(i, j)) {
						System.out.println("#" + tc + " " + 0);
						flag = false;
						break Outter;
					}
				}
			}

3x3 그리드는 3개씩 반복되는데 좌표를 보면 다음과 같다.

 

(0,0) (0,1) (0,2)      (0,3) (0,4) (0,5) ...

(1,0) (1,1) (1,2)      (1,3) (1,4) (1,5) ...

 (2,0) (2,1) (2,2)      (2,3) (2,4) (2,5) ... 

 

3개씩 반복이 된다.

 

따라서 checkGrid 함수에 nx = x+3 , ny = y+3 으로 설정하고,

3개씩 반복할거기 때문에 for문에 초기값과 끝값을 설정해준다(i=x; i<nx; , j=y; j<ny)

main 함수에서도 값을 3씩 증가시켜주고 0, 3, 6 세 개만 반복하면 되므로 6까지 반복문을 돌려준다.

 

 

Outter: 이 부분은 Java의 Label 이다.

break Outter: 부분을 통해 위에까지 되돌아가는데,

라벨< 참고하면 된다.