14503번. 로봇 청소기

http://boj.kr/14503 

 

 

정말 꼼꼼하게 문제 조건을 살펴야 하는구나...라고 느낀 문제.

그리고 코딩 전 직접 시뮬레이션을 해보는 것이 중요하다.

 

import sys
from copy import deepcopy


def get_back_direction(direct):
    if direct < 2:
        return direct + 2
    else:
        return direct - 2


def get_left_direction(direct):
    if direct == 0:
        return 3
    else:
        return direct - 1


def start(row, col, di):
    visited = deepcopy(board)
    visited[row][col] = 1
    clean_area = 1  # 청소한 영역
    turn_times = 0   # 4방향을 봤는지 카운트해줌
    next_di = di  # 다음 방향

    while True:
        while turn_times < 4: 
            next_di = get_left_direction(next_di)  # 왼쪽으로 한번 돌려봐라
            turn_times += 1
            if visited[row+x[next_di]][col+y[next_di]] == 0:  # 갈 수 있으면 가고
                di = next_di
                row += x[di]
                col += y[di]
                visited[row][col] = 1
                clean_area += 1
                turn_times = 0

            # 왼쪽으로 돌렸는데 갈 수 없으면 실제로 방향을 변경하는 것은 아니고
            # while로 돌아가 다시 왼쪽으로 돌려보는 것

        back_di = get_back_direction(di)  # 4방향 모두 봤는데 갈 수 없으면 후진 시도

        # 후진할 수 있으면(=벽이 아니면) 방향은 유지하고 한칸 빽->while로 돌아가서 거기서 다시 왼쪽으로 돌려보기 시작
        if board[row+x[back_di]][col+y[back_di]] != 1:
            row += x[back_di]
            col += y[back_di]
            turn_times = 0

        # 프로그램 종료
        else:
            break

    return clean_area


if __name__ == '__main__':
    input = sys.stdin.readline
    N, M = map(int, input().split())
    r, c, d = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    x = [-1, 0, 1, 0]
    y = [0, 1, 0, -1]
    print(start(r, c, d))

 

왼쪽으로 돌려볼 때 next_di 를 사용하는 이유.

di를 왼쪽으로 돌릴 때마다 바로바로 업데이트하면 4방향 모두 봤는데 막혀있을 때,

후진 전에다시 원래 방향으로 돌아와야 하기 때문이다. 

 

board와 로봇 청소기가 사용한 visited는 따로 사용했다. 

로봇청소기가 후진하려고 할 때 벽일 때는 바로 프로그램이 종료되어야 하지만 

청소한 영역(visited = 1)일 때는 후진 가능하기 때문이다...

다시 생각해보니 청소 영역을 2로 체크해도 됐었을 듯.