[BOJ/Gold 4] 백준 17492 바둑알 점프(C++)

문제 링크

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

17492번: 바둑알 점프

 

문제

바둑알 점프는 판 위에 있는 바둑알을 하나만 남기고 모두 없애는 게임이다. 바둑알은 가로, 세로, 대각선으로 인접한 바둑알 하나를 점프하여 움직일 수 있다. 움직였을 때, 뛰어넘은 바둑알은 없어진다. 이때 뛰어넘을 바둑알이 없으면 움직일 수 없다.

 

 

예를 들어, [그림1]에서 왼쪽 상단 바둑알을 오른쪽 하단 대각선 방향으로 움직이면 [그림2] 와 같이 된다. [그림3]에서 오른쪽 하단에 있는 바둑알은 뛰어 넘을 바둑알이 없으므로 움직일 수 없다.

바둑알이 놓이는 판은 N × N의 정사각 행렬이고 한 칸은 1 × 1 행렬이다. 판은 빈 칸 혹은 벽으로 구성된다. 바둑알은 항상 빈 칸으로만 이동할 수 있고 벽을 뛰어넘을 수 없다. 바둑알이 없어진 칸은 빈 칸이 된다. 바둑알 점프는 바둑알 하나를 골라 점프하여 바둑알 하나를 없애고 다시 남은 바둑알들 중에 하나를 골라 점프하는 행위를 반복하여 바둑알을 1개만 남기면 승리한다.

판 위에 바둑알의 배치 정보가 주어진다. 바둑알 점프를 했을 때 승리할 수 있는지 판별하는 프로그램을 작성하라.

 

입력

입력의 첫 줄에 양의 정수 N이 주어진다. 이는 N × N 정사각 행렬의 한 변의 길이이다. 그 다음 줄부터 N개의 줄에 걸쳐 판의 상태가 주어진다. 각 줄은 N개의 정수가 공백으로 구분되어 주어지는데, 각각의 정수는 0, 1 또는 2이다. 여기서 0은 빈 칸, 1은 벽, 2는 바둑알을 의미한다.

 

출력

바둑알 점프를 하여 바둑알을 1개만 남길 수 있다면 Possible을, 불가능하다면 Impossible을 출력한다.

 

제한

• 3 ≤ N ≤ 10
• 입력으로 주어지는 판의 둘레에 있는 칸들은 모두 벽이며, 모든 바둑알은 빈 칸에 위치한다.

 

서브태스크 1 (60점)

• 바둑알의 수가 1 이상 2 이하이다.

 

서브태스크 2 (40점)

• 바둑알의 수가 1 이상 7 이하이다.

 

예제 입력 1

5
1 1 1 1 1
1 2 2 0 1
1 2 2 0 1
1 0 0 0 1
1 1 1 1 1

예제 출력 1

Possible

예제 입력 2

5
1 1 1 1 1
1 2 2 0 1
1 2 0 0 1
1 0 0 2 1
1 1 1 1 1

예제 출력 2

Impossible

예제 입력 3

3
1 1 1
1 2 1
1 1 1

예제 출력 3

Possible

 

알고리즘 분류

• 백트래킹

 

풀이

모든 바둑알의 8방향을 전부 탐색하여 다음 칸에 바둑알이 있고, 그 다음 칸으로 현재 바둑알이 이동할 수 있는지 파악한다.

가능하다면 다음 칸의 바둑알을 제거하고 현재 바둑알을 그 다음 칸으로 이동시킨다.

가능한 경우를 모두 탐색하면서 최종적으로 바둑알이 1개만 남게 된다면 재귀를 종료한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 11
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct HORSE {
    int Y, X;
};

int N;
int MAP[MAX][MAX];
vector<HORSE> Horses;
int MoveY[8] = { -1,-1,-1,0,1,1,1,0 };
int MoveX[8] = { -1,0,1,1,1,0,-1,-1 };
bool Answer = false;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> MAP[i][j];
            if (MAP[i][j] == 2) {
                Horses.push_back({ i,j });
            }
        }
    }
}

bool find_Horses() {
    int Result = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (MAP[i][j] == 2) {
                Result++;
            }
        }
    }

    if (Result == 1) {
        return true;
    }

    return false;
}

void DFS(vector<HORSE> NextHorses) {
    if (find_Horses()) {
        Answer = true;
        return;
    }

    for (int i = 0; i < (int)NextHorses.size(); i++) {
        int NowY = NextHorses[i].Y;
        int NowX = NextHorses[i].X;
        if (MAP[NowY][NowX] != 2) {
            continue;
        }
        for (int j = 0; j < 8; j++) {
            int NextY = NowY + MoveY[j];
            int NextX = NowX + MoveX[j];
            int NNextY = NextY + MoveY[j];
            int NNextX = NextX + MoveX[j];
            if ((NextY >= 0) && (NextY < N) && (NextX >= 0) && (NextX < N) && (MAP[NextY][NextX] == 2)
                && (NNextY >= 0) && (NNextY < N) && (NNextX >= 0) && (NNextX < N) && (MAP[NNextY][NNextX] == 0)) {
                MAP[NowY][NowX] = 0;
                MAP[NextY][NextX] = 0;
                NextHorses[i].Y = NNextY;
                NextHorses[i].X = NNextX;
                MAP[NNextY][NNextX] = 2;
                DFS(NextHorses);
                MAP[NNextY][NNextX] = 0;
                NextHorses[i].Y = NowY;
                NextHorses[i].X = NowX;
                MAP[NextY][NextX] = 2;
                MAP[NowY][NowX] = 2;
            }
        }
    }
}

void settings() {
    DFS(Horses);
}

void find_Answer() {
    if (Answer) {
        cout << "Possible\n";
    }
    else {
        cout << "Impossible\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}