[Python] 백준 14503. 로봇 청소기

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

14503번: 로봇 청소기

삼성SW역량평가 A형 기출문제로,

엄청 어려운 문제라기보다는 신중하게 생각해서 코드를 짜야 하다보니 시간이 부족했을 법한 문제.

 

예컨대 현재 바라보는 위치가 북쪽(0)인 경우, 북쪽 기준으로 '왼쪽'은 서쪽이고, 2d 리스트에서 서쪽으로 이동하는 좌표는 (0, -1)이다.

(아래 코드의 dirs)

 

이런 식으로 "현재 바라보는 위치 & 해당 위치 기준, 왼쪽으로 이동하는 좌표상의 방법"을 연결해야 하고,

"현재 바라보는 위치 기준, 뒤로 이동하는 좌표상의 방법"도 정의해야 한다.

 

북쪽 기준으로 '뒤'로 이동하기 위해서는 좌표가 남쪽으로 이동해야 하며, 2d 리스트에서 남쪽으로 이동하는 좌표는 (1,0)이다.

(아래 코드의 back)

 

문제에서 정의한 북->서->남->동 은 숫자로 각각 0 -> 3 -> 2 -> 1 에 대응된다.

즉 next head = (head - 1) % 4 형태로 next head를 정의해야 한다.

 

 

	import sys
	from collections import deque
	from copy import deepcopy
	n, m = map(int, sys.stdin.readline().split())
	dirs = [(0,-1), (-1,0), (0,1), (1,0)]
	back = {0:(1, 0), 1:(0,-1), 2:(-1,0),3:(0,1)}
	# a = {0:"북",1:'동',2:'남',3:"서"}
	# 현재 청소기 좌표
	y, x, head = map(int, sys.stdin.readline().split())
	maps = []
	for _ in range(n):
	maps.append(list(map(int, sys.stdin.readline().split())))
	def bfs(start, maps):
	queue = deque()
	queue.append(start)
	# 청소기가 청소한 횟수
	cnt = 0
	while queue:
	y, x, head = queue.popleft()
	if maps[y][x] == 0:
	# 청소하지 않은 곳은 0이고, 벽은 1이기 때문에
	# 둘 모두와 겹치지 않는 2를 '청소 완료한 좌표'로 정의
	maps[y][x] = 2
	cnt += 1
	# 바라보는 곳 기준 왼쪽으로 이동하기 위한 좌표
	dy, dx = dirs[head]
	# 왼쪽으로 이동했을 때의 좌표
	ny, nx = y + dy, x + dx
	# 바라보는 곳 기준, 후진해야 할 때의 좌표
	by, bx = back[head]
	# 더 이상 움직일 수 없는 경우
	cant_move = True
	for ty, tx in dirs:
	# 청소할 곳이 남아있으면, 그곳으로 움직일 수 있음
	if maps[y+ty][x+tx] == 0:
	cant_move = False
	break
	if 0 <= ny < len(maps) and 0 <= nx < len(maps[0]):
	# a조건
	if maps[ny][nx] == 0:
	new_head = (head - 1) % 4
	queue.append((ny, nx, new_head))
	elif cant_move:
	# d조건.
	if maps[y+by][x+bx] == 1:
	break
	else:
	# c조건
	queue.append((y+by, x+bx, head))
	else:
	# 'b조건'
	new_head = (head - 1) % 4
	queue.append((y, x, new_head))
	else:
	# b조건
	new_head = (head - 1) % 4
	queue.append((y, x, new_head))
	return cnt
	print(bfs((y,x,head), maps))

view raw [백준] 로봇 청소기.py hosted with ❤ by GitHub