[BOJ] 16197 두 동전

딱히 뚜렷한 방법이 생각이 나지 않았습니다.. 그래서 그냥 맨 처음 생각났던 '한번에 두개 해보자'로 풀기 시작했습니다.

from sys import stdin
input=stdin.readline

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

n,m=map(int,input().split())
board=[list(input().rstrip()) for i in range(n)]
vi1=[[0 for i in range(m)]for i in range(n)]
vi2=[[0 for i in range(m)]for i in range(n)]

coins=[]
ans=11

for i in range(n):
    for j in range(m):
        if board[i][j]=='o':
            coins.append((j,i))

def dfs(coin1,coin2,tmpt):
    global ans
    if tmpt>=ans:
        return
    coin1_moved=False
    coin2_moved=False
    for i in range(4):
        fallen=0
        nx1=coin1[0]+dx[i]
        ny1=coin1[1]+dy[i]
        nx2=coin2[0]+dx[i]
        ny2=coin2[1]+dy[i]
        if nx1<0 or ny1<0 or nx1>=m or ny1>=n:
            fallen+=1
        if nx2<0 or ny2<0 or nx2>=m or ny2>=n:
            fallen+=1
        if fallen==1:
            ans=min(ans,tmpt+1)
            continue
        elif fallen==2:
            continue
        elif ny1==ny2 and nx1==nx2:
            continue
        if board[ny1][nx1]=='#':
            nx1=coin1[0]
            ny1=coin1[1]
        if board[ny2][nx2]=='#':
            nx2=coin2[0]
            ny2=coin2[1]
        if board[ny1][nx1]=='.' and vi1[ny1][nx1]==0:
            board[ny1][nx1],board[coin1[1]][coin1[0]]=board[coin1[1]][coin1[0]],board[ny1][nx1]
            vi1[ny1][nx1]=1
            coin1_moved=True
        if board[ny2][nx2]=='.' and vi2[ny2][nx2]==0:
            board[ny2][nx2],board[coin2[1]][coin2[0]]=board[coin2[1]][coin2[0]],board[ny2][nx2]
            vi2[ny2][nx2]=1
            coin2_moved=True
        if coin1_moved or coin2_moved:
            dfs((nx1,ny1),(nx2,ny2),tmpt+1)
        if coin1_moved:
            board[ny1][nx1],board[coin1[1]][coin1[0]]=board[coin1[1]][coin1[0]],board[ny1][nx1]
            vi1[ny1][nx1]=0
        if coin2_moved:
            board[ny2][nx2],board[coin2[1]][coin2[0]]=board[coin2[1]][coin2[0]],board[ny2][nx2]
            vi2[ny2][nx2]=0
            
            
dfs(coins[0],coins[1],0)
        
        
print(ans if ans!=11 else -1)

코드가 굉장히 보기싫게 생겼네요..

간단히 설명하자면 2개의 코인 위치를 보내주고 상하좌우 한 방향을 정해서 두개 다 옮겨주었습니다.

이때 배열 밖으로 벗어나게 되면 떨어진 것의 개수를 셀 변수 fallen의 값을 +1해주었습니다. 매번 움직일 때마다 초기화시켜주므로 fallen은 0,1,2 셋 중 하나의 값을 가지게 되어있습니다.

2인 경우 하나만 떨어져야 하는데 두 개 떨어졌으므로 continue

1개만 떨어졌으면 그것이 정답이므로 기존의 정답과 비교해서 작은 값을 정답에 저장해주었습니다. 그리고 하나만 떨어졌다면 남은 하나가지고 탐색을 이어나갈 필요가 없으므로 마찬가지로 continue 시켜주었습니다.

만약 코인을 옮긴 위치가 같아진다면 2개가 겹치게 되고 이 상황에서 뭘 해도 하나만 떨어트릴수는 없으므로 continue 시켜주었습니다.

만약 이동한 코인의 위치가 벽인 경우에는 좌표에 이동하기 이전의 값을 넣어주었습니다.

만약 이동한 코인의 위치가 '.'인 경우에는 기존 코인의 위치와 바꿔주고 코인이 움직였음을 알려줄 변수 coin_moved를 이용해 어떤 코인이 움직였는지를 확인해주었습니다. 백트래킹을 할 때 만약 어떤 코인은 움직이지 않았다면 그 코인을 이동하기 이전의 값으로 바꿀 수는 없고, 어떤 코인도 움직이지 않았다면 이동을 안 한 것이나 다름없기 때문에 아무일도 없도록 코드를 짜 주었습니다.

짜고 보니 엄청 더럽고 시간도 비효율적으로 쓴 느낌이네요.. 최소 횟수다 보니 오히려 bfs로 푸는 쪽이 더 편했을 것이란 생각이 드네요