[백준] 스도쿠

스도쿠 (골 4) : https://www.acmicpc.net/problem/2580

2580번: 스도쿠

 

 

스도쿠는 내가 정말 좋아했던 게임이다. 에버랜드 알바하던 시절에 쉬는 시간 틈만 나면 폰으로 스도쿠 했을 만큼 좋아했다.

스도쿠를 하면서 가장 힘들었던 유형은, 노가다로 숫자를 하나씩 집어 넣어 중복되는게 없는지 일일이 다 확인해야 하는 경우가 많은 문제였다. 이 문제는 그 노가다 과정을, 고스란히 코드로 옮기는 문제이다.

 

접근 방법은 다음과 같다.

 

1. 빈 칸에 숫자 1을 넣어본다.

2. 가로, 세로, 사각형에 숫자가 중복되는지 확인한다.

3. 중복 유무 확인.

• 중복된다면 -> 빈칸에 숫자 2, 3, ... 을 넣어 보면서 1~2 과정 반복
• 중복되지 않는다면 -> 함수를 재귀 호출하여 또다른 빈 칸에 숫자 1 부터 넣어본다.

 

빈 칸의 좌표들을 담는 배열을 하나 만든 다음, 위의 과정을 재귀 함수로 탐색하면 된다.

아래 C++ 코드는 그 과정을 보여주는 코드이다.

 

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int map[9][9];
vector<pair<int, int>> zeroLoc;

// 열에 중복되는 숫자가 없는지 검사.
bool canRowPlace(int candNum, int colNum, int rowNum)
{
  for (int newCol = 0; 9 > newCol; newCol++)
  {
    if (colNum != newCol && candNum == map[newCol][rowNum])
      return false;
  }

  return true;
}

// 행에 중복되는 숫자가 없는지 검사.
bool canColPlace(int candNum, int colNum, int rowNum)
{
  for (int newRow = 0; 9 > newRow; newRow++)
  {
    if (rowNum != newRow && candNum == map[colNum][newRow])
      return false;
  }

  return true;
}

// 네모칸에 중복되는 숫자가 없는지 검사.
bool canSquarePlace(int cand_x, int cand_y)
{
  int colStart = (cand_x / 3) * 3;
  int rowStart = (cand_y / 3) * 3;

  for (int i = colStart; colStart + 3 > i; i++)
    for (int j = rowStart; rowStart + 3 > j; j++)
    {
      if (i == cand_x && j == cand_y)
        continue;

      if (map[i][j] == map[cand_x][cand_y])
        return false;
    }

  return true;
}

void printMap()
{
  for (int i = 0; 9 > i; i++)
  {
    for (int j = 0; 9 > j; j++)
      cout << map[i][j] << ' ';
    cout << '\n';
  }
}

void recursion(vector<pair<int, int>> zeroLoc)
{
  if (zeroLoc.empty())
  {
    printMap();
    exit(0);
  }

  int x = zeroLoc.back().first;
  int y = zeroLoc.back().second;

  zeroLoc.pop_back();

  // 현재 빈 자리에 숫자를 1부터 채워넣음
  for (int candNum = 1; 9 >= candNum; candNum++)
  {
    map[x][y] = candNum;

    // 가로, 세로, 네모간 중복되는 숫자가 없을 시,
    // 다음 빈자리를 바탕으로 재귀
    if (canRowPlace(candNum, x, y) && canColPlace(candNum, x, y) && canSquarePlace(x, y))
    {
      recursion(zeroLoc);
    }
    map[x][y] = 0;
  }
}

int main(void)
{
  for (int i = 0; 9 > i; i++)
    for (int j = 0; 9 > j; j++)
    {
      scanf("%d", &map[i][j]);
      if (map[i][j] == 0)
        zeroLoc.push_back({i, j});
    }

  recursion(zeroLoc);

  return 0;
}

 

하지만 이렇게 코드를 제출했을 때, 시간 초과가 나왔다. 중복되는 숫자가 있는지 없는지 확인하는 코드에서, 각각 9번씩 총 27번을 매번 계산해야 하므로 시간 초과가 나온 듯 하다.

다행히도 행이나 열, 네모칸에 중복되는 숫자가 있는지 검사하는 작업은 1번의 계산으로 구할 수 있다. 캐싱을 하는 방법으로, 해당 열[숫자] == true 형식으로 중복 유무를 검사할 시, for문을 돌며 9번 확인하지 않아도 1번의 계산으로 중복 유무를 구할 수 있다. 아래 코드는 이를 반영한 코드이다. 이 코드는 성공적으로 통과하였다.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>

using namespace std;

int map[9][9];
// 각각 colStatus[행번호][숫자] = {true or false} 방식으로 캐싱할 수 있다.
bool colStatus[9][10] = {false}, rowStatus[9][10] = {false}, squareStatus[3][3][10] = {false};

vector<pair<int, int>> zeroLoc;

bool canRowPlace(int candNum, int rowNum)
{
  if (rowStatus[rowNum][candNum])
    return false;

  return true;
}

bool canColPlace(int candNum, int colNum)
{
  if (colStatus[colNum][candNum])
    return false;
  return true;
}

bool canSquarePlace(int candNum, int x, int y)
{
  int col = x / 3;
  int row = y / 3;
  if (squareStatus[col][row][candNum])
    return false;
  return true;
}

void printMap()
{
  for (int i = 0; 9 > i; i++)
  {
    for (int j = 0; 9 > j; j++)
      cout << map[i][j] << ' ';
    cout << '\n';
  }
}

void recursion(vector<pair<int, int>> zeroLoc)
{
  if (zeroLoc.empty())
  {
    printMap();
    exit(0);
  }

  int x = zeroLoc.back().first;
  int y = zeroLoc.back().second;

  zeroLoc.pop_back();

  // 현재 빈 자리에 숫자 1부터 채워넣음
  for (int candNum = 1; 9 >= candNum; candNum++)
  {
    map[x][y] = candNum;

    // 가로, 세로, 네모간 중복되는 숫자가 있는지 확인. 만일 중복되는 숫자가 숫자가 없다면
    if (canRowPlace(candNum, y) && canColPlace(candNum, x) && canSquarePlace(candNum, x, y))
    {
      colStatus[x][candNum] = true;
      rowStatus[y][candNum] = true;
      squareStatus[x / 3][y / 3][candNum] = true;

      // 다음 빈자리를 바탕으로 재귀
      recursion(zeroLoc);

      colStatus[x][candNum] = false;
      rowStatus[y][candNum] = false;
      squareStatus[x / 3][y / 3][candNum] = false;
    }
    map[x][y] = 0;
  }
}

int main(void)
{
  int mapNum;

  for (int i = 0; 9 > i; i++)
    for (int j = 0; 9 > j; j++)
    {
      scanf("%d", &map[i][j]);

      if (map[i][j] == 0)
      {
        zeroLoc.push_back({i, j});
        continue;
      }
      mapNum = map[i][j];
      colStatus[i][mapNum] = true;
      rowStatus[j][mapNum] = true;

      int col = i / 3, row = j / 3;
      squareStatus[col][row][mapNum] = true;
    }

  recursion(zeroLoc);

  return 0;
}

 

 

아래는 자바 코드이다. C++ 코드와 일치하고(벡터를 스택으로 바꾼것만 다름) 답은 제대로 맞는 것을 확인했는데 틀렸습니다가 뜨는데, 아마도 프린트할 때 형식이 맞지 않거나 세부적으로 조금 문제가 있는 듯하다.

 

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

public class Main {
  static int[][] map = new int[9][9];
  static boolean[][] colStatus = new boolean[9][10];
  static boolean[][] rowStatus = new boolean[9][10];
  static boolean[][][] squareStatus = new boolean[3][3][10];

  public static void recursion(Stack<Location> zeroLocations) {
    if (zeroLocations.isEmpty()) {
      printMap();
      System.exit(0);
    }

    Location curLocation = zeroLocations.pop();
    int x = curLocation.x;
    int y = curLocation.y;

    for (int candNum = 1; 9 >= candNum; candNum++) {
      map[x][y] = candNum;

      if (canRowPlace(candNum, y) && canColPlace(candNum, x) && canSquarePlace(candNum, x, y)) {
        colStatus[x][candNum] = true;
        rowStatus[y][candNum] = true;
        squareStatus[x / 3][y / 3][candNum] = true;

        recursion(zeroLocations);

        colStatus[x][candNum] = false;
        rowStatus[y][candNum] = false;
        squareStatus[x / 3][y / 3][candNum] = false;
      }
      map[x][y] = 0;
    }
  }

  public static boolean canRowPlace(int candNum, int rowNum) {
    if (rowStatus[rowNum][candNum])
      return false;

    return true;
  }

  public static boolean canColPlace(int candNum, int colNum) {
    if (colStatus[colNum][candNum])
      return false;
    return true;
  }

  public static boolean canSquarePlace(int candNum, int x, int y) {
    int col = x / 3;
    int row = y / 3;
    if (squareStatus[col][row][candNum])
      return false;
    return true;
  }

  public static void printMap() {
    for (int x = 0; 9 > x; x++) {
      for (int y = 0; 9 > y; y++)
        System.out.print(map[x][y] + " ");
      System.out.println();
    }
  }

  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    Stack<Location> zeroLocations = new Stack<>();
    int mapNum;
    for (int x = 0; 9 > x; x++) {
      StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
      for (int y = 0; 9 > y; y++) {
        mapNum = Integer.parseInt(stringTokenizer.nextToken());
        map[x][y] = mapNum;

        if (mapNum == 0) {
          zeroLocations.add(new Location(x, y));
          continue;
        }
        colStatus[x][mapNum] = true;
        rowStatus[y][mapNum] = true;
        squareStatus[x / 3][y / 3][mapNum] = true;
      }
    }
    recursion(zeroLocations);
  }
}

class Location {
  public int x;
  public int y;

  Location(int x, int y) {
    this.x = x;
    this.y = y;
  }
}

 

 

유사문제 : 스도쿠 (골4, 똑같이 풀고 input & output 살짝 바꾸고 vector -> queue로  고치면 됨) : https://www.acmicpc.net/problem/2239