13460 - 구슬 탈출 2

 

문제

13460번: 구슬 탈출 2 (acmicpc.net)

13460번: 구슬 탈출 2

풀이 1

다음 문제와 상당히 유사하다는 것을 알 수 있다.

블록 이동하기 (lv3) (tistory.com)

블록 이동하기 (lv3)

본 문제도 위 블럭 이동하기 문제와 유사하게 두 좌표가 하나로 묶여 이동한다. 블럭 이동하기 문제에서는 로봇의 움직임에 따라 이동 가능 여부를 따지고, 집합 안의 좌표 튜플이 목적지 좌표와 같은지 확인했다면, 본 문제에서는 벽에 부딪힐때까지 한 방향으로 움직이다가, 파란공이 구멍으로 들어가버리면 다시 원위치를 시키고, 빨간공이 구멍으로 들어가도 해당 방향으로 끝까지 진행했을 때 파란공이 남아있는지를 확인해야 한다. 어떤 위치에 도달할 때까지 일정한 비용으로 움직인다는 점에서 BFS 최단거리 문제로 유형이 좁혀지고, 다만 조건에 두개의 좌표를 동시에 고려해야 하므로 board 값에 직접 거리를 입력하는 방식이 아닌 두 좌표를 하나의 튜플로 묶어 방문 여부를 따져야 하며 정답이 되는 경우는 한 방향으로 끝까지 이동했을때 빨간 공만 사라지고 파란공은 남아있는 경우이므로 빨간공, 파란공 각각의 존재여부를 큐에 함께 넣어줘야 한다.

from collections import deque

n,m = map(int,input().split())
board = []
for _ in range(n):
    board.append([elem for elem in input()])

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]
rb = [(),()]
for row in range(1,n-1):
    for col in range(1,m-1):
        if board[row][col] == 'R':
            rb[0] = (row,col)
        if board[row][col] == 'B':
            rb[1] = (row,col)

answer = 0
q = deque()
visited = set()
q.append((0,rb,True,True))
visited.add(tuple(rb))

while q:
    cnt,((rR,rC),(bR,bC)),red,blue = q.popleft()
    if cnt > 10:
        break
    if not red and blue:
        answer = cnt
        break
    for i in range(4):
        _red,_blue = red,blue
        nrR,nrC = rR,rC
        nbR,nbC = bR,bC
        temp = ()
        while not (board[nrR+dRow[i]][nrC+dCol[i]] == '#' and board[nbR+dRow[i]][nbC+dCol[i]] == '#'):
            temp = ((nrR,nrC),(nbR,nbC))
            if not board[nrR+dRow[i]][nrC+dCol[i]] == '#':
                if board[nrR+dRow[i]][nrC+dCol[i]] == 'O':
                    _red = False
                nrR += dRow[i]
                nrC += dCol[i]
            if not board[nbR+dRow[i]][nbC+dCol[i]] == '#':
                if board[nbR+dRow[i]][nbC+dCol[i]] == 'O':
                    nrR, nrC = rR, rC
                    nbR, nbC = bR, bC
                    _blue = False
                    break
                nbR += dRow[i]
                nbC += dCol[i]
        if _red and nrR == nbR and nrC == nbC:
            (nrR,nrC), (nbR,nbC) = temp
        if not ((nrR,nrC),(nbR,nbC)) in visited:
            visited.add(((nrR,nrC),(nbR,nbC)))
            q.append((cnt+1,((nrR,nrC),(nbR,nbC)),_red,_blue))

print(answer) if answer > 0 else print(-1)

풀이 2

빨간 구슬이 구멍 위치에 도달할 때 까지 최소 몇번의 기울이기 동작이 필요한지 구해야한다는 점에서, BFS로 접근 가능하다는 것을 알 수 있다. 이번에는 BFS가 아닌 DFS와 백트래킹을 이용해 풀이했고, 추가적인 풀이를 남기는 것은 "기울이기" 동작에 대한 접근법을 기억하기 위함이다.

보드를 기울이면 두 구슬은 함께 움직이며, 서로 같은칸에 존재할 수 없다. 이점을 유의해야 하는데, 빨강 구슬과 파랑 구슬은 다음칸에 벽이 있지 않는 한 동시에 움직일 수 있고, 둘 중 하나가 구멍에 빠지거나 벽을 만나면 나머지 구슬 하나만 움직이게 된다. 이를 구현하는게 문제의 핵심이고, 나머지는 보드를 이리저리 기울여보다가 빨강 구슬이 구멍에 빠지는지 확인하면 된다. 풀이 1 처럼 최소거리를 직접 찾는 방식이 아닌, 보드를 10번까지 직접 이리저리 기울여보며 answer를 갱신하는 백트래킹 방식으로 풀이했다. 실행시간은 약 4~5배 걸렸다.

N,M = map(int,input().split())
board = [['' for col in range(M)] for row in range(N)]
red,blue = [],[]
goal = []
for row in range(N):
    for col,v in enumerate(input()):
        board[row][col] = v
        if v == 'R':
            red = [row,col]
        if v == 'B':
            blue = [row,col]
        if v == 'O':
            goal = [row,col]

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]
INF = int(1e9)


def get_answer(cnt):
    global red,blue,answer
    if cnt > 10:
        return
    if red == goal:
        answer = min(answer,cnt)
        return
    rR,rC = red
    bR,bC = blue
    for i in range(4):
    	# 빨강, 파랑 구슬 존재 유무
        r_flag,b_flag = True,True
        # 두 구슬 모두 다음위치가 벽이 아닐때까지
        while board[red[0]+dRow[i]][red[1]+dCol[i]] != '#' and board[blue[0]+dRow[i]][blue[1]+dCol[i]] != '#':
            red[0],red[1] = red[0]+dRow[i],red[1]+dCol[i]
            blue[0],blue[1] = blue[0]+dRow[i],blue[1]+dCol[i]
            if red == goal:
                r_flag = False
                break
            if blue == goal:
                b_flag = False
                break
        # 빨강 구슬만 남아서 움직임
        while r_flag and board[red[0]+dRow[i]][red[1]+dCol[i]] != '#' and\
                not (b_flag and [red[0]+dRow[i],red[1]+dCol[i]] == blue):
            red[0], red[1] = red[0] + dRow[i], red[1] + dCol[i]
            if red == goal:
                r_flag = False
        # 파랑 구슬만 남아서 움직임
        while b_flag and board[blue[0] + dRow[i]][blue[1] + dCol[i]] != '#' and\
                not (r_flag and [blue[0] + dRow[i],blue[1] + dCol[i]] == red):
            blue[0], blue[1] = blue[0] + dRow[i], blue[1] + dCol[i]
            if blue == goal:
                b_flag = False
        # 파랑 구슬이 남아있고, 구슬이 이동했다면
        if b_flag and not (red == [rR,rC] and blue == [bR,bC]):
            get_answer(cnt+1)
        red,blue = [rR,rC],[bR,bC]


answer = INF
get_answer(0)
if answer > 10:
    print(-1)
else:
    print(answer)