백준 2580번: 스도쿠

문제

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

2580번: 스도쿠

 

---

풀이

스도쿠 규칙에 맞춰 9 x 9 크기의 보드를 채우는 문제입니다.

dfs를 이용하여 모든 칸에 대해 어떤 숫자가 해당 칸에 들어갈 수 있는지에 대한 여부를 sudoku 함수를 통해 확인받아가며 2차원 정수 배열에 기록하는 방식을 사용했습니다.

---

코드

C언어

2차원 정수 배열 arr로 9 x 9 크기의 보드를 표현합니다. dfs 함수에서 보드의 (x, y)의 위치에 있는 숫자를 arr[y][x]라고 할 때 dpth는 y를, idx는 x를 의미합니다. 메인 함수에서 모든 입력을 받은 후에 xy 좌표 (0,0)부터 시작한다는 의미로 dfs(0, 0)을 실행합니다.

먼저 arr[dpth][idx]가 0이라면(비어있는 칸이라면) 1부터 9까지 숫자중에서 넣을 수 있는 숫자를 sudoku 함수를 통해 확인한 뒤에 dfs 함수를 재귀적으로 실행합니다. 이때 sudoku 함수는 dpth, idx 그리고 가능한지 확인하고자 하는 숫자인 value를 매개변수로 입력받고 상하좌우에 같은 값이 있는지 위쪽의 for문을 통해 확인합니다. 또한 3 x 3 크기의 작은 정사각형 안에 같은 값이 있는지 아래 for문을 통해 확인합니다. 이때 row는 작은 정사각형의 가장 위쪽, col은 가장 왼쪽을 표현합니다. 모든 조건을 만족하면 1(True)을, 그렇지 않으면 0(False)을 반환합니다.

만약 함수가 실행되고 있던 와중에 막혀서 다시 돌아가야 하는 경우가 있을 수 있으므로 기록했던 것들을 아래에서 지워줍니다. 다시 돌아가기 전에 비어있는 칸을 건너뛰고 다음 dfs 함수를 실행하는 것을 막기 위해 if문 안에서 return합니다.

idx가 9가 됐다면 해당 y 좌표의 모든 x값을 확인한 것이므로 dfs(dpth + 1, 0)을 통해 다음 y 좌표의 처음, 즉 (0, y + 1)부터 다시 시작합니다. dpth가 9가 됐다면 모든 칸을 다 채웠다는 것이므로 arr의 모든 값을 문제 조건에 맞게 출력한 뒤에 exit(0)을 통해 프로그램을 종료합니다.

#include <stdio.h>
#include <stdlib.h>
int arr[9][9];
int sudoku(int dpth, int idx, int value) {
	for (int i = 0; i < 9; i++) {
		if (arr[dpth][i] == value) {
			return 0;
		}
		if (arr[i][idx] == value) {
			return 0;
		}
	}
	int row = (dpth / 3) * 3;
	int col = (idx / 3) * 3;
	for (int i = row; i < row + 3; i++) {
		for (int j = col; j < col + 3; j++) {
			if (arr[i][j] == value) {
				return 0;
			}
		}
	}
	return 1;
}
void dfs(int dpth, int idx) {
	if (idx == 9) {
		dfs(dpth + 1, 0);
		return;
	}
	if (dpth == 9) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				printf("%d ", arr[i][j]);
			}
			printf("\n");
		}
		exit(0);
	}
	if (arr[dpth][idx] == 0) {
		for (int i = 1; i <= 9; i++) {
			if (sudoku(dpth, idx, i)) {
				arr[dpth][idx] = i;
				dfs(dpth, idx + 1);
			}
		}
		arr[dpth][idx] = 0;
		return;
	}
	dfs(dpth, idx + 1);
}
main() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			scanf("%d", &arr[i][j]);
		}
	}
	dfs(0, 0);
}

자바

위의 C언어를 이용한 풀이와 동일한 방법으로 다른 점이라면 Stringbuilder를 이용하여 한꺼번에 출력한다는 것입니다.

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

public class Main {

    static int[][] arr;
    static StringBuilder sb;

    public static boolean sudoku(int dpth, int idx, int value) {
        for (int i = 0; i < 9; i++) {
            if (arr[dpth][i] == value) {
                return false;
            }
            if (arr[i][idx] == value) {
                return false;
            }
        }
        int row = (dpth / 3) * 3;
        int col = (idx / 3) * 3;
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                if (arr[i][j] == value) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void dfs(int dpth, int idx) {
        if (idx == 9) {
            dfs(dpth + 1, 0);
            return;
        }
        if (dpth == 9) {
            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.print(sb);
            System.exit(0);
        }
        if (arr[dpth][idx] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (sudoku(dpth, idx, i)) {
                    arr[dpth][idx] = i;
                    dfs(dpth, idx + 1);
                }
            }
            arr[dpth][idx] = 0;
            return;
        }
        dfs(dpth, idx + 1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        arr = new int[9][9];
        sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 9; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dfs(0, 0);
    }
}

 

---

결론

함수 안에서 다른 함수를 호출해가며 조건을 확인하는 방식이 처음에는 익숙하지도 않고 괜히 어렵다고 생각했었습니다. 하지만 이와 비슷한 문제들을 계속 풀어보니 프로그래밍적 사고방식도 기존보다 많이 좋아졌다는 것이 느껴졌습니다. 앞으로도 이러한 문제를 풀면서 프로그래밍적 사고방식을 더욱 업그레이드해나가고 싶습니다.