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

 

2580번: 스도쿠

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루

www.acmicpc.net

코드설명

백트래킹과 DFS를 활용하는 문제입니다.

 

시간초과가 나지않게 효율적으로 코딩해야합니다. 

특히 저는 For 0부터 9까지 모든 구간을 돌며 0 을 만날시 simulate를 진행하였는데

그렇게하지않고, 갱신한 곳의 위치를 nowX, nowY로 계속가져가면서 업데이트 시켜줘야합니다.

만약 nowY >= 9 라면 열을 벗어난 것이므로 다음행으로 이동시키기 위해 nowX += 1, nowY = 0 으로 갱신시킵니다.

이떄, 당연히 nowX가 만약에 마지막 행인 nowX == 8 이고 nowY == 9 라면 더이상 이동할 수 없으니 return 시켜야합니다.

 

 

문제의 기본적인 로직입니다.

  1. 먼저 map을 돌면서 0 인 구간을 만나면 simulate를 시작합니다.
    1. 1. 가로줄과 세로줄을 확인하며 비어있는 숫자를 찾아냅니다,
    2. 3x3 정사각형 안의 1부터 9까지의 숫자가 한번씩만 나타나는지도 확인합니다.
  2. 이떄 비어있는 숫자를 찾았을경우, 
    1. 해당 숫자를 먼저 넣고, simulate()를 다시 돌립니다.
    2. 이제 가다가 다른 빈칸을 하나 더 만납니다. 그러면 다시 simulate()를 돌리면서 계속해서 찾아나갑니다.

 

 

처음에 맵의 9x9 를 모두 확인해가며 진행하여 시간초과가 났습니다.

0 0 0 0 0 0 0 0 9
0 0 0 0 0 0 0 0 8
0 0 0 0 0 0 0 0 7
0 0 0 0 0 0 0 0 6
0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 4
0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 1

위와 같은 예시를 돌려보면, 너무 많은 경우가 있기에 DFS가 시간초과가 납니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int N, M;
	public static int answer = 0;
	public static int[][] map;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		map = new int[9][9];
		for(int i=0;i<9;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<9;j++) {
				map[i][j] = st.nextToken().charAt(0) - '0';
			}
		}
		
		simulate(0, 0, 0);
	}
	
	public static void simulate(int level, int r, int c) {
		if( c >= 9 ) {
			r = r + 1;
			c = 0;
		}
		if(level >= 9*9) {
			//찾은경우입니다.
			for(int i=0;i<9;i++) {
				for(int j=0;j<9;j++) {
					System.out.print(map[i][j]+" ");
				}
				System.out.println();
			}
			System.exit(0);
			return ;
		}
		
		if( r >= 9) {
			
			return ;
		}
		
		//만약 0 이라면, 
		if(map[r][c] == 0) {
			for(int num = 1; num <= 9; num++) {
				//행, 열, 3x3 에 해당 숫자가 존재하지 않을경우에만 넣어야할 것 입니다.
				if ( checkSudoku(num, r, c) == true ) {
					map[r][c] = num;
					simulate(level + 1, r, c + 1);
				}
			}
			map[r][c] = 0;
		}
		
		//만약 0 이 아닐경우에만 담은칸으로 그냥 넘어가도록 해야합니다.
		else if(map[r][c] != 0) {
			//아무것도 하지 않고 넘어가는 경우입니다.
			simulate(level + 1, r, c + 1);	
		}
		
	}
	
	public static boolean checkSudoku(int num, int r, int c) {
		
		for(int col = 0; col < 9; col++) {
			if(map[r][col] == num) {
				return false;
			}
		}
		
		for(int row = 0; row < 9; row++) {
			if(map[row][c] == num) {
				return false;
			}
		}
		
		//시작칸의 3x3 을 구하기 위해.
		int newR = r / 3;
		int newC = c / 3;
		for(int i=newR * 3; i < newR * 3  + 3; i++) {
			for(int j=newC * 3; j < newC * 3 + 3; j++) {
				if(map[i][j] == num) {
					return false;
				}
			}
		}
		
		return true;
	}
	
}

 

시간초과나지않은 코드(nowX, nowY 로 현재 위치를 갱신합니다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N;
	public static int answer = 0;
	public static int[][] map;
	public static int cnt = 0;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    	map = new int[9][9];
    	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) cnt ++;
    		}
    	}
    	simulate(0,0,0);
    }
    //먼저 map을 돌면서 0 인 구간을 만나면 simulate를 시작합니다.
    //이때 먼저. 
    		//1. 가로줄과 세로줄을 확인하며 비어있는 숫자를 찾아냅니다,
    		//2. 3x3 정사각형 안의 1부터 9까지의 숫자가 한번씩만 나타나는지도 확인합니다.
    //이떄 비어있는 숫자를 찾았을경우, 
    	//해당 숫자를 먼저 넣고, simulate()를 다시 돌립니다.
    	//이제 가다가 다른 빈칸을 하나 더 만납니다.
    public static void simulate(int nowX, int nowY, int level) {
 
    	if( cnt == level && answer== 0) {
    		answer = 1;
    		for(int i=0;i<9;i++) {
    			for(int j=0;j<9;j++) {
    				System.out.print(map[i][j]+" ");
    			}
    			System.out.println();
    		}
    		
    		return ;
    	}
    	if(nowX < 8 && nowY == 9) { // map[0][9] 일경우 -> map[1][0] 으로 이동시킵니다.
    		nowX += 1;
    		nowY = 0;
    	}
    	
    	if(nowX == 8 && nowY == 9) return ; //(map[8][9] 일경우 중단처리합니다.)
    	
    	if(map[nowX][nowY] == 0) {
    		
    		for(int num = 1; num <= 9; num++) {
				boolean flag = false;
				//가로 확인
				for(int col=0;col<9;col++) {
					if(num == map[nowX][col]) { //같은경우 안됨. 
						flag = true;
						break;
					}
				}
				if(flag == true) continue;
				
				//세로확인
				for(int row=0;row<9;row++) {
					if(num == map[row][nowY]) { //같은경우 안됨.
						flag = true;
						break;
					}
				}
				
				int compare3by3Row = (nowX / 3) * 3;
				int compare3by3Col = (nowY / 3) * 3;
				
				for(int row=compare3by3Row;row<compare3by3Row+3;row++) {
					for(int col=compare3by3Col;col<compare3by3Col+3;col++) {
						if(map[row][col] == num) {
							flag = true;
							break;
						}
					}
				}
				
				if(flag == false) {
					map[nowX][nowY] = num;
					simulate(nowX, nowY + 1, level + 1);
					map[nowX][nowY] = 0;
				}
    		}
    		
    	}else {
    		simulate(nowX, nowY + 1, level);
    	}
    	
    }
 
}

 

처음에 시간초과가 난 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N;
	public static int answer = 0;
	public static int[][] map;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    	map = new int[9][9];
    	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());
    		}
    	}
    	
    	simulate(0,0);
    }
    
    public static void simulate(int startx, int starty) {
    	if(answer == 1) return ;
 
    	boolean endFlag = true;
    	for(int i=0;i<9;i++) {
    		for(int j=0;j<9;j++) {
    			if(map[i][j] == 0) {
    				endFlag = false;
    				break;
    			}
    		}
    	}
    	if(endFlag == true) {
        	for(int i=0;i<9;i++) {
        		for(int j=0;j<9;j++) {
        			System.out.print(map[i][j] +" ");
        		}
        		System.out.println();
        	}
        	answer = 1;
    		return ;
    	}
    	for(int i=0;i<9;i++) {
    		for(int j=0;j<9;j++) {
    			if(map[i][j] == 0) {
    				for(int num = 1; num <= 9; num++) {
    					boolean flag = false;
        				//가로 확인
        				for(int col=0;col<9;col++) {
        					if(num == map[i][col]) { //같은경우 안됨. 
        						flag = true;
        						break;
        					}
        				}
        				
        				//세로확인
        				for(int row=0;row<9;row++) {
        					if(num == map[row][j]) { //같은경우 안됨.
        						flag = true;
        						break;
        					}
        				}
        				
        				if( i / 3 == 0 && j / 3 == 0) { // 정사각형 확인 (첫번쨰 정사각형)
        					for(int row = 0; row < 3;row++) {
        						for(int col = 0; col < 3; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				else if( i / 3 == 0 && j / 3 == 1) { // 정사각형 확인 (두번쨰 정사각형)
        					for(int row = 0; row < 3;row++) {
        						for(int col = 3; col < 6; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				else if( i / 3 == 0 && j / 3 == 2) { // 정사각형 확인 (두번쨰 정사각형)
        					for(int row = 0; row < 3;row++) {
        						for(int col = 6; col < 9; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				
        				else if( i / 3 == 1 && j / 3 == 0) { // 정사각형 확인 (네번쨰 정사각형)
        					for(int row = 3; row < 6;row++) {
        						for(int col = 0; col < 3; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				else if( i / 3 == 1 && j / 3 == 1) { // 정사각형 확인 (다섯번쨰 정사각형)
        					for(int row = 3; row < 6;row++) {
        						for(int col = 3; col < 6; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				else if( i / 3 == 1 && j / 3 == 2) { // 정사각형 확인 (여섯번쨰 정사각형)
        					for(int row = 3; row < 6;row++) {
        						for(int col = 6; col < 9; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				
        				else if( i / 3 == 2 && j / 3 == 0) { // 정사각형 확인 (일곱번쨰 정사각형)
        					for(int row = 6; row < 9;row++) {
        						for(int col = 0; col < 3; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				else if( i / 3 == 2 && j / 3 == 1) { // 정사각형 확인 (여덟쨰 정사각형)
        					for(int row = 6; row < 9;row++) {
        						for(int col = 3; col < 6; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				else if( i / 3 == 2 && j / 3 == 2) { // 정사각형 확인 (아홉번쨰 정사각형)
        					for(int row = 6; row < 9;row++) {
        						for(int col = 6; col < 9; col++) {
        							if(num == map[row][col]) {
        								flag = true;
        								break;
        							}
        						}
        					}
        				}
        				
        				if(flag == false) { //통과한경우.
        					map[i][j] = num;
        					simulate(i, j);
        					map[i][j] = 0;
        				}
    				}
    			}
    			
    		}
    	}
    	
    }
 
}

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 2661 좋은수열 - 백트래킹(Backtracking) + 문자열(String) + 아이디어(Idea) JAVA  (0) 2023.08.22
[백준] 1062 가르침 - 백트래킹(BackTracking) + 조합(Combination) JAVA  (0) 2023.08.22
[백준] 16987 계란으로 계란치기 - 백트래킹 + DFS JAVA  (0) 2023.08.21
[백준] 10971 외판원 순회 2 - 백트래킹 + DFS + 외판원 순회 문제(Traveling Salesman Problem (TSP) )JAVA  (0) 2023.08.20
[백준] 15486 퇴사 2 - DP JAVA  (0) 2023.08.20

+ Recent posts

티스토리툴바