[백준][C++] 2239번: 스도쿠 <207>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

2239번: 스도쿠

생각의 흐름

음 왜인지는 모르겠으나... 생각보다 코드가 안짜지는 문제였다...

 

우선 배열의 크키가 9x9 사이즈라 백트래킹 혹은 brute force 방식으로 해결 가능할거라 생각되었다.

 

문제에서 input을 받을때 0인 지점들을 vector 에 담아 두었다.

따라서 vector 에 담겨 있는 점들을 차례로 돌면서 1 ~ 9 까지의 수를 한번씩 담아보게 되었다.

코드가 BFS와 비슷한 방식으로 작동한다.

void run(int num) {
    if (num == emptySize) { //  모든 빈칸을 숫자로 채운 경우
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << MAP[i][j];
            cout << '\n';
        } // 결과 출력
        exit(0);
    }
    
    for (int j = 1; j <= 9; j++) {
        MAP[points[num].first][points[num].second] = j; // 1~9 까지의 숫자를 넣어봄
        if (validPosition(points[num])) {
            run(num + 1);
        }
        MAP[points[num].first][points[num].second] = 0;// 최적해를 못찾았을 경우 값 비워주기
    }
}

 

각 칸에다 숫자를 대입해 본 후, validPosition 메서드를 호출하여 알맞은 장소인지를 확인한다.

이때!

알맞은 장소라면 -> 다음 빈곳에 숫자를 채우로 이동

알맞지 않은 장소라면 -> 더이상 진행하지 않는다 (백트래킹)

bool validPosition(pair<int, int> &p) {
    int squareX = p.first / 3; // 구역을 나눔
    int squareY = p.second / 3;

    for (int i = 0; i < 9; i++) {
        if (i != p.second && MAP[p.first][i] == MAP[p.first][p.second])
            return false; // 같은 행에 같은 숫자가 있으면 false 반환
        if (i != p.first && MAP[i][p.second] == MAP[p.first][p.second])
            return false; // 같은 열에 같은 숫자가 있으면 false 반환
    }
    for (int i = 3 * squareX; i < 3 * squareX + 3; i++) {
        for (int j = 3 * squareY; j < 3 * squareY + 3; j++) {
            if (MAP[i][j] == MAP[p.first][p.second] && (i != p.first && j != p.second)) {
                return false;
            }
        }
    }
    return true;
}

 

나의 코드

#include <bits/stdc++.h>
using namespace std;

int MAP[9][9];
int emptySize;
bool found = false;
vector<pair<int, int>> points;

bool validPosition(pair<int, int> &p) {
    int squareX = p.first / 3; // 구역을 나눔
    int squareY = p.second / 3;

    for (int i = 0; i < 9; i++) {
        if (i != p.second && MAP[p.first][i] == MAP[p.first][p.second])
            return false; // 같은 행에 같은 숫자가 있으면 false 반환
        if (i != p.first && MAP[i][p.second] == MAP[p.first][p.second])
            return false; // 같은 열에 같은 숫자가 있으면 false 반환
    }
    for (int i = 3 * squareX; i < 3 * squareX + 3; i++) {
        for (int j = 3 * squareY; j < 3 * squareY + 3; j++) {
            if (MAP[i][j] == MAP[p.first][p.second] && (i != p.first && j != p.second)) {
                return false;
            }
        }
    }
    return true;
}

void run(int num) {
    if (num == emptySize) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << MAP[i][j];
            cout << '\n';
        } // 결과 출력
        exit(0);
    }
    for (int j = 1; j <= 9; j++) {
        MAP[points[num].first][points[num].second] = j; // 1~9 까지의 숫자를 넣어봄
        if (validPosition(points[num])) {
            run(num + 1);
        }
        MAP[points[num].first][points[num].second] = 0;// 최적해를 못찾았을 경우 값 비워주기
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 9; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < 9; j++) {
            MAP[i][j] = str[j] - '0';
            if (MAP[i][j] == 0) {
                points.push_back({i, j});
                emptySize++;
            }
        }
    }

    run(0);

    return 0;
}