(Python) 백준 14503. 로봇 청소기

최권민·2023년 3월 9일
0

알고리즘 풀이

목록 보기
7/13
post-thumbnail

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은
N×MN \times M 크기의 직사각형으로 나타낼 수 있으며,
1×11 \times 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표
(r,c)(r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가
(0,0)(0, 0), 가장 남쪽 줄의 가장 동쪽 칸의 좌표가
(N1,M1)(N-1, M-1)이다. 즉, 좌표
(r,c)(r, c)는 북쪽에서
(r+1)(r+1)번째에 있는 줄의 서쪽에서
(c+1)(c+1)번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

  1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
  2. 현재 칸의 주변 44칸 중 청소되지 않은 빈 칸이 없는 경우,
    1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
    2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
  3. 현재 칸의 주변 44칸 중 청소되지 않은 빈 칸이 있는 경우,
    1. 반시계 방향으로 9090^\circ 회전한다.
    2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
    3. 1번으로 돌아간다.
    상세보기

  • 정직한 시뮬레이션 구현 문제
  • 문제에서 꼼꼼하게 조건을 설명해주기 때문에, 해당 조건에 맞게 구현하면 해결할 수 있다.
  • 문제 자체에서 외곽에 패딩을 주기 때문에 범위를 벗어나는 지 확인하는 로직이 없어져서, 코드를 쉽게 작성할 수 있다.
  • 분기 자체도 많은 편이 아니라서, 어렵지 않은 편
  • 델타를 효율적으로 쓸 수 있다면 쉬운 문제
from sys import stdin; input=stdin.readline

N, M = map(int,input().split()) # 가로, 세로 받아오기

sx, sy, d = map(int,input().split()) # x좌표, y좌표, 방향
field = [list(map(int,input().split())) for _ in range(N)]

# 문제에서 제시한 방향대로 북 - 동 - 남 - 서
dx = [-1,0,1,0]
dy = [0,1,0,-1]

# 청소한 칸을 세는 변수
cnt = 0

while True:
	# 현재 칸이 청소되지 않았으면 청소하고, 값을 -1로 변경
    if field[sx][sy] == 0:
        field[sx][sy] = -1
        cnt += 1
    
    # 2번 상황일 경우
    if field[sx-1][sy] != 0 and field[sx+1][sy] != 0 and field[sx][sy+1] != 0 and field[sx][sy-1] != 0:
    	# 2-2. 후진할 수 없는 경우 break
        if field[sx + dx[(d+2)%4]][sy + dy[(d+2)%4]] == 1:
            break
        # 후진할 수 있는 경우 한 칸 후진
        else:
            sx = sx + dx[(d+2)%4]
            sy = sy + dy[(d+2)%4]
            continue
    # 3번 상황일 경우
    else:
    	# 반시계방향이므로 +3
        d = (d+3)%4
        if field[sx+dx[d]][sy+dy[d]] == 0:
            sx = sx+dx[d]
            sy = sy+dy[d]
            continue

print(cnt)
profile
하나의 궤적을 따라서

0개의 댓글