[BOJ] 14503 - 로봇청소기
문제 링크
문제 설명
N*M크기의 방을 로봇청소기가 청소하려고 한다. 방의 각 칸은 빈칸(0)과 벽(1)으로 나뉜다. 청소기는 북0 동1 남2 서3 중 한 방향을 바라보고 북쪽으로부터 r칸, 서쪽으로부터 c칸 떨어진 (r,c) 좌표에 위치한다. 동작은
- 현재 칸 청소
- 왼쪽부터 차례로 탐색
2.1 왼쪽칸이 아직 청소 안한 빈칸이면 -> 회전 후 한칸 전진 -> 1로
2.2 벽이거나 이미 청소한 칸이면 -> 회전 -> 2로
2.3 네방향 다 벽이거나 이미 청소한 칸이면 -> 방향은 유지하고 한칸 뒤로 후진 -> 2로
2.4 네방향 다 벽 또는 이미 청소한 칸이고 뒤쪽 방향도 벽이면 -> 종료
청소기는 벽을 통과할 수 없고, 한칸당 청소는 1번만 할때 청소기가 청소할 수 있는 칸의 개수는?
문제 풀이
주어진 그대로 구현하면 되는 문제다!
import sys
input = sys.stdin.readline
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
N, M = map(int, input().split())
x, y, dir = map(int, input().split())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
def in_range(x, y):
if x in range(N) and y in range(M):
return True
return False
answer = 0
while 1:
#1. clean
if board[x][y] == 0:
board[x][y] = 2
answer += 1
clean_flag = 0
#2. check from left
for i in range(4):
next_dir = (dir+3)%4
nx, ny = x+dx[next_dir], y+dy[next_dir]
if in_range(nx, ny) and board[nx][ny] == 0:
#2-1. in range and has not been cleaned
dir = next_dir
x, y = nx, ny
clean_flag = 1
break
else:
#2-2. already cleaned
dir = next_dir
if clean_flag == 1:
continue
else:
behind = (dir+2)%4
bx, by = x+dx[behind], y+dy[behind]
if board[bx][by] == 1:
#2-4. if all 4 spaces are cleaned and behind is a wall
break
else:
#2-3. if all 4 spaces are cleaned and behind is not a wall
x, y = bx, by
print(answer)
^_^
Author And Source
이 문제에 관하여([BOJ] 14503 - 로봇청소기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@woo0_hooo/BOJ-14503-로봇청소기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)