[BOJ] 10429번 - QUENTO

백준 10429번 - QUENTO

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	254	120	106	49.533%

문제

Quento는 Q42에서 만든 게임이다. 이 게임의 게임판은 항상 3×3 크기이며, 오른쪽 그림과 같이 검정색 칸에는 숫자, 흰색 칸에는 +또는 -가 적혀져 있다.

게임판의 상단에는 만들어야하는 숫자 N과 사용해야 하는 숫자의 개수 M이 주어진다. 이제 숫자에서 스와이프를 시작해 +/-로 이동한 다음, 다시 숫자로 스와이프를 하고, 이런식으로 숫자를 M개 지났을 때, 결과가 N이 되어야 한다. 이미 방문한 칸은 재방문 할 수 없으며, 다시 지나가는 것도 불가능하다.

예를 들어, 7을 숫자 2개를 이용해서 만들려면, 4+3, 9-2는 가능하다. 하지만, 5+3-1은 숫자 3개를 이용했기 때문에 불가능하다.

N과 M, 그리고 게임판에 쓰여 있는 숫자와 +/-가 주어진다. 이때, 숫자 M개를 이용해서 N을 만드는 방법을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 45, 2 ≤ M ≤ 5) 둘째 줄부터 3개의 줄에 걸쳐 게임판에 써잇는 숫자와 +/-가 주어진다. 숫자는 항상 한자리 숫자이고, 0이 아니다.

 

출력

M개의 숫자를 이용해서 N을 만들 수 있으면, 첫째 줄에 1을 출력하고, 없는 경우에는 0을 출력한다. 그 다음, 숫자를 만들 수 있는 경우에는 방문한 칸을 총 2*M-1개 줄에 걸쳐서 출력한다. 가장 왼쪽 윗칸의 좌표는 (0, 0), 왼쪽 아랫칸의 좌표는 (2, 0), 오른쪽 윗칸의 좌표는 (0, 2), 오른쪽 아랫칸의 좌표는 (2, 2)이다.

가능한 방법이 여러 가지인 경우 아무거나 하나만 출력한다.

---

예제 입력 1

11 2
6+5
-3-
8+4

예제 출력 1

1
0 0
0 1
0 2

예제 입력 2

1 3
6+5
-3-
8+4

예제 출력 2

1
2 2
2 1
1 1
1 0
0 0

예제 입력 3

15 3
6+5
-3-
8+4

예제 출력 3

0

출처

www.acmicpc.net/problem/10429

10429번: QUENTO

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색

접근 방법

가능한 모든 경우를 찾는 문제이다.

3*3 이라는 작은 크기 때문에, 충분히 Brute-Force방식으로 해결할 수 있는 문제이다.

Backtracking을 위해 DFS를 통해 구현하였다.

단, 문제의 조건 상 숫자와 연산자가 번갈아서 나오는 것을 잘 고려해 주어야 한다.

숫자 M개를 활용하여 값을 만들 때 연산자의 개수는 M-1개가 나오는 것을 고려하여 수식의 2번째 항(연산자) 부터 DFS를 돌려서 탐색하였다.( 숫자 : M-1 개 , 연산자 : M-1개 )

 또한, 이전에 택한 것이 숫자라면 다음 DFS에서는 연산자를 뽑아야한다. 

그것을 구분하기 위해 DFS의 매개변수로 option을 넘겨 주었다.

소스 코드

#define OPT_NUMBER 0
#define OPT_OPERATOR 1
#include <bits/stdc++.h>
using namespace std;
int N, M;
char board[3][3] ;

bool visited[3][3];
vector<pair<int,int>> v; // 경로를 담을 임시 변수
vector<pair<int,int>> answer_path;
int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

string expression;
int calculate( const string& exp ){
    int ret = exp[0] - '0' ;
    for(int i=1; i<exp.size()-1; i++){
        char op = exp[i];
        int factor = exp[i+1] - '0';
        if( op == '+' ) ret += factor;
        else if( op == '-' ) ret -= factor;
    }
    return ret;
}
void DFS(int y, int x, int surplus,  bool option){
    if( surplus == 0 ){
        int sum = calculate(expression);
        if( sum == N ){
            answer_path = v;
        }
        return ;
    }

    for(int i=0; i<4; i++){
        int ny = y + dir[i][0], nx = x + dir[i][1];
        if( ny < 0 || nx < 0 || ny >= 3 || nx >= 3 || visited[ny][nx] ) continue;
        if( option == OPT_NUMBER ){
            if( '1' <= board[ny][nx] && board[ny][nx] <= '9' ){
                v.push_back({ny, nx});
                expression.push_back(board[ny][nx]);
                visited[ny][nx] = true;
                DFS(ny, nx, surplus-1, !option);
                visited[ny][nx] = false;
                expression.pop_back();
                v.pop_back();
            }
        }
        else{
            if( board[ny][nx] == '+' || board[ny][nx] == '-' ){
                v.push_back({ny,nx});
                expression.push_back(board[ny][nx]);
                visited[ny][nx] = true;
                DFS(ny, nx, surplus, !option);
                visited[ny][nx] = false;
                expression.pop_back();
                v.pop_back();
            }
        }
    }
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N >> M;

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++)
            cin >> board[i][j];
    }

    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if( board[i][j] <= '0' || board[i][j] > '9' ) continue;
            v.push_back({i,j});
            expression.push_back(board[i][j]);
            visited[i][j] = true;

            DFS(i,j, M-1, OPT_OPERATOR);

            visited[i][j] = false;
            expression.pop_back();
            v.pop_back();
        }
    }

    if( answer_path.empty() ) cout << 0 ;
    else {
        cout << 1 << '\n';
        for (auto elem : answer_path)
            cout << elem.first << ' ' << elem.second << '\n';
    }

    return 0;
}