[백 준/구현] 13460: 구슬 탈출2

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

13460번: 구슬 탈출 2

핵심 아이디어

• 시뮬레이션 + BFS 탐색 알고리즘

문제 해결 과정

전형적인 구현, 시뮬레이션 문제이다. 최소 칸의 개수를 구하기 위해 bfs 탐색 알고리즘을 수행한다. 빨간 구슬과 파란 구슬을 동시에 같은 칸에 있을 수 없는 로직을 ("더 많이 이동한 구슬이 더 늦게 이동한 구슬이므로 늦게 이동한 구슬을 한 칸 뒤로 이동" ) 생각해내지 못해서 어려웠다. 문제를 풀고나니 엄청 어려운 문제는 아닌거 같지만 문제에서 주어진 조건을 구현하는 것이 어려워 구현문제를 더욱 많이 연습해야함을 느꼈다. 

1. 그래프를 입력받을 때 빨간 구슬의 위치와 파란 구슬의 위치를 각각 rx, ry, bx, by로 입력받는다.

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

# 맵의 크기 입력받기
n, m = map(int, input().split())
# graph 정의하고 빨간 구슬의 위치와 파란구슬의 위치를 지정한다.
graph = []
for i in range(n):
	graph.append(list(input()))
    	for j in range(m):
        	if graph[i][j] == 'R' # 빨간 구슬
            	rx, ry = i, j
            elif graph[i][j] == 'B': # 파란 구슬
            	bx, by = i,j

2. 구슬 이동을 위한 방향 정의하기

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

3. BFS 탐색 알고리즘 정의하기

def bfs(rx, ry, bx, by):
	# 큐 구현을 위해 덱 라이브러리 사용
    q = deque()
    q.append((rx, ry, bx, by))
    # 방문 여부 판단하기 위한 리스트
    visited = []
    visited.append((rx, ry, bx, by))
    count = 0 # 이동 횟수 카운트 변수
    while q: # 큐가 빌 때까지 반복
    	for _ in range(len(q)):
        	rx, ry, bx, ny = q.popleft()
            # 만약 움직인 횟수가 10회 초과하면 -1 출력
            if count > 10:
            	print(-1)
                return
            # 만약 빨간 공이 홀에 들어간다면 count 출력
            if graph[rx][ry] == 'O':
            	print(count)
                return
            # 4가지 방향 확인하기
            # 파란 구슬과 빨간 구슬은 동시에 이동한다.
            for i in range(4):
            	nrx, nry = rx, ry
                #  기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지
                while True:
                	nrx += dx[i]
                    nry += dy[i]
                    # 만약 다음 칸이 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
                    if graph[nrx][nry] == '#':
                    	nrx -= dx[i]
                        nry -= dy[i]
                    	break
                     # 만약 다음 위치가 구멍이라면
                     if graph[nrx][nry] == 'O':
                     	break
                 nbx, nby = bx, by # 파란 구슬 이동
                 while True:
                 	nbx += dx[i]
                    nby += dy[i]
                    # 만약 다음 칸이 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
                    if graph[nbx][nby] == '#':
                    	nbx -= dx[i]
                        nby -= dy[i]
                        break
                     # 만약 다음 위치가 구멍이라면
                     if graph[nbx][nby] == 'O':
                     	break
                  # 파란 구슬이 먼저 구멍에 들어가거나 동시에 들어가면 안된다. 따라서 무시
                  if graph[nbx][nby] == 'O':
                  	continue
                  # 두 구슬의 다음 위치가 같다면, 조건에 부합하지 않아서 더 늦게 온 친구를 뒤로 보낸다.
                  if nrx == nbx and nry == nby:
                  	if abs(nrx - rx) + abs(nry - ry) > abs(nbx - bx) + abs(nby - by):
                    	nrx -= dx[i]
                        nry -= dy[i]
                    else:
                    	nbx -= dx[i]
                        nby -= dy[i]
                   # 방문해본적이 없는 위치라면 새로 큐에 추가 후 방문처리
                   if (nrx, nry, nbx, nby) not in visited:
                       q.append((nrx, nry, nbx, nby))
                       visited.append((nrx, nry, nbx, nby))
		count += 1
	print(-1) # 10회가 초과하지 않았지만 10회 내에도 구멍에 들어가지 못하는 경우

4. 함수 수행

bfs(rx, ry, bx, by)