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

9207번: 페그 솔리테어

from collections import deque
n = int(input())

dx = [-1,1,0,0]
dy = [0,0,-1,1]

dx_2 = [-2,2,0,0]
dy_2 = [0,0,-2,2]

result = []

def move(movetime):

    global min_count, min_movement

    pin_list = []

    for i in range(5):
        for j in range(9):
            if area[i][j] == 'o':
                pin_list.append((i,j))

    if len(pin_list) < min_count:
        min_movement = movetime
        min_count = len(pin_list)

    for x,y in pin_list:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            nx_2, ny_2 = x + dx_2[i], y + dy_2[i]
            if 0 <= nx < 5 and 0 <= ny < 9 and area[nx][ny]=='o' and 0 <= nx_2 < 5 and 0 <= ny_2 < 9 and area[nx_2][ny_2] == '.':
                area[nx_2][ny_2] = 'o'
                area[x][y] = '.'
                area[nx][ny] = '.'
                move(movetime+1)
                area[nx_2][ny_2] = '.'
                area[x][y] = 'o'
                area[nx][ny] = 'o'         

for i in range(n):
    min_count = 10
    min_movement = 10
    area = [list(input().rstrip()) for _ in range(5)]
    if i != n-1:
        input()
    move(0)
    result.append((min_count,min_movement))

for i in result:
    print(f'{i[0]} {i[1]}')

이번 문제는 주어진 조건에 맞게 핀을 최대한 제거했을 때 남게 되는 핀의 개수와 최소 이동횟수를 구하는 문제이다.

 

문제 내용 자체를 이해하는 것과 DFS 및 Backtracking 알고리즘을 떠올리는 것은 크게 어렵지 않았는데, 실제로 DFS를 작동시킬 때 어떤 방식으로 탐색을 해야할지 잘 떠올리지 못한 것 같다.

 

결국 DFS를 사용하여 핀이 존재하는 모든 위치에서 이동시켜가며 탐색을 하고, 모든 경우의 수를 계산하기 위해 원래 상태로 복구시켜주는 작업까지 해주어야하는 문제였다.

 

그리고 재귀함수를 사용할 때 탐색의 깊이(Depth)를 저장하기 위해 '인자를 전달해주는 방식'을 사용할 수 있다는 것을 떠올리지 못하여 풀이를 제대로 하지 못한 것 같다.

 배운 점 및 느낀 점

1. 재귀함수를 사용한 DFS에서 탐색의 깊이를 구하기 위해서는 인자로 값을 전달하는 방법이 있다 !
2. DFS를 사용할 경우 탐색의 대상은 동작할 수 있는 모든 경우의 수이다.(해당 문제의 경우에는 핀이 꽂혀있는 모든 위치)
3. 모든 경우의 수를 DFS로 계산할 때는 현재의 변경이 다음 경우의 수에 영향을 미치면 안되기 때문에 반드시 원래 상태로 되돌려주는 작업을 해주어야 한다 !