[백준] 13459 구슬 탈출 python 풀이

문제

• 난이도: 골드1
• 알고리즘 분류: 구현, 그래프, 시뮬레이션, 너비 우선 탐색
• 요약: 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 1을 없으면 0을 출력하기

풀이

빨간/파란 구슬의 x, y 좌표를 queue에 담아서 진행

1.한 방향으로 이동중인 구슬이 멈추는 조건

• 다음 위치가 벽이거나
• 현재 위치가 구멍일 때

2. 빨간/파란 구슬이 끝까지 이동했을 때의 위치와 움직인 횟수 확인

• 이동한 빨간/파란 구슬 위치가 같을 경우
  움직인 횟수 비교 후, 이동거리가 더 많은 구슬이 뒤로 한칸 이동

코드

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())

board = []
for _ in range(n):
	board.append(list(input().rstrip()))

for r in range(n):
	for c in range(m):
		if board[r][c] == 'R':
			rx, ry = r, c
		if board[r][c] == 'B':
			bx, by = r, c

#     상  하  좌  우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def move(x, y, dx, dy):
	count = 0

	while True:
		if board[x+dx][y+dy] == '#' or board[x][y] == 'O':
			return x, y, count

		x += dx
		y += dy
		count += 1

def bfs(rx, ry, bx, by):
	queue = deque()
	queue.append([rx, ry, bx, by, 0])

	visited[rx][ry][bx][by] = True

	while queue:
		rx, ry, bx, by, count = queue.popleft()

		for i in range(4):
			if count > 10:
				print(0)
				return
			
			if board[rx][ry] == 'O':
				print(1)
				return
			
			for i in range(4):
				nrx, nry, rcount = move(rx, ry, dx[i], dy[i])
				nbx, nby, bcount = move(bx, by, dx[i], dy[i])

				if board[nbx][nby] == 'O':
					continue
				
				if nrx == nbx and nry == nby:
					if rcount > bcount:
						nrx -= dx[i]
						nry -= dy[i]
					else:
						nbx -= dx[i]
						nby -= dy[i]
				
				if visited[nrx][nry][nbx][nby] == False:
					visited[nrx][nry][nbx][nby] = True
					queue.append([nrx, nry, nbx, nby, count + 1])
	
	print(0)

visited = [[[[False] * m for _ in range(n)] for _ in range(m)] for _ in range(n)]
bfs(rx, ry, bx, by)