글 읽기 - 어디서 틀렸는지 모르겠습니다

yooil405 1년 전 0

사전식으로 출력된 것 같은데 틀렸다고 뜹니다.!

잘못된 부분이나 반례 부탁드립니다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static int[][] board;

	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		board = new int[9][9];
		
		
		for(int i = 0; i < 9; i++) {
			
			String S = br.readLine();
			
			for(int j = 0; j < 9; j++) {
				
				board[i][j] = S.charAt(j) - 48;
			}
		}
		
		sudoku(0, 0);
	}

	private static void sudoku(int row, int col) {
		if(col == 9) {
			sudoku(row + 1, 0);
			
			return;
		}
		
		if(row == 9) {
			
			StringBuilder sb = new StringBuilder();
			
			for (int i = 0; i < 9; i++) {
				
				for (int j = 0; j < 9; j++) {
					
					sb.append(board[i][j]).append(' ');
				}
				
				sb.append('\n');
			}
			
			System.out.println(sb);
			
			System.exit(0);
		}
		
		if(board[row][col] == 0) {
			for(int i = 0; i < 9; i++) {
				
				if(isPossible(row, col, i + 1)) {
					board[row][col] = i + 1;
					
					// flag1
					sudoku(row, col + 1); 
				}
			}
			
			// 백트래킹! 특정값을 넣고 재귀함수를 진행했는데 깊은 곳에서 막혔을 시 다시 내려보낸다. flag1으로 돌아가서 다른 숫자를 대입해서 연산을 진행하게 된다.
			board[row][col] = 0;
			return;
		}
		
		sudoku(row, col + 1);
	}

	private static boolean isPossible(int row, int col, int value) {
		// 행, 열 검사
		for(int i = 0; i < 9; i++) {
			
			if(board[row][i] ==  value) {
				
				return false;
			}
			
			if(board[i][col] ==  value) {
				
				return false;
			}
		}
		
		int r = row / 3 * 3;
		int c = col / 3 * 3;
		
		for(int i = r; i < r + 3; i++) {
			
			for(int j = c; j < c + 3; j++) {
				
				if(board[i][j] ==  value) {
					
					return false;
				}
			}
		}
		
		return true;
	}
}

semi0777 1년 전 1

58번째 줄에서 isPossible이 실패했을경우엔 현재연산중인 위치에 0넣고 리턴시키기는 것만 하셨는데 그렇게 돼면 처음부터 잘못됀 숫자가 들어가서 스도쿠가 성립하지 못하는 경우엔 답을 도출하지 못하고 return돼지 않을까요?

yooil405 1년 전 0

답이 되지 않는 경우에 대한 조건이 없어서 스도쿠가 성립하지 않는 경우를 배재해서 저렇게 작성했습니다.!

리턴시에는 다음 인덱스의 포문을 돈다고 생각했습니다.

제가 어느 부분을 놓치는 지를 몰라서 저 부분이 어떻게 잘 못된 건지 모르겠네요. 알려주시면 감사합니다

semi0777 1년 전 0

스도쿠를 풀때는 보통 가지고있는 경우의 수가 가장적은것부터 기입합니다 하지만 지금 방식으로 기입하면 경우의 수가 가장적은 칸에서 받을 수 있는 경우의 수가 없어질 수 있어요

yooil405 1년 전 0

넵 그럼 적은 경우의 수부터 해결하는 식으로 구현해보겠습니다

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

문제

문제

출처

ICPC

어디서 틀렸는지 모르겠습니다

yooil405 1년 전 0

semi0777 1년 전 1

yooil405 1년 전 0

semi0777 1년 전 0

yooil405 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말