[백준 BOJ / Python] 14503번 로봇 청소기

문제

로봇 청소기의 위치와 방향 정보, 방의 상태 정보가 주어졌을 때, 작동을 멈출 때까지 로봇 청소기가 청소하는 영역의 개수를 구하는 문제이다.

방은 n*m 크기이며, 가장 북서쪽 칸의 좌표가 (0,0), 남동쪽 칸의 좌표는 (n-1, m-1)이다.

(i, j)가 0인 경우 청소되지 않은 칸이며, 1인 경우는 벽을 의미한다.

로봇청소기의 작동법은 다음과 같다.

1. 현재 칸이 청소가 안되어 있다면 청소한다.
2. 주변 4칸 모두 깨끗한 경우,
   • 바라보는 방향을 유지한 채 한 칸 후진하고 1번으로 돌아간다.
   • 만약 뒤쪽이 벽이라면 작동을 멈춘다.
3. 주변 4칸 중 청소되지 않은 칸이 있는 경우,
   • 반시계 방향으로 90도 회전한다.
   • 바라보는 방향을 기준으로 앞쪽이 청소되지 않은 칸이라면 앞으로 한 칸 이동한다.
   • 1번으로 돌아간다.

풀이

• 1번을 반복한다는 것은 루프를 이룬다고 볼 수 있다.
• 루프 안에서 3번에 해당되는 경우를 먼저 실행한다. 3번을 통해 2번 여부를 확인할 수 있기 때문이다.
• 반시계 방향으로 회전하면서 청소가 되어 있지 않은 빈칸을 탐색한다.
• 찾았다면 이동하여 청소 횟수를 늘려준다.
• 찾지 못했다면 2번에 해당된다고 볼 수 있다.
• 이때 뒤쪽이 벽이라면 작동을 멈추고 청소한 개수를 출력한다.
• 이동 가능하다면 후진으로 이동하고 청소 횟수를 늘려준다.
  • <주의> 후진은 현재 방향을 바꾸지 않고 이동만 하는 것이다.

알고리즘

1. 기본 정보를 받는다. 현재 바라보는 방향은 문제에서 북동남서로 정의되었기 때문에 dx, dy를 해당 방향으로 정렬한다.
2. (1번) while 반복문을 통해 매번 해당 칸이 청소 안 한 칸이면 청소하고 청소 횟수(cnt)를 1 증가시킨다.
3. (3번) 해당 칸에서 반시계 방향으로 회전하면서 청소 안한 빈칸을 탐색한다.
   • dx, dy가 시계방향으로 정렬되어 있음으로 반시계 방향으로 회전하려면 현재 방향(d)에 -1을 하면 된다.
4. 청소 안 한 칸이 있다면 해당 위치로 이동하고 (x, y = nx, ny) break를 통해 1번을 반복한다.
5. 만약 청소 안한 칸이 없다면 break 되지 않기 때문에 else 조건으로 이동한다.
6. (2번) 후진을 하고 만약 벽이라면 작동을 멈춘다.
   • 방향을 유지하며 후진을 해야 하므로 현재 방향(d)을 바꾸기보단 -1을 곱함으로써 방향을 180도 바꿀 수 있다.
   • x = x + dx [d] * (-1)
   • 후진 이동한 곳이 벽(1)이라면 작동을 멈춘다. (본 문제에서는 이동할 수 없는 경우는 안 나온다)
   • 작동을 멈추는 경우엔 청소 횟수를 출력한다.

Python 코드

n, m = map(int, input().split())
r, c, d = map(int, input().split())
area = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


# 본 문제에서는 없어도 통과되지만, 범위 안에서 이동하는지 확인하기 위해 필요함
def in_range(x, y):
    return 0 <= x < n and 0 <= y < m


def cleaner(x, y, d):
    cnt = 0
    while True:
        # 1번 청소하고 청소 횟수 1 증가
        if area[x][y] == 0:
            area[x][y] = -1 # 청소함
            cnt += 1

        # 3번 반시계 방향으로 회전하며 청소하지 않은 칸 탐색
        for _ in range(4):
            d = (d - 1) % 4
            nx, ny = x + dx[d], y + dy[d]
            if in_range(nx, ny) and area[nx][ny] == 0:  # 청소 안한 칸으로 이동
                x, y = nx, ny
                break # 이동했으면 다시 1번으로

        else:
            # 2번 4칸다 깨끗하다면 후진하거나 멈춤
            x, y = x + dx[d] * (-1), y + dy[d] * (-1) # 후진
            if in_range(x, y) and area[x][y] == 1 or not in_range(x,y):  # 벽이라면 작동 멈춤
                print(cnt)
                return

cleaner(r, c, d)

 

문제출처

14503번: 로봇 청소기