[BOJ 16197] 두동전

문제

[BOJ 16197] 두동전

시도1(백트래킹)

코드

주의할 점: dropped가 2인 경우는 다른 방향도 봐야 하므로 return이 아닌 continue 써야함
dropped가 1인 경우는 이미 답이 나왔으므로 더이상 탐색할 필요가 없음. 따라서 return

import sys
input = sys.stdin.readline

N,M = map(int,input().split()) # 1<=세로,가로<=20
board = []
for _ in range(N):
    board.append(list(input().rstrip()))

coins = []
for i in range(N):
    for j in range(M):
        if board[i][j]=='o':
            coins.append((i,j))
        
dx = [0,0,1,-1]
dy = [1,-1,0,0]
    
def back(cnt,coins):
    global answer
    
    # 가지치기
    if cnt>answer or cnt>10:
        return
  
    for dir in range(4):
        dropped = 0
        newcoins = [] # 동전이 떨어지지 않을 경우만 좌표 추가
        for coin in coins:
            x,y = coin
            nx,ny = x+dx[dir],y+dy[dir]
            if nx<0 or nx>=N or ny<0 or ny>=M:
                dropped += 1
                continue
            # 벽이면 좌표 그대로
            if board[nx][ny]=='#':
                newcoins.append((x,y))
            # 벽이 아니면 한칸 이동
            else:
                newcoins.append((nx,ny))
              
        if dropped==2:
            continue # 다른 방향도 봐야하므로 continue
        if dropped==1:
            answer = min(answer,cnt)
            return # 답이 나왔으므로 더이상 볼 필요없음 따라서 continue가 아닌 return
        if dropped==0:
            back(cnt+1,newcoins)
    
answer = 11 
back(1,coins)
if answer==11:
    print(-1)
else:
    print(answer)

문제점

동전이 하나만 떨어지는 경우가 나오기 전까지는 계속 탐색하므로 시간 오래걸림

시도2(BFS)

떨어진 동전의 개수를 dropped로 관리
visited는 두 동전이 모두 보드에 있을때만 기록함

import sys
from collections import deque
input = sys.stdin.readline

N,M = map(int,input().split()) # 1<=세로,가로<=20
board = []
for _ in range(N):
    board.append(list(input().rstrip()))

coins = []
for n in range(N):
    for m in range(M):
        if board[n][m]=='o':
            coins.append((n,m))
   
dx = [0,0,1,-1]
dy = [1,-1,0,0]     

def bfs():
    
    global answer
    q = deque()
    x1,y1 = coins[0]
    x2,y2 = coins[1]
    q.append((x1,y1,x2,y2,1))
    # visited는 dropped==0일때만(두 동전이 모두 보드에 있을때만) 관리함 
    visited = [ [[[False]*M for _ in range(N)] for _ in range(M)] for _ in range(N) ] 
    visited[x1][y1][x2][y2]=True
    while q:
        x1,y1,x2,y2,cnt = q.popleft()
        if cnt>answer or cnt>10: break
        
        for dir in range(4):
            dropped = 0
            nx1,ny1,nx2,ny2 = x1+dx[dir],y1+dy[dir],x2+dx[dir],y2+dy[dir]
          
            # 2. 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 바깥으로 떨어진다.
            if nx1<0 or nx1>=N or ny1<0 or ny1>=M: dropped += 1 
            if nx2<0 or nx2>=N or ny2<0 or ny2>=M: dropped += 1    
            
            if dropped==2:
                continue
            if dropped==1:
                answer = min(answer,cnt)
            if dropped==0: 
                # 1. 동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다.
                if board[nx1][ny1]=='#': nx1,ny1 = x1,y1
                if board[nx2][ny2]=='#': nx2,ny2 = x2,y2
                if not visited[nx1][ny1][nx2][ny2]:
                    visited[nx1][ny1][nx2][ny2]=True
                    q.append((nx1,ny1,nx2,ny2,cnt+1))

answer = 11
bfs()
if answer==11:
    print(-1)
else:
    print(answer)