안녕하세요
인포돈 입니다.
백준 알고리즘 2580번 풀이입니다.
* 참고사항
- 개발환경은 eclipse을 기준으로 작성되었습니다.
- java언어를 이용하여 문제를 풀이합니다.
- 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
- 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.
백준 2580 (스도쿠)
문제
스도쿠는 18세기 스위스 수학자가 만든 '라틴사각형''라틴사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈칸을 채우는 방식은 다음과 같다.
각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈칸에는 3이 3 들어가야 한다.
이와 같이 빈칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
나머지 빈칸을 채우는 방식은 다음과 같다.
각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈칸에는 3이 3 들어가야 한다.
이와 같이 빈칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
나머지 빈칸을 채우는 방식은 다음과 같다.
각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈칸에는 3이 3 들어가야 한다.
이와 같이 빈칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그중 하나만을 출력한다.
입력 예시
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0출력 예시
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1성공 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int[][] arr = new int[9][9];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i = 0 ; i < 9 ; i++) {
StringTokenizer str = new StringTokenizer(br.readLine());
for(int j = 0 ; str.hasMoreTokens();j++) {
arr[i][j]= Integer.parseInt(str.nextToken());
}
}
dfs(0,0);
}
public static void dfs(int row, int col) {
if(col == 9) {
dfs(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(arr[i][j]).append(' ');
}
sb.append('\n');
}
System.out.println(sb);
System.exit(0);
}
if(arr[row][col]==0) {
for(int i = 1 ; i <= 9 ; i++) {
if(check(row, col, i)) {
arr[row][col] = i;
dfs(row, col+1);
}
}
arr[row][col]=0;
return;
}
dfs(row, col+1);
}
public static boolean check(int row, int col, int value) {
//같은열에 무슨 숫자가 비었는지
for(int i = 0 ; i < 9 ; i ++) {
if(arr[row][i] == value) {
return false;
}
}
//같은행에 무슨 숫자가 비었는지
for(int i = 0 ; i < 9 ; i ++) {
if(arr[i][col] == value) {
return false;
}
}
//같은 네모에 뭐가 있는지
int ind_row = (row/3)*3;
int ind_col = (col/3)*3;
for(int i = ind_row ; i < ind_row+3 ; i ++) {
for(int j = ind_col ; j < ind_col +3 ; j++) {
if(arr[i][j] == value)
return false;
}
}
return true;
}
}스도쿠 알고리즘에서의 핵심은 바로 빈칸에 무슨 값이 들어가야 하는지 체크하는 기능입니다. 저 같은 경우 해당 알고리즘은 이전에 풀어보았던 N-Queen알고리즘이랑 많이 비슷하다고 생각했었습니다. 뭐 간단한 형식이야 비슷하긴 하더라고요.
( 기본적인 입력받기는 성공코드를 참고하시면 됩니다! 꼭 BUFFEREDREADER 말고도 SCANNER를 통해서 하셔도 되고요 입력받는 방법은 여러 가지랍니다 ~)
해당 알고리즘을 STEP을 따라 간략히 이해해보도록 하죠
알고리즘 흐름도
입력받기 -> DFS 실행하기 -> 빈칸 찾기 -> 찾은 빈칸에 어떤 값이 들어가야 하는지 찾기 -> 찾은 값 대입하고 다음 빈칸 찾기 -> 완성된 배열 출력
STEP1 DFS인자 설정하기
가장 먼저 저희는 DFS의 인자를 찾아봐야 합니다. 항상 고민이 되지만, 이번에 인자는 굉장히 쉽게 생각해볼 수 있었어요. 그냥 행과 열을 주면 되지 않을까?
이렇게 생각한 이유는 행과 열을 계속 재귀하면서 바꿔줘 가면서 값을 찾으면 쉽게 코드 할 수 있다고 생각했기 때문이죠.. (물론 코딩을 하다 잘못된 부분이 있다면, 추가하거나 삭제할 수도 있겠죠)
public static void dfs(int row, int col) {
}STEP2 DFS FOR문 (빈칸 찾기)
그러면 우선 가장 먼저 빈칸을 찾으러 가봐야겠죠. 저희가 원하는 결과는 빈칸에 알맞은 값을 넣어주는 거니깐요. 입력에서 보다시피 빈칸의 값은 0으로 되어있습니다.
public static void dfs(int row, int col) {
if(arr[row][col]==0) {
}
}이렇게 열과 행에 있는 값이 0이라면 조건문을 설정하여 빈칸을 쉽게 찾을 수 있겠죠. 그렇다면 이제 어떤 값을 넣어야 할지 생각해야 합니다. 그러기 위해서는 새로운 CHECK라는 함수를 한번 만들어보도록 하죠.
그전에 값은 1 ~ 9의 값을 찾기 때문에 반복문을 하나 설정해 줍니다.
public static void dfs(int row, int col) {
if(arr[row][col]==0) {
for(int i = 1 ; i <= 9 ; i++) {
if(check(row, col, i)) {
}
}
}
}간단하죠?
STEP 3 DFS FOR문 (빈칸에 넣을 값 찾기)
그러면 이제 열과 행 그리고 넣어줄 값 i를 가지고 값이 맞는지 확인을 해야 합니다.
고려해야 될 사항은 3가지
- 같은 행에 값이 있는가
- 같은 열에 값이 있는가
- 네모 박스에 값이 있는가
public static boolean check(int row, int col, int value) {
//같은열에 무슨 숫자가 비었는지
for(int i = 0 ; i < 9 ; i ++) {
if(arr[row][i] == value) {
return false;
}
}
//같은행에 무슨 숫자가 비었는지
for(int i = 0 ; i < 9 ; i ++) {
if(arr[i][col] == value) {
return false;
}
}
//같은 네모에 뭐가 있는지
int ind_row = (row/3)*3;
int ind_col = (col/3)*3;
for(int i = ind_row ; i < ind_row+3 ; i ++) {
for(int j = ind_col ; j < ind_col +3 ; j++) {
if(arr[i][j] == value)
return false;
}
}
return true;
}행과 열을 찾는 것은 비교적으로 간단하죠. 행이면 행 열이면 열을 쭉 반복해보면서 해당 값이 있으면 false 즉, 인자로 들어온 i (value) 값은 들어가면 안 된다고 알려주는 것이죠
여기서 고비인 것은 바로 같은 네모에 뭐가 있는지!!
이를 위해서는 간단한 수학 지식이 필요합니다. row, col의 값에 따라서 찾아야 하는 범위가 바뀌기 때문이죠. 이는 인자로 들어온 row/3으로 나눕니다.
0/3=0
1/3=0
2/3=0
3/3=1
4/3=1
5/3=1
6/3=2
7/3=2
8/3=2
이런 식으로 값이 나오게 되죠. 여기서 저희가 찾기 시작해야 하는 범위는 3만 곱해주면 끝! 즉 0 1 2 번행이 들어왔다면 0번부터 찾을 수 있게 되는 거죠. 이와 같이 열도 설정한 다음 2중 for문을 통해 값을 비교해 확인해 주면 끝!
STEP 4 DFS FOR문 완성
public static void dfs(int row, int col) {
if(arr[row][col]==0) {
for(int i = 1 ; i <= 9 ; i++) {
if(check(row, col, i)) {
arr[row][col] = i;
dfs(row, col+1);
}
}
arr[row][col]=0;
return;
}
}만약에 이전에 만들었던 CHECK에 TRUE가 들어온다면, 그 값을 넣어도 된다는 뜻! 해당 값을 넣어준 뒤 열을 하나 올려주어 또 다른 빈칸을 찾으러 재귀를 돌려주는 것이죠. 그런데 만약에 해당 값에 맞는 값이 없다.... 이것은 바로 스도쿠 문제가 잘못되었다는 것을 의미합니다!! 그러면 바로 DFS를 종료시켜주는 거죠.
STEP 5 DFS IF문
public static void dfs(int row, int col) {
if(col == 9) {
dfs(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(arr[i][j]).append(' ');
}
sb.append('\n');
}
System.out.println(sb);
System.exit(0);
}
if(arr[row][col]==0) {
for(int i = 1 ; i <= 9 ; i++) {
if(check(row, col, i)) {
arr[row][col] = i;
dfs(row, col+1);
}
}
arr[row][col]=0;
return;
}
dfs(row, col+1); //빈칸이 아닌경우
}IF문은 항상 언제나 그렇듯이 간단합니다. 저희가 찾는 방향은 가로 먼저 찾고 세로를 찾는 방식! 그렇기에 만약 열이 9가 된다는 것은 끝까지 찾았으니 다음 행으로 이동하여 찾기를 도와줍니다.!! (참소로 저희 열은 0 ~ 8입니다.)
만약 ROW가 끝이라면 이제 모든 스도쿠를 채웠다는 의미니 저희가 원하는 출력은 STRINGBUILDER에 저장해 줍니다. (단순 반복문) 그리고 출력 후 프로그램을 종료하면 끝!
여기서 마지막에 한 줄을 추가해 주어야 합니다. 만약에 빈칸이 아닌 경우에는 DFS를 통해 열을 한 칸 이동해 주어야 합니다. (즉, 빈칸이 아닌 경우를 고려해 주어야 하죠)
이렇면 저희가 원했던 DFS구현이 끝났습니다.
해당 문제는 N-Queen문제와 조금 유사한 문제로 생각됩니다. 이러한 문제를 풀이할 때는 항상 무엇을 체크해야 하는지 정리하고 체크해야 하는 부분을 작성해주시면 보다 쉽게 풀이하는 방식으로 접근할 수 있습니다.!
'알고리즘 > 백준알고리즘' 카테고리의 다른 글
| [백준][JAVA알고리즘]9184번 풀이(신나는 함수 실행) - 초보도 이해하는 풀이 (0) | 2021.08.03 |
|---|---|
| [백준][JAVA알고리즘]1003번 풀이(피보나치 함수) - 초보도 이해하는 풀이 (0) | 2021.07.23 |
| [백준][JAVA알고리즘]14889번 풀이(스타트와 링크) - 초보도 이해하는 풀이 (0) | 2021.07.21 |
| [백준][JAVA알고리즘]14888번 풀이(연산자 끼워넣기) - 초보도 이해하는 풀이 (0) | 2021.07.20 |
| [백준][JAVA알고리즘]9663번 풀이(N-Queen) - 초보도 이해하는 풀이 (0) | 2021.07.19 |
