[모의 SW 역량테스트] 탈주범 검거

SWEA 문제 모음: https://swexpertacademy.com/main/code/problem/problemList.do

SW Expert Academy

일반적인 BFS에서 주어진 시간동안 얼마나 이동할 수 있는지 보면 되는데, 해당 방향으로 파이프가 연결되었다고 해서 무조건 이동할 수 있는 것이 아니다. 이동하고자 하는 칸에 파이프가 있는지, 있다면 원래 위치와 연결되어 있는지 확인하고 이동해야 한다.(line 39~40) 현재 시간 이전에 이미 방문했던 칸이면 다시 볼 필요가 없으니 큐에 넣어주지 말자.

 

예제 1을 보면 매 시간마다 이동하지 않아도 되는 것 같은데, 어차피 최대 이동할 수 있는 경우를 체크해야 하니 무시하자.

 

원래는 line 30에서 visited[cur_r][cur_c] = True로 바꿔주면서 지금까지 이동한 곳 개수를 +1 해주는 방식으로 짰는데, 2번째 예제에서 실제 정답과 다르게 저장이 되는 문제가 있었다. visited 내 True 개수를 출력하도록 하니 되던데, 뭐가 문제지...?

 

 

	from collections import deque
	def check(n):
	if n == 1: return 0
	elif n == 0: return 1
	elif n == 2: return 3
	elif n == 3: return 2
	t = int(input())
	# 상 하 좌 우 = [1, 1, 1, 1]
	pipe = [[], [1, 1, 1, 1], [1, 1, 0, 0], [0, 0, 1, 1], [1, 0, 0, 1], [0, 1, 0, 1], [0, 1, 1, 0], [1, 0, 1, 0]]
	move = [[-1,0], [1,0], [0,-1], [0,1]] # 상 하 좌 우
	for t_idx in range(1, t+1):
	n, m, r, c, l = map(int, input().split())
	lst = [list(map(int, input().split())) for _ in range(n)]
	field = [[0]*m for _ in range(n)]
	visited = [[0]*m for _ in range(n)]
	for i in range(n):
	for j in range(m):
	field[i][j] = pipe[lst[i][j]]
	queue = deque([[r,c,1]])
	while queue:
	cur_r, cur_c, cur_t = queue.popleft()
	if cur_t <= l: # 이동 가능한 시간
	visited[cur_r][cur_c] = True
	if cur_t == l: # 더 이상 이동 불가능
	continue
	for i in range(4):
	if field[cur_r][cur_c][i]: # 해당 방향으로 파이프가 있으면
	next_r, next_c = cur_r + move[i][0], cur_c + move[i][1]
	if 0 <= next_r < n and 0 <= next_c < m and field[next_r][next_c]: #지도 내 존재, 파이프가 있다면
	if field[next_r][next_c][check(i)] and not visited[next_r][next_c]: # 이동해야 하는 곳도 원래 위치로 파이프가 있고 방문 안 했다면
	queue.append([next_r, next_c, cur_t+1])
	print("#{} {}".format(t_idx, sum([sum(x) for x in visited])))

view raw 탈주범 검거.py hosted with ❤ by GitHub