[백준] 14503번 / 로봇청소기 / Python(파이썬)

14503번: 로봇 청소기 (acmicpc.net)

[14503번: 로봇 청소기

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽

www.acmicpc.net](https://www.acmicpc.net/problem/14503)

문제

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

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

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 없는 경우,

    1) 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.

    2) 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 $4$칸 중 청소되지 않은 빈 칸이 있는 경우,

    1) 반시계 방향으로 $90^\circ$ 회전한다.
    2) 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.

    3) 1번으로 돌아간다.

입력

첫째 줄에 방의 크기 $N$과 $M$이 입력된다.
$(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽, $1$인 경우 동쪽, $2$인 경우 남쪽, $3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 $N$개의 줄에 각 장소의 상태를 나타내는 $N \times M$개의 값이 한 줄에 $M$개씩 입력된다. $i$번째 줄의 $j$번째 값은 칸 $(i, j)$의 상태를 나타내며, 이 값이 $0$인 경우 $(i, j)$가 청소되지 않은 빈 칸이고, $1$인 경우 $(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

풀이

이 문제는 4방향으로 이동하면서 칸을 조사하는 문제이기 때문에 dx, dy를 리스트로 설정하여 문제를 푸는 것이 효과적이다.

문제에서 주어진 대로 차례차례 구현하면 어려울 것은 없다.

 

1. 주변 4칸이 청소가 된 경우  ->  | 후진

                                                     | 후진 불가능하면 작동 멈춤

 

2. 주변 4칸 중 청소되지 않은 칸  -> 반시계 방향으로 90도 회전 후, 앞쪽 칸이 빈칸인 경우 전진 

 

- 방향 전환은 반시계 방향으로 움직이므로 4방향 주변 칸을 조사할 때 반시계 방향으로 조사한다.

- 후진 방향을 선택하기 위해 (d+2) % 4 식을 이용한다. 삼성 기출 문제에서는 방향을 전환하는 문제가 굉장히 많기 때문에 이런건 외워두는게 좋당

- 반시계 방향 회전은 (d+3) % 4를 이용한다. 간단한 문제지만 %4를 하는 이유는 4방향 안에서 자꾸 돌라고.. 

- 큐를 이용한 bfs로 문제를 풀면 간단하게 해결 할 수 있다.

   

코드

 

from collections import deque

# x, y가 좌표 내에 존재하는지 확인
def is_board(x, y):
    if 0 <= x < n and 0 <= y < m:
        return True
    return False

n, m = map(int, input().split())
r, c, d = map(int, input().split())

# 4방향
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

vaccum_map = [list(map(int, input().split())) for _ in range(n)]

def bfs(x, y, d):
    cnt = 0
    queue = deque()
    queue.append((x, y, d))
    # 현재 칸 청소
    vaccum_map[x][y] = 2
    cnt += 1
    while queue:
        x, y, d = queue.popleft()
        temp_d = d
        turn = 0
        for i in range(4):
            nd = (temp_d+3) % 4
            nx = x+dx[nd]
            ny = y+dy[nd]
            temp_d = nd
            if is_board(nx, ny):
                if vaccum_map[nx][ny] == 0:
                    queue.append([nx, ny, nd])
                    vaccum_map[nx][ny] = 2
                    cnt += 1
                    break
                else:
                    turn += 1
        # 주반 4칸에 빈 칸이 없는 경우 후진
        if turn == 4:
            bx = x + dx[(d+2) % 4]
            by = y + dy[(d+2) % 4]
            if vaccum_map[bx][by] == 1:
                return cnt
            queue.append((bx, by, d))
print(bfs(r, c, d))