백준9270(페그 솔리테어) - 해결

페그 솔리테어

문제

페그 솔리테어는 구멍이 뚫려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다.

핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다.

현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또, 그렇게 남기기 위해 필요한 최소 이동횟수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 1 ≤ N ≤ 100이 주어진다. 각 테스트 케이스는 게임판의 초기 상태이다.

게임판은 모두 같은 모양을 가진다. (예제 참고) '.'는 빈 칸, 'o'는 핀이 꽂혀있는 칸, '#'는 구멍이 없는 칸이다. 핀의 개수는 최대 8이며, 각 테스트 케이스는 빈 줄로 구분되어져 있다.

 

출력

각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다.

---

핀의 개수가 적은것을 보고 dfs일꺼라 생각해서 dfs로 풀었다.

조금 노가다성이 있었지만 맵에 패딩을 주고 탐색을 하였고

pin과 맵을 초기화 하면서 dfs로 바꾸었다.

따로 return은 두지 않고 모두 돌려주었고 핀 개수가 줄어들면 갱신하고

핀 개수가 같을때 횟수가 줄어들어도 갱신하였다.

'''
페그 솔리테어

'''
import sys
input = sys.stdin.readline
from copy import deepcopy
# N 값
N = int(input())

# 탐색
def dfs(pins,cnt):
    global maps, min_pin, min_cnt

    # 핀 개수가 죽어들면
    if len(pins) < min_pin:
        min_pin = len(pins)
        min_cnt = cnt
    # 핀 개수가 같을 때, 횟수가 줄어들면
    elif len(pins) == min_pin and cnt < min_cnt:
        min_pin = len(pins)
        min_cnt = cnt
    
    # 각 핀 마다 탐색
    for pin in pins:
        # 4방향 탐색
        for i in range(4):
            # 옆 확인
            next_x =  pin[0] + dirs[i][0]
            next_y =  pin[1] + dirs[i][1]
            # 뛰어 넘을 곳 확인
            ck_x = next_x + dirs[i][0]
            ck_y = next_y + dirs[i][1]
            # 옆이 핀이고 뛰어 넘을 수 있으면
            if maps[next_x][next_y] == 'o' and maps[ck_x][ck_y] == '.':
                # deepcopy로 복사
                next_pins = deepcopy(pins)
                # pins 사용을 갱신
                next_pins.remove(pin)
                next_pins.remove((next_x,next_y))
                next_pins.append((ck_x,ck_y))
                # 맵 핀 이동
                maps[pin[0]][pin[1]] = "."
                maps[next_x][next_y] = "."
                maps[ck_x][ck_y] = "o"
                dfs(next_pins, cnt+1)
                # 다시 초기화
                maps[pin[0]][pin[1]] = "o"
                maps[next_x][next_y] = "o"
                maps[ck_x][ck_y] = "."

# 각 맵 마다
for tc in range(N):
    # 맵에 패딩 주기
    maps = []
    maps.append(["#"] * 11)
    for _ in range(5):
        maps.append(["#"] + list(input().strip()) + ["#"])
    maps.append(["#"] * 11)
    if tc != N-1:
        input()    

    # 핀 위치 저장
    pins = []
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == "o":
                pins.append((i,j))
    
    dirs = [(-1,0),(0,1),(1,0),(0,-1)]

    min_pin = len(pins)
    min_cnt = 987654321
    
    dfs(pins,0)

    print(min_pin,min_cnt)