[BOJ] 14503. 로봇 청소기

Jimeaning·2023년 5월 24일

구현 시뮬레이션

코딩테스트

목록 보기

100/143

Python3

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램
https://www.acmicpc.net/problem/14503

키워드

구현
시뮬레이션
그래프 한 방울

문제 풀이

문제 요구사항

청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다.
가장 북쪽 줄의 가장 서쪽 칸의 좌표가 $(0, 0)$ , 가장 남쪽 줄의 가장 동쪽 칸의 좌표가
$(N-1, M-1)$ 이다.
로봇 청소기의 작동 방식

현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
현재 칸의 주변 $4$ 칸 중 청소되지 않은 빈 칸이 없는 경우,
1) 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
2) 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
현재 칸의 주변 $4$ 칸 중 청소되지 않은 빈 칸이 있는 경우,
1) 반시계 방향으로 $90^\circ$ 회전한다.
2) 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
3) 1번으로 돌아간다.

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

변수 및 함수 설명

n, m : 방의 크기 $(3 \le N, M \le 50)$
r, c, d : 로봇 청소기가 있는 칸의 좌표 $(r, c)$ 와 처음에 로봇 청소기가 바라보는 방향 $d$ .
$d$ 가
$0$ 인 경우 북쪽,
$1$ 인 경우 동쪽,
$2$ 인 경우 남쪽,
$3$ 인 경우 서쪽

dx, dy : 동남서북 순으로 탐색
adjMatrix : 장소의 상태를 나타내는 2차원 배열
visited : 방문 처리
nx, ny : 다음으로 이동할 칸의 좌표
backD, backX, backY : 후진할 좌표 및 방향

cnt : 청소하는 칸의 개수
clean : 청소할 칸이 하나라도 남아 있으면 1, 없으면 0

풀이

처음에 문제 유형이 그래프인줄 알고 풀었는데 그냥 빡구현 시뮬레이션이다.
그동안 북쪽을 기준으로 오른쪽(시계 방향)으로 돌면서 탐색하는 코드를 작성했다.
하지만 이 문제에서는 왼쪽(반시계 방향)으로 돌아야 하는 문제여서 이걸 처리하는 부분이 어려웠다.

(입력 및 선언)

방의 크기를 입력받는다
현재 로봇 청소기의 위치와 방향을 입력받는다
동쪽부터 반시계 방향으로 탐색한다 (dx, dy)

처음 시작하는 위치인 r, c에 방문 처리를 해준다.
시작하는 부분도 결국 청소를 해야 하므로 cnt는 1로 초기화한다.

(청소를 하자)

무한 반복문
청소를 해야 할 곳이 남았는지를 확인하는 변수 clean을 0으로 초기화한다

네 방향을 탐색해야 하므로 4번 반복한다
이동할 다음 칸은 현재 칸(r/c)에서 왼쪽으로 돈 방향((d+3)%4)의 좌표를 더한 값이다.
방향도 (d+3)%4로 바꿔준다

만약 다음 칸이 맵 안에 있고, 청소가 되지 않은 곳이고(adjMatrix[nx][ny] == 0)
방문하지 않은 곳이라면(if visited[nx][ny] == 0)
방문 처리를 하고, 청소하는 칸의 개수를 나타내는 cnt 값을 하나 증가시킨다.
청소할 방향이 남아 있는지 확인하는 변수인 clean의 값을 1로 바꾸었다.
그리고 현재 칸을 nx, ny로 바꿔 이동한다.

만약 더이상 청소해야 할 칸이 없다면, 두 가지로 나누어 처리한다.
1) 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
- 방향은 유지해야 하므로 (d+2)%4를 해야 한다.
- 좌표는 현재 칸에서 (d+2)%4의 좌표를 더한 값이다.
- 후진할 칸이 벽도 아니고, 맵 안에 있으면 현재 위치를 backX, backY로 바꾼다.

2) 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
- 후진할 수 없으면(벽이거나 맵 밖이거나) cnt를 출력하고 반복문 종료

최종 코드

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

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

adjMatrix = []
visited = [[0 for _ in range(m)] for _ in range(n)]

for _ in range(n):
    adjMatrix.append(list(map(int, input().split())))

visited[r][c] = 1
cnt = 1

while True:
    clean = 0
    
    for _ in range(4):
        nx = r + dx[(d+3)%4]
        ny = c + dy[(d+3)%4]
        d = (d + 3) % 4 
        
        if 0 <= nx < n and 0 <= ny < m and adjMatrix[nx][ny] == 0:
            if visited[nx][ny] == 0:
                visited[nx][ny] = 1
                cnt += 1
                clean = 1
                r, c = nx, ny
                break

    if clean == 0:
        backD = (d + 2) % 4
        backX = r + dx[backD]
        backY = c + dy[backD]
        if n <= backX < 0 or m <= backY < 0 or adjMatrix[backX][backY] == 1:
            print(cnt)
            break
        else:
            r, c = backX, backY