[Python] 백준 13460. 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

삼성SW역량평가 기출이고, DFS를 활용한 brute force 문제.

 

구슬이 같은 위치에 놓일 때 선후관계를 구분해서 처리하는 게 특징.

같은 위치에 놓였어도, 해당 위치까지 도달하는 데 더 오래 걸린 구슬이 뒤처지는 걸 반영했다.

 

 

	import sys
	import math
	n, m = map(int, sys.stdin.readline().split())
	maps = []
	for y in range(n):
	arr = list(sys.stdin.readline())
	maps.append(arr)
	for x in range(len(arr)):
	if arr[x] == 'R':
	r = (y, x)
	# 맵을 재활용하기 위해 처음 위치값만 저장한 뒤 값을 .로 바꿔준다
	arr[x] = '.'
	if arr[x] == 'B':
	b = (y, x)
	arr[x] = '.'
	mins = math.inf
	def bfs(maps, start_r, start_b, dirs, cnt):
	global mins
	if cnt > 10:
	return
	# 어디로 이동할 건지 direction
	dy, dx = dirs
	# 각 구슬의 y좌표, x좌표
	ry, rx = start_r
	by, bx = start_b
	# 정지하기까지 이동한 횟수. 같은 위치에 있을 때 선후관계를 가리는 용도
	r_cnt, b_cnt = 0, 0
	# 구슬이 빠져나갔는지 여부
	r_out, b_out = False, False
	# 빨간 공
	ny, nx = ry + dy, rx + dx
	while 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
	r_cnt += 1
	# 구슬이 밖으로 빠져나옴
	if maps[ny][nx] == 'O':
	r_out = True
	break
	# 움직일 수 없음
	elif maps[ny][nx] == '#':
	start_r = (ry, rx)
	r_cnt -= 1
	break
	# 이동 가능
	elif maps[ny][nx] == '.':
	ry, rx = ny, nx
	ny, nx = ry + dy, rx + dx
	# 파란 공
	ny, nx = by + dy, bx + dx
	while 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
	b_cnt += 1
	if maps[ny][nx] == 'O':
	b_out = True
	break
	elif maps[ny][nx] == '#':
	start_b = (by, bx)
	b_cnt -= 1
	break
	elif maps[ny][nx] == '.':
	by, bx = ny, nx
	ny, nx = by + dy, bx + dx
	# 두 개가 같은 위치에 겹친 경우
	if start_r == start_b:
	# r이 더 오래 걸렸으면 r을 한 칸 뒤로
	if r_cnt > b_cnt:
	start_r = (ry - dy, rx - dx)
	# b가 더 오래 걸렸으면 b를 한 칸 뒤로
	else:
	start_b = (by - dy, bx - dx)
	# b가 통과한 경우 실패
	if b_out:
	return
	# r만 통과하고 b는 통과하지 못한 경우 성공
	elif r_out and not b_out:
	mins = min(mins, cnt)
	return
	## 둘 다 전혀 움직이지 않은 경우 실패
	elif r_cnt == b_cnt == 0:
	return
	else:
	bfs(maps, start_r, start_b, (0, 1), cnt + 1)
	bfs(maps, start_r, start_b, (1, 0), cnt + 1)
	bfs(maps, start_r, start_b, (0, -1), cnt + 1)
	bfs(maps, start_r, start_b, (-1, 0), cnt + 1)
	dirs = [(0,1), (0,-1), (1, 0), (-1,0)]
	for head in dirs:
	bfs(maps, r, b, head, 1)
	if mins == math.inf:
	print(-1)
	else:
	print(mins)

view raw [백준] 구슬 탈출 2.py hosted with ❤ by GitHub