[백준] 로봇 청소기

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

14503번: 로봇 청소기

구현 문제입니다.

 

문제부터 간단하게 요약하면,

로봇 청소기가 아래의 규칙대로 움직일 때, 

1. 현재 위치를 청소한다. 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.     2-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.     2-2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.     2-3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.     2-4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

청소하는 칸의 갯수를 출력해야 하는 문제입니다. (문제 조건이 더 있으므로, 실제로 위의 링크로 문제를 읽어보는 것을 추천합니다.)

 

<Solution>

이 문제처럼 step을 주는 문제들의 경우, 따로 특별한 알고리즘을 떠올릴 필요 없이 그대로 순서대로 구현을 하면 됩니다. 

 

실제 구현은 아래와 같습니다. (각각의 step별로 주석을 달아두었으니 위치별로 확인해 보면 될 것 같습니다.)

import sys

N, M = list(map(int,sys.stdin.readline().rstrip().split()))
r, c, d = list(map(int,sys.stdin.readline().rstrip().split()))

graph = []

for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

move_r = [-1, 0, 1, 0] # up right down left
move_c = [0, 1, 0, -1]

count = 0

while(1):

    endflag = 0
    # step 1
    if graph[r][c] == 0:
        graph[r][c] = 2
        count+=1

    # step 2
    # search left directions
    for i in range(1,5):
        new_d = (d-i) % 4
        # step 2-1, 2-2
        new_r = r + move_r[new_d]
        new_c = c + move_c[new_d]
        if graph[new_r][new_c] == 0:
            d, r, c = new_d, new_r, new_c
            endflag = 1
            break
    if endflag == 1:
        continue

    # step 2-3
    back_direction = (d-2) % 4
    # check back move is valid
    new_r = r + move_r[back_direction]
    new_c = c + move_c[back_direction]
    if graph[new_r][new_c] != 1:
        r, c = new_r, new_c
        continue
    
    # step 2-4
    break
print(count)