[백준/Python] 9207번 페그 솔리테어

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

9207번: 페그 솔리테어

 

문제 분석

분류

구현, 브루트포스 알고리즘, 백트래킹

문제

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

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

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

입력

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

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

출력

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

소스코드

# 최대 시간복잡도 계산
# N의 크기 (100) * 핀의 개수(8!) 대략 4백만번
# 8!으로 생각한 이유는 핀을 하나 옮길 때 마다 핀이 하나씩 줄어든다.
# 그렇지 않은 경우는 애초에 움직일 수 없으므로 생각할 필요가 없다.

# 사실 움직이는 조건 특성상 생각보다 움직임이 굉장히 제한되므로
# 로직만 맞는다면 시간복잡도를 가지치기 할 필요가 전혀 없이 잘 돌아간다.


# 핀을 움직였다면 핀 하나는 사라진다.
# 즉 핀을 움직인 횟수 = 핀을 없앤 횟수이다.


from sys import stdin # 입력이 많지는 않지만 그래도 해주는 것이 좋다.
input=stdin.readline

# 4방향으로 움직이므로 아래가 필요하다.
dx=[0,0,1,-1] 
dy=[1,-1,0,0]

def move(movetime): # 매 움직임마다 변하는 보드를 구현할 함수.
    global mincnt,minmove

    # 핀의 위치들을 저장해준다. 동시에 핀의 개수도 알 수 있다.
    pinloc=[]
    for i in range(5):
        for j in range(9):
            if matrix[i][j]=='o':
                pinloc.append((j,i))

    if len(pinloc)<mincnt: # 핀의 위치를 담은 배열의 크기 = 핀의 개수
        minmove=movetime # 가장 적은 움직임을 갱신해준다.
        mincnt=len(pinloc) # 가장 적은 핀의 개수를 갱신해준다.

        # 맨 처음 핀의 수를 세놓았다면
        # 맨 처음 핀의 수 - 가장 적게 남은 핀의 수가 최소 이동횟수이다.
        # 핀의 이동횟수 = 제거한 핀의 수 이기 때문이다.

    for x,y in pinloc: # 각 핀의 위치를 가져온다.
        for i in range(4): # 4방향 이동
            nx=x+dx[i]
            ny=y+dy[i]
            # 바로 인접칸만 고려할 게 아니라, 인접칸을 뛰어 넘은 칸도 고려해야 한다.
            # 따라서 인접 칸을 뛰어넘었을 때도 움직이는 것이 가능하다면
            # 인접 칸은 당연히 이동 가능하므로 비교문을 n?+d?[i]로 작성해주었다.
            if -1<nx+dx[i]<9 and -1<ny+dy[i]<5:
                if matrix[ny][nx]=='o' and matrix[ny+dy[i]][nx+dx[i]]=='.':
                    # 인접한 핀을 뛰어 넘었을 경우 핀을 지우고 그 판의 모양에서 다음 함수 실행해준다.
                    matrix[ny][nx]='.'
                    matrix[ny+dy[i]][nx+dx[i]]='o'
                    matrix[y][x]='.'
                    move(movetime+1)
                    # 다른 경우도 살펴보기 위해 핀을 제거 이전상태로 되돌려준다.
                    matrix[ny][nx]='o'
                    matrix[ny+dy[i]][nx+dx[i]]='.'
                    matrix[y][x]='o'
                        
                        
for tc in range(int(input())):
    mincnt=10 # 핀의 개수는 최대 8개이므로 그냥 10개로 설정해주었다.
    minmove=10 # 핀의 개수는 최대 8개이고 1개 이상으로 남기 때문에 최대 7번 이동이 가능하지만 그냥 10개로 설정했다.
    matrix=[list(input().rstrip()) for i in range(5)]
    input()
    move(0)
    print(mincnt,minmove)

문제풀이

시간복잡도는 굉장히 널널한 문제이다. N의 최대 크기 (100) * 핀의 이동 경우의 수(8!) = 대략 4백만번 정도
움직이는 조건이 빡세가지고 8!까지 나올일도 없어서 문제해결을 위해 최적화를 크게 신경쓸 필요가 없다.

핀을 움직일 때 마다 핀 하나는 사라진다. 그리고 사라진 핀은 다음 고려 대상에 해당되지 않으므로 8개의 핀 중 한개의 핀을 이동시켰다면 7개의 핀이 남게되고 그 7개의 핀에 대한 이동만 고려해주면 된다.

이동할 때 뛰어넘을 핀의 다음 칸까지 고려해야 한다. 이것만 신경써준다면 크게 어려울 것이 없는 문제였다.