[백준] 4574번 : 스도미노쿠

문제

 

---

풀이

 

일단 주어진 도미노의 총 개수는 36개이므로 이 도미노들의 정보와 사용여부를 map으로 관리하기로 했다.

그리고 빈 공간을 발견할 때마다 가로 또는 세로로 배치할 수 있는 도미노를 찾아보는데

1	1
1

상하좌우로 배치할 필요없이 그냥 2개의 방향만 고려하면 된다.

위 또는 왼쪽으로 배치하는건 이전 경우에서 고려됐을 것이기 때문이다.

 

아무튼 그래도 하나의 위치에 대해 최대 4개의 경우를 고려해야 한다. (가로세로)*(도미노 방향 2)

하나의 도미노에 적힌 숫자는 다르기 때문에 해당 위치에 이 도미노가 들어갈 수 있을지 확인할 때 도미노를 쪼개서 각각 고려해도 문제가 없다.

 

https://myunji.tistory.com/202

[백준] 2580번 : 스도쿠

이 때 사용한 promising 함수를 그대로 사용해도 된다는 뜻이다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>

using namespace std;
typedef pair<int, int> pp;

vector<vector<int>> board;
map<pp, bool> domino;
bool is_found;

void initDomino() { //사용 가능한 도미노 초기화
    for (int i = 1; i <= 8; i++) {
        for (int j = i + 1; j <= 9; j++) {
            domino[make_pair(i, j)] = true;
        }
    }
}

pp makePos(string pos) { //string 입력을 좌표로 변경
    int r = pos[0] - 'A';
    int c = (pos[1] - '0') - 1;
    return make_pair(r, c);
}

bool isPromise(pp pos, int num) { //해당 위치에 숫자 입력 가능한지 확인
    int row = pos.first;
    int col = pos.second;
    int r_sector = row / 3;
    int c_sector = col / 3;

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if ((i == row) && (j == col))
                continue;
            if (((i == row) || (j == col)) && (board[i][j] == num)) //같은 행 또는 열에 이미 숫자가 있음
                return false;
            else if (((i / 3) == r_sector) && ((j / 3) == c_sector) && (board[i][j] == num)) //같은 구역에 이미 숫자가 있음
                return false;
        }
    }
    return true;
}

void inputDomino(pp domino_pos, pp board_input, pp pos1, pp pos2){ //도미노 넣기
    domino[domino_pos] = false;
    board[pos1.first][pos1.second] = board_input.first;
    board[pos2.first][pos2.second] = board_input.second;
}

void retrieveDomino(pp domino_pos, pp pos1, pp pos2){ //도미노 뺴기
    domino[domino_pos] = true;
    board[pos1.first][pos1.second] = 0;
    board[pos2.first][pos2.second] = 0;
}

void backtracking(int cnt) {
    if (cnt == 81) { //결과 찾음
        is_found = true;
        return;
    }
    int r = cnt / 9; //행
    int c = cnt % 9; //열
    if (board[r][c] == 0) { //빈공간이라면
        vector<pp> tmp;
        if ((r + 1 < 9) && (board[r + 1][c] == 0)) //세로 배치
            tmp.push_back(make_pair(r + 1, c));
        if ((c + 1 < 9) && (board[r][c + 1] == 0)) //가로 배치
            tmp.push_back(make_pair(r, c + 1));
        if (tmp.size() == 0) //도미노 배치할 수 없음
            return;
        for (auto iter = domino.begin(); iter != domino.end(); iter++) { //남아있는 도미노 넣어보기
            if (!iter->second) //이미 배치한 도미노
                continue;
            if (isPromise(make_pair(r, c), iter->first.first)) { //똑바로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.second)) {
                        inputDomino(iter->first, iter->first, make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }
            if (isPromise(make_pair(r, c), iter->first.second)) { //반대로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.first)) {
                        inputDomino(iter->first, make_pair(iter->first.second, iter->first.first), make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }
        }
    } else //이미 채워져있으면 백트래킹 호출
        backtracking(cnt + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int input, puzzle_cnt = 1;
    string single_input;
    pair<int, string> input_info[2];
    pp pos;

    while (true) {
        cin >> input;
        if (input == 0) //입력 종료
            break;

        is_found = false;
        initDomino();
        board.assign(9, vector<int>(9, 0));
        for (int i = 0; i < input; i++) {
            for (int j = 0; j < 2; j++) { //좌표 받아서 board에 입력
                cin >> input_info[j].first >> input_info[j].second;
                pos = makePos(input_info[j].second);
                board[pos.first][pos.second] = input_info[j].first;
            }
            if (input_info[0].first > input_info[1].first) //오름차순 정렬
                swap(input_info[0], input_info[1]);
            domino[make_pair(input_info[0].first, input_info[1].first)] = false; //도미노 사용 처리
        }
        for (int i = 1; i <= 9; i++) { //좌표 받아서 board에 입력
            cin >> single_input;
            pos = makePos(single_input);
            board[pos.first][pos.second] = i;
        }
        cout << "Puzzle " << puzzle_cnt << '\n'; //출력
        backtracking(0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << board[i][j];
            cout << '\n';
        }
        puzzle_cnt++;
    }
}

전체 소스코드다.

 

vector<vector<int>> board;
map<pp, bool> domino;
bool is_found;

스도미노쿠의 현상태를 저장할 벡터, domino의 사용여부를 확인할 map, 그리고 정답을 찾았는지 확인할 bool 변수다.

 

    while (true) {
        cin >> input;
        if (input == 0) //입력 종료
            break;

        is_found = false;
        initDomino();
        board.assign(9, vector<int>(9, 0));
        for (int i = 0; i < input; i++) {
            for (int j = 0; j < 2; j++) { //좌표 받아서 board에 입력
                cin >> input_info[j].first >> input_info[j].second;
                pos = makePos(input_info[j].second);
                board[pos.first][pos.second] = input_info[j].first;
            }
            if (input_info[0].first > input_info[1].first) //오름차순 정렬
                swap(input_info[0], input_info[1]);
            domino[make_pair(input_info[0].first, input_info[1].first)] = false; //도미노 사용 처리
        }
        for (int i = 1; i <= 9; i++) { //좌표 받아서 board에 입력
            cin >> single_input;
            pos = makePos(single_input);
            board[pos.first][pos.second] = i;
        }
        cout << "Puzzle " << puzzle_cnt << '\n'; //출력
        backtracking(0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << board[i][j];
            cout << '\n';
        }
        puzzle_cnt++;
    }

일단 입력을 받자

 

        cin >> input;
        if (input == 0) //입력 종료
            break;

        is_found = false;
        initDomino();
        board.assign(9, vector<int>(9, 0));

종료조건을 써주고, 각 테스트케이스마다 전역변수들을 초기화 한다.

 

void initDomino() { //사용 가능한 도미노 초기화
    for (int i = 1; i <= 8; i++) {
        for (int j = i + 1; j <= 9; j++) {
            domino[make_pair(i, j)] = true;
        }
    }
}

도미노 맵은 initDomino 함수로 초기화 하는데, 각 도미노의 숫자들이 오름차순으로 입력되도록 했다.

(1, 2), (1, 3) ... (8, 9) 이런식으로

 

        for (int i = 0; i < input; i++) {
            for (int j = 0; j < 2; j++) { //좌표 받아서 board에 입력
                cin >> input_info[j].first >> input_info[j].second;
                pos = makePos(input_info[j].second);
                board[pos.first][pos.second] = input_info[j].first;
            }
            if (input_info[0].first > input_info[1].first) //오름차순 정렬
                swap(input_info[0], input_info[1]);
            domino[make_pair(input_info[0].first, input_info[1].first)] = false; //도미노 사용 처리
        }

도미노의 초기입력을 받는다.

pair<int, string> 형인 input_info 배열에 입력을 받고 각 input_info에 대해 makePos로 좌표를 찾아준다.

그리고나서 board에 입력하면 된다.

 

그 후에 input_info 배열을 숫자 기준으로 오름차순 정렬하고 해당하는 도미노를 사용처리한다.

pp makePos(string pos) { //string 입력을 좌표로 변경
    int r = pos[0] - 'A';
    int c = (pos[1] - '0') - 1;
    return make_pair(r, c);
}

string 입력을 좌표로 변환하는 코드는 위와같다.

 

        for (int i = 1; i <= 9; i++) { //좌표 받아서 board에 입력
            cin >> single_input;
            pos = makePos(single_input);
            board[pos.first][pos.second] = i;
        }

그리고 하나씩 들어오는 9개의 입력을 받고 도미노의 좌표를 찾을때와 같이 좌표를 찾아 board에 입력한다.

 

        cout << "Puzzle " << puzzle_cnt << '\n'; //출력
        backtracking(0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                cout << board[i][j];
            cout << '\n';
        }
        puzzle_cnt++;

백트래킹 함수를 호출해서 답을 찾는다.

 

void backtracking(int cnt) {
    if (cnt == 81) { //결과 찾음
        is_found = true;
        return;
    }
    int r = cnt / 9; //행
    int c = cnt % 9; //열
    if (board[r][c] == 0) { //빈공간이라면
        vector<pp> tmp;
        if ((r + 1 < 9) && (board[r + 1][c] == 0)) //세로 배치
            tmp.push_back(make_pair(r + 1, c));
        if ((c + 1 < 9) && (board[r][c + 1] == 0)) //가로 배치
            tmp.push_back(make_pair(r, c + 1));
        if (tmp.size() == 0) //도미노 배치할 수 없음
            return;
        for (auto iter = domino.begin(); iter != domino.end(); iter++) { //남아있는 도미노 넣어보기
            if (!iter->second) //이미 배치한 도미노
                continue;
            if (isPromise(make_pair(r, c), iter->first.first)) { //똑바로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.second)) {
                        inputDomino(iter->first, iter->first, make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }
            if (isPromise(make_pair(r, c), iter->first.second)) { //반대로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.first)) {
                        inputDomino(iter->first, make_pair(iter->first.second, iter->first.first), make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }
        }
    } else //이미 채워져있으면 백트래킹 호출
        backtracking(cnt + 1);
}

백트래킹 함수다.

 

    if (cnt == 81) { //결과 찾음
        is_found = true;
        return;
    }

cnt가 81이라면 판의 끝까지 도달했다는 뜻이다.

그럼 is_found를 true로 바꿔주고 리턴한다.

 

    int r = cnt / 9; //행
    int c = cnt % 9; //열

그렇지 않다면 이번 위치의 행과 열을 계산한다.

 

    if (board[r][c] == 0) { //빈공간이라면
        /.../
    } else //이미 채워져있으면 백트래킹 호출
        backtracking(cnt + 1);

해당 위치에 0이 있다면 빈공간이니 공간을 채울 값을 찾아야하고

이미 숫자가 채워져있다면 백트래킹 함수를 호출한다.

 

        vector<pp> tmp;
        if ((r + 1 < 9) && (board[r + 1][c] == 0)) //세로 배치
            tmp.push_back(make_pair(r + 1, c));
        if ((c + 1 < 9) && (board[r][c + 1] == 0)) //가로 배치
            tmp.push_back(make_pair(r, c + 1));
        if (tmp.size() == 0) //도미노 배치할 수 없음
            return;
        for (auto iter = domino.begin(); iter != domino.end(); iter++) { //남아있는 도미노 넣어보기
            if (!iter->second) //이미 배치한 도미노
                continue;
            if (isPromise(make_pair(r, c), iter->first.first)) { //똑바로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.second)) {
                        inputDomino(iter->first, iter->first, make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }
            if (isPromise(make_pair(r, c), iter->first.second)) { //반대로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.first)) {
                        inputDomino(iter->first, make_pair(iter->first.second, iter->first.first), make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }
        }

빈공간에 채울 숫자를 찾는 과정이다.

 

        vector<pp> tmp;
        if ((r + 1 < 9) && (board[r + 1][c] == 0)) //세로 배치
            tmp.push_back(make_pair(r + 1, c));
        if ((c + 1 < 9) && (board[r][c + 1] == 0)) //가로 배치
            tmp.push_back(make_pair(r, c + 1));
        if (tmp.size() == 0) //도미노 배치할 수 없음
            return;

먼저 가로 또는 세로로 도미노를 배치할 수 있다면 해당 위치를 tmp 벡터에 넣어준다.

만약 tmp의 크기가 0이라면 어떤 방향으로도 도미노를 배치할 수 없다는 뜻이니 리턴한다.

 

        for (auto iter = domino.begin(); iter != domino.end(); iter++) { //남아있는 도미노 넣어보기
            if (!iter->second) //이미 배치한 도미노
                continue;
            if (isPromise(make_pair(r, c), iter->first.first)) { //똑바로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.second)) {
                        inputDomino(iter->first, iter->first, make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }
            if (isPromise(make_pair(r, c), iter->first.second)) { //반대로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.first)) {
                        inputDomino(iter->first, make_pair(iter->first.second, iter->first.first), make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }
        }

배치 가능한 도미노를 찾는 과정이다.

 

도미노 map을 돌면서 아직 배치하지 않은 도미노를 찾는다.

만약 찾았다면 배치를 해본다.

 

            if (isPromise(make_pair(r, c), iter->first.first)) { //똑바로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.second)) {
                        inputDomino(iter->first, iter->first, make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }

먼저 똑바로 넣어보는데 빈공간에 도미노의 한쪽이 들어갈 수 있다면

tmp 벡터를 돌면서 나머지 한쪽도 들어갈 수 있는지 확인하고 들어갈 수 있다면 백트래킹을 호출한다.

 

bool isPromise(pp pos, int num) { //해당 위치에 숫자 입력 가능한지 확인
    int row = pos.first;
    int col = pos.second;
    int r_sector = row / 3;
    int c_sector = col / 3;

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if ((i == row) && (j == col))
                continue;
            if (((i == row) || (j == col)) && (board[i][j] == num)) //같은 행 또는 열에 이미 숫자가 있음
                return false;
            else if (((i / 3) == r_sector) && ((j / 3) == c_sector) && (board[i][j] == num)) //같은 구역에 이미 숫자가 있음
                return false;
        }
    }
    return true;
}

숫자의 투입가능여부는 2580번의 코드와 거의 같다.

 

void inputDomino(pp domino_pos, pp board_input, pp pos1, pp pos2){ //도미노 넣기
    domino[domino_pos] = false;
    board[pos1.first][pos1.second] = board_input.first;
    board[pos2.first][pos2.second] = board_input.second;
}

도미노를 board에 넣는 함수는 이와같다.

도미노를 반대로도 넣어야하는데 코드의 중복을 막고자 함수로 뺐다.

 

void retrieveDomino(pp domino_pos, pp pos1, pp pos2){ //도미노 뺴기
    domino[domino_pos] = true;
    board[pos1.first][pos1.second] = 0;
    board[pos2.first][pos2.second] = 0;
}

넣었던 도미노를 뺴는 함수다.

 

            if (isPromise(make_pair(r, c), iter->first.second)) { //반대로 넣어보기
                for (int i = 0; i < tmp.size(); i++) {
                    if (isPromise(tmp[i], iter->first.first)) {
                        inputDomino(iter->first, make_pair(iter->first.second, iter->first.first), make_pair(r, c), tmp[i]); //visited 처리
                        backtracking(cnt + 1); //백트래킹 호출
                        if (is_found) //이미 답을 찾았다면 리턴
                            return;
                        retrieveDomino(iter->first, make_pair(r, c), tmp[i]); //unvisited 처리
                    }
                }
            }

도미노를 반대로 넣어보는 과정도 비슷하다.

 

아무튼 이렇게 답을 찾고 출력하면 된다.