🦊 페그 솔리테어

1. 문제 링크

9207번: 페그 솔리테어

2. 코드

Python3 31120KB 140ms

delta = [
    (0,1), (0,-1), (1,0), (-1,0)
]

ROW = 5
COLUMN = 9

N = int(input())

MIN_PIN = 2000000000
MIN_MOVE = 2000000000

def backtracking(move: int):
    global MIN_PIN
    global MIN_MOVE
    # 탈출조건
    flag = False

    # 검사
    for i in range(ROW):
        for j in range(COLUMN):
            if MAP[i][j] == 'o':
                for dr, dc in delta:
                    nr = i + dr
                    nc = j + dc
                    if 0 <= nr < ROW and 0 <= nc < COLUMN and MAP[nr][nc] == 'o':
                        # (nr, nc) not in no_hole and
                        # 구멍을 뛰어넘어 다른 칸으로 이동
                        nnr = nr + dr
                        nnc = nc + dc
                        if 0 <= nnr < ROW and 0 <= nnc < COLUMN and MAP[nnr][nnc] == '.':
                            flag = True
                            # 백트래킹
                            MAP[i][j] = '.'
                            MAP[nr][nc] = '.'
                            MAP[nnr][nnc] = 'o'
                            backtracking(move + 1)
                            # 복귀
                            MAP[i][j] = 'o'
                            MAP[nr][nc] = 'o'
                            MAP[nnr][nnc] = '.'

    # 모든 칸에서 이동이 불가하면
    if not flag:
        pin = 0
        for i in range(ROW):
            for j in range(COLUMN):
                if MAP[i][j] == 'o':
                    pin += 1
        if pin < MIN_PIN:
            MIN_MOVE = move
            MIN_PIN = pin

for n in range(N):
    MIN_PIN = 2000000000
    MIN_MOVE = 2000000000
    MAP = []
    for i in range(ROW):
        MAP.append(list(input()))

    backtracking(0)

    print(MIN_PIN, MIN_MOVE)

    if n < N - 1:
        input()

3. 해설

인접한 칸 ⇒ 해당 핀의 상하좌우에 해당되는 핀 이를 뛰어넘어 구멍이 있는 칸일 경우 백트래킹 시행 flag 로 모든 칸에 대해 이동을 1번이라도 할 수 있는지 검사해서, 그렇지 않을 경우 모든 맵의 핀을 검사 핀의 개수가 최소일 경우 이동횟수 갱신