로봇 청소기
백준 14503
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하기.
- 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
- 로봇 청소기는 다음과 같이 작동한다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
- 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)
- 둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.
- 셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.
- 로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.
입출력
입력 | 출력 |
---|---|
3 3 1 1 0 1 1 1 1 0 1 1 1 1 | 1 |
11 10 7 4 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 | 57 |
접근 방식
:
알게된 점
시뮬레이션 문제는 문제에서 나와있는대로 충실히 구현하면 된다. 특히 이 문제는 한 번에 움직일 수 있는 한 방향이 정해져 있으므로 특별한 알고리즘도 필요하지 않다.
코드
def change(d):
if d==0: return 3
elif d==1: return 0
elif d==2: return 1
elif d==3: return 2
def clean(x, y, d):
# 북동남서
dx = [-1,0,1,0]
dy = [0,1,0,-1]
maps[x][y] = -1 #청소
cnt = 1
while True:
flag = 0
for _ in range(4):
nd = change(d)
nx = x + dx[nd]
ny = y + dy[nd]
d = nd
if 0<=nx<n and 0<=ny<m:
if maps[nx][ny] == 0:
maps[nx][ny] = -1
cnt += 1
x, y = nx, ny #이동
flag += 1
break
#네 방향 모두 청소 or 벽
if flag == 0:
if d==0: nx = x+1
elif d==1: ny = y-1
elif d==2: nx = x-1
elif d==3: ny = y+1
if 0<=nx<n and 0<=ny<m :
if maps[nx][ny] == 1: #뒤도 벽
return cnt
else:
x, y = nx, ny #후진
else:
return cnt
n, m = map(int, input().split())
r, c, d = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(n)]
print(clean(r, c, d))
Author And Source
이 문제에 관하여(로봇 청소기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sezeom/로봇-청소기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)