[ BOJ ] 17492 : 바둑알 점프 ( GOLD 4 ) / Python

문제

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

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

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

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

입력

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

출력

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

풀이 과정

바둑알이 점프한다고 하길래 한 칸을 뛰어넘어 멀리까지 갈 수 있는 장기의 포를 생각해서 구현했는데... 그냥 앞에 있는 흰 돌만 넘을 수 있는 거였다. "인접한 바둑알 하나를 점프하여 움직일 수 있다." 라는 문장을 봤어야 하는데 못 봤다 ㅠ

백트래킹으로 풀이했다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
maps = [list(map(int, input().rstrip().split())) for _ in range(n)]

white = 0
for i in range(n):
    for j in range(n):
        if maps[i][j] == 2: white += 1

row = [-1, 1, 0, 0, -1, -1, 1, 1]
col = [0, 0, -1, 1, -1, 1, -1, 1]
result = 0

def backtracking(now_white):
    global result
    if now_white == 1:
        result = 1
        return

    for y in range(n):
        for x in range(n):
            if maps[y][x] != 2: continue
            for d in range(8):
                ny = y + row[d]
                nx = x + col[d]
                nny = ny + row[d]
                nnx = nx + col[d]

                if 0 <= ny < n and 0 <= nx < n and 0 <= nny < n and 0 <= nnx < n and maps[ny][nx] == 2 and maps[nny][nnx] == 0:
                    maps[y][x] = 0
                    maps[ny][nx] = 0
                    maps[nny][nnx] = 2
                    backtracking(now_white - 1)
                    maps[y][x] = 2
                    maps[ny][nx] = 2
                    maps[nny][nnx] = 0

backtracking(white)

print('Possible' if result == 1 else 'Impossible')