Sho1007

MMORPG 클라이언트 개발자 지망생

2 minute read

2580 스도쿠 (c++)

문제

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

접근 방식

백 트래킹

  1. 0이 적힌 칸이 없을 때 까지 다음을 반복
    1. 0이 적힌 칸에 1 ~ 9 중 숫자 하나를 집어 넣는다
    2. 0이 적힌 칸이 없으면 맞게 적어넣었는지 체크한다.
    3. 틀렸으면 한칸 전 0으로 돌아가서 다음 수를 넣어본다.

문제 풀이

#include <iostream>
#define endl '\n'
using namespace std;

int board[9][9], zeroRow[81], zeroCol[81], zeroCnt;
bool Used[3][9][10] = {};

bool Solve(int n);
void Print();

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for (int i = 0; i < 9; ++i)
    {
        for (int j = 0; j < 9; ++j)
        {
            cin >> board[i][j];
            if (!board[i][j])
            {
                zeroRow[zeroCnt] = i;
                zeroCol[zeroCnt++] = j;
            }
            Used[0][i][board[i][j]] = Used[1][j][board[i][j]] = Used[2][(i/3) * 3 + (j / 3)][board[i][j]] = true;
        }
    }
    Solve(0);
    return 0;
}

bool Solve(int n)
{
    if (n == zeroCnt)
    {
        Print();
        return true;
    }
    int r = zeroRow[n];
    int c = zeroCol[n];
    for (int i = 1; i < 10; ++i)
    {
        if (!(Used[0][r][i] + Used[1][c][i] + Used[2][(r/3) * 3 + (c / 3)][i]))
        {
            Used[0][r][i] = Used[1][c][i] = Used[2][(r / 3) * 3 + (c / 3)][i] = true;
            board[r][c] = i;
            if (Solve(n + 1)) return true;
            board[r][c] = 0;
            Used[0][r][i] = Used[1][c][i] = Used[2][(r / 3) * 3 + (c / 3)][i] = false;
        }   
    }
    return false;
}
void Print()
{
    for (int i = 0; i < 9; ++i)
    {
        for (int j = 0; j < 9; ++j) cout << board[i][j] << " ";
        cout << endl;
    }
}

다시 생각해 볼 점

  1. 처음엔 제한시간이 1초 (계산 1억회)이길래 조건 없이 0이 적힌 칸에 1 ~ 9 까지의 숫자를 하나씩 적어봤다. (시간 초과)
  2. 그 다음엔 아래의 배열에서 입력받은 숫자를 제외하고 나머지 숫자들 중 세 배열 모두 만족하는 수를 넣었다. (성공)
    • 가로 배열 [9][9] : (첫 번째 숫자)의 행에 (두 번째 숫자)의 숫자가 존재하는지
    • 세로 배열 [9][9] : (첫 번째 숫자)의 열에 (두 번째 숫자)의 숫자가 존재하는지
    • 작은 사각형 배열 [9][9] : (첫 번째 숫자)의 작은 사각형에 (두 번째 숫자)의 숫자가 존재하는지
  3. 이 때 배열을 만들고 인덱스 계산을 잘못해서 시간을 많이 잡아먹었다.
    • 작은 사각형 배열의 인덱스는 (i / 3) * 3 + (j / 3) 이다.
    • 나누기 와 곱하기가 연달아 오길래 소거해버렸다. (멍청)
    • 여기서 나누기의 의미는 나머지가 0~2까지의 수를 같은 수로 따지겠다는 의미이다. (0~2 = 0, 3~5 = 1, 6~8 = 2)
  4. 그리고 위의 알고리즘으로 풀면 결국 0의 갯수가 0이 되는 순간 문제가 해결된 것이나 다름이 없어서 Check를 할 필요가 없었다.
  5. 또한 중간의 
     if (Solve(n+1)) return true;

    이 구절이 없으면 가능한 정답을 모두 출력하기 때문에 출력이 완료되면 빠져나오는 위의 구문이 중요했다.

    • 마찬가지로 exit(0) 보다 return true 가 시간상으로도 효율적이었다. (exti(0)는 프로세스 강제 종료)
  6. 최적화된 다른 분의 코드를 참조했는데 여기서 새로운 사실을 깨달았다.
    • Used라는 상기한 3가지 배열을 가지는 배열이 있는데 이를 수정할 때 = 으로 엮어서 한줄로 수정하는 것이 더 빠르다.
    • 처음엔 0이 적힌 칸의 위치를 stack<pair<int, int»로 처리했었는데, 이러면 stack에 push, pop하는 시간이 걸린다.
    • 이를 zeroRow[81], zeroCol[81] (0이 최대 81개이기 때문)으로 처리하면 배열 인덱스 n만 조절해주면 백트래킹해가며 0의 위치에 접근할 수 있다.

참조

https://www.acmicpc.net/source/38709329

You may also enjoy