문제
https://www.acmicpc.net/problem/14503
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.
로봇 청소기는 다음과 같이 작동한다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
2.1 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
2.2 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
2.3 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
2.4네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
입력
첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)
둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.
셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.
로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.
출력
로봇 청소기가 청소하는 칸의 개수를 출력한다.
아이디어
✅ 주어진 테스트 케이스로 직접 해보았다.
- 처음에 현재 위치를 청소한다.
- 왼쪽을 검사한다.
- 청소할 수 있는 경우
- 회전하고 한 칸 전진한 후 다시 처음부터 반복한다.
- 청소할 수 없는 경우
- 회전을 하고 다시 왼쪽을 검사한다.
- 4번 회전을 한 경우는 모든 방향을 검사한 것이므로 후진을 해야한다.
- 후진을 할 때 뒤가 벽인 경우
청소가 끝난다.- 뒤가 벽이 아닌 경우
후진을 한 후 왼쪽 검사부터 다시 반복한다.✔️ 코드 설명
1. 입력을 받은 후, 주어진 배열의 크기와 같은 visited를 만들어서 청소를 했는지 표시한다.
2. direction을 만들어서 각 방향의 왼쪽 위치를 표시한다.👍 direction설명 0 : 북쪽방향이면 인덱스에 각 [0, -1]을 더해주면 왼쪽이다. 3 : 서쪽방향이면 인덱스에 각 [1, 0]을 더해주면 왼쪽이다. 2 : 남쪽방향이면 인덱스에 각 [0, 1]을 더해주면 왼쪽이다. 1 : 동쪽방향이면 인덱스에 각 [-1, 0]을 더해주면 왼쪽이다.
- 회전을 몇 번 했는지 표시하는 c를 만든다.
- 처음 청소기 위치를 청소했다고 표시하고 ans = 1로 만든다.
- 현재 위치에서 왼쪽 방향을 검사한다.
- 왼쪽이 False(청소를 하지 않았고), 0(벽이 아님)이면 회전을 하고 한 칸 전진해서 True로 변경하고 ans += 1을 한다.
(한 칸 회전하면 0 -> 3 -> 2 -> 1 순서로 돌아가기 때문에 -1을 하고 %4의 값으로 바뀐다.)- 청소할 수 없으면 회전을 하고 c += 1을 한다.
- 회전을 4번 한 경우에는 c를 0으로 초기화하고 로봇의 뒤를 검사한다.
(로봇의 뒤쪽 인덱스는 한 번 회전한 후 왼쪽과 같다.)- 뒤가 벽이면 청소를 끝내고 벽이 아니면 후진을 하고, 방향은 바꾸지 않고 계속 반복한다.
내 코드_python
:: 방문 표시를 하기 위해 visited를 만들어서 표시했는데 arr에 0, 1이 아닌 2와같은 수로 표현하는 방법도 있다.
n, m = map(int, input().split()) robot = list(map(int, input().split())) arr = [list(map(int, input().split())) for x in range(n)] visited = [[False]*m for x in range(n)] direction = {0:[0, -1], 3:[1, 0], 2:[0, 1], 1:[-1, 0]} #북, 서, 남, 동 c = 0 #회전 몇 번 했는지 visited[robot[0]][robot[1]] = True ans = 1 while True: #왼쪽 검사 lx = robot[0] + direction[robot[2]][0] ly = robot[1] + direction[robot[2]][1] if visited[lx][ly] == False and arr[lx][ly] == 0: #왼쪽을 청소할 수 있는 경우 c = 0 #청소를 하면 회전한 값을 초기화 해야 함 robot[2] = (robot[2] - 1) % 4 robot[0] = lx robot[1] = ly visited[lx][ly] = True ans += 1 else: #왼쪽 청소할 수 없으면 회전하기 c += 1 robot[2] = (robot[2] - 1) % 4 if c == 4: #4번을 회전하면 모든 방향을 모두 검사한 것이므로 후진할 수 있는지 검사 c = 0 chk = (robot[2] - 1) % 4 cx = robot[0] + direction[chk][0] cy = robot[1] + direction[chk][1] if arr[cx][cy] == 1: #뒤가 벽이면 후진할 수 없고 청소 끝 print(ans) break else: #벽이 아니면 후진하고 다시 왼쪽부터 검사 robot[0] = cx robot[1] = cy
