[백준 14503] 로봇 청소기

 

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

알고리즘 : 구현, 시뮬레이션

난이도 : 골드Ⅴ

 

1. 문제요약

• N * M 크기의 방이 주어진다. 값이 0인 경우 청소되지 않은 빈 칸이고, 1인 경우 벽이 있는 곳이다.
• 로봇청소기는 다음과 같이 동작한다.
  • 현재 칸이 청소되지 않았다면 현재 칸을 청소한다.
  • move1 : 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없다면 바라보는 방향을 유지한 채로 후진이 가능하면 한 칸 후진하고, 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
  • move2 : 주변 4칸 중 청소되지 않은 빈 칸이 있다면 청소되지 않은 빈칸을 마주할때까지 반시계 방향으로 90도씩 회전하고, 청소되지 않은 칸으로 전진한다.
• 입력으로 방의 크기 N, M이 첫째 줄에 주어지고, 둘째줄에 로봇 청소기의 처음 좌표 r, c와 청소기가 바라보는 방향 d가 입력된다. 북, 동, 남, 서를 순서대로 0, 1, 2, 3으로 나타낸다. 셋째줄부터 N개의 줄에 방의 상태를 나타내는 값이 한줄에 M개씩 입력된다.
• 로봇 청소기가 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

2. 구현과정

• 문제에서 요구하는대로 구현하면 된다. 다만 이번 문제는 클래스를 이용해서 풀어보기로 한다.
• RobotSimulation이라는 클래스를 만들고, 클래스의 메서드 사이에서 공유될 파라미터를 초기화해준다.
• 방을 청소하는 메서드 clean(), 현재 칸 기준 주변에 청소되지 않은 빈칸을 탐색하는 check_clean_around(), 청소기가 움직이는 두 경우를 각각 move_case1, move_case2, 마지막으로 이러한 메서드들을 활용한 simulation() 메서드까지 문제를 따라 구현한다.
• 클래스로부터 my_robot이라는 인스턴스를 생성하여 시뮬레이션 메서드로 시뮬레이션하며 파라미터를 업데이트시킨다. 최종적으로 동작이 멈춘 경우에 청소한 칸의 개수를 나타내는 num_cleaned 파라미터를 출력한다.

3. 파이썬 코드

NORTH, EAST, SOUTH, WEST = 0, 1, 2, 3

class RobotSimulation:
    def __init__(self, r, c, direction, place):
        self.r = r
        self.c = c
        self.num_cleaned = 0
        self.direction = direction
        self.move = {NORTH:(-1,0), EAST:(0,1), SOUTH:(1,0), WEST:(0,-1)}
        self.move_back = {NORTH:(1,0), EAST:(0,-1), SOUTH:(-1,0), WEST:(0,1)}
        self.rotate = {NORTH:WEST, EAST:NORTH, SOUTH:EAST, WEST:SOUTH}
        self.place = place
        self.visited = [row[:] for row in place]

    def clean(self):
        if not self.visited[self.r][self.c]:
            self.num_cleaned += 1
            self.visited[self.r][self.c] = True

    def check_clean_around(self):
        for dr, dc in self.move.values():
            nr, nc = self.r + dr, self.c + dc
            if self.place[nr][nc] == 0 and not self.visited[nr][nc]:
                return False
        return True

    def move_case1(self):
        nr = self.r + self.move_back[self.direction][0]
        nc = self.c + self.move_back[self.direction][1]
        if self.place[nr][nc] == 0:
            self.r, self.c = nr, nc
            return False
        else:
            return True

    def move_case2(self):
        for _ in range(4):
            self.direction = self.rotate[self.direction]
            nr, nc = self.r + self.move[self.direction][0], self.c + self.move[self.direction][1]
            if self.place[nr][nc] == 0 and not self.visited[nr][nc]:
                self.r, self.c = nr, nc
                break

    def simulation(self):
        is_end = False
        while not is_end:
            self.clean()
            if self.check_clean_around():
                is_end = self.move_case1()
            else:
                self.move_case2()


if __name__ == "__main__":
    N, M = map(int,input().split())
    r, c, d = map(int,input().split())
    my_place = []
    for _ in range(N):
        my_place.append(list(map(int,input().split())))
    my_robot = RobotSimulation(r, c, d, my_place)
    my_robot.simulation()
    print(my_robot.num_cleaned)