[Python] 백준 3055. 탈출

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

3055번: 탈출

BFS 문제.

 

'고슴도치 S가 먼저 이동하고,  고슴도치가 이미 이동한 공간이라 해도 물이 해당 공간을 잠식하도록' 코드를 구성했다.

고슴도치가 먼저 이동해서 목적지인 D에 도착하기만 하면 된다.

 

 

 

	import sys
	from collections import deque
	height, width = map(int, sys.stdin.readline().split())
	maps = []
	waters = []
	for y in range(height):
	arr = sys.stdin.readline()
	for x in range(len(arr)):
	if arr[x] == 'S':
	# 시작 지점
	start = [(y, x)]
	elif arr[x] == "D":
	end = (y, x)
	elif arr[x] == '*':
	# 물 시작지점
	waters.append((y,x))
	maps.append(list(arr))
	def bfs(start, maps):
	dirs = [(1,0),(-1,0),(0,1),(0,-1)]
	queue = deque()
	queue.extend(start)
	# 시간별 다음 이동경로를 반환하도록.
	nexts = []
	while queue:
	y, x = queue.popleft()
	for dy, dx in dirs:
	ny, nx = y + dy, x + dx
	if 0 <= ny < height and 0 <= nx < width:
	# 물로 bfs를 돌 때. 고슴도치가 도착할 수 있는 지점이어도 물로 바꿔준다.
	if (maps[ny][nx] == "." or maps[ny][nx] == "S") and maps[y][x] == "*":
	maps[ny][nx] = "*"
	nexts.append((ny, nx))
	# 고슴도치가 사방으로 전진할 때.
	elif maps[ny][nx] == "." and maps[y][x] == "S":
	maps[ny][nx] = "S"
	nexts.append((ny, nx))
	# 목적지에 도착했을 때.
	elif maps[ny][nx] == 'D' and maps[y][x] == 'S':
	return True
	return nexts
	time = 0
	while True:
	time += 1
	# 고슴도치의 이동경로 먼저 계산
	start = bfs(start, maps)
	# 물의 이동경로 계산
	waters = bfs(waters, maps)
	# 이미 D까지 도착했을 경우
	if start == True:
	print(time)
	break
	# 고슴도치가 갈 수 있는 경로가 없는 경우
	elif start == []:
	print("KAKTUS")
	break
	# waters로 한번 돌고 나면,
	# 원래 고슴도치가 있던 공간인데 물이 차서 더 이상 쓸 수 없는 지점이 있을 수 있다.
	temp = []
	for y, x in start:
	if maps[y][x] == 'S':
	temp.append((y,x))
	start = temp

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