문제
문제 설명
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 방은 크기의 직사각형으로 나타낼 수 있으며, 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 , 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 이다. 즉, 좌표 는 북쪽에서 번째에 있는 줄의 서쪽에서 번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.
로봇 청소기는 다음과 같이 작동한다.
- 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
- 현재 칸의 주변 칸 중 청소되지 않은 빈 칸이 없는 경우,
- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
- 현재 칸의 주변 칸 중 청소되지 않은 빈 칸이 있는 경우,
- 반시계 방향으로 회전한다.
- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
- 1번으로 돌아간다.
입력
첫째 줄에 방의 크기 과 이 입력된다. 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 와 처음에 로봇 청소기가 바라보는 방향 가 입력된다. 가 인 경우 북쪽, 인 경우 동쪽, 인 경우 남쪽, 인 경우 서쪽을 바라보고 있는 것이다.
셋째 줄부터 개의 줄에 각 장소의 상태를 나타내는 개의 값이 한 줄에 개씩 입력된다. 번째 줄의 번째 값은 칸 의 상태를 나타내며, 이 값이 인 경우 가 청소되지 않은 빈 칸이고, 인 경우 에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.
출력
로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.
입출력
예제 입력 1
3 31 1 01 1 11 0 11 1 1
예제 출력 1
1
예제 입력 2
11 107 4 01 1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 0 11 0 0 0 1 1 1 1 0 11 0 0 1 1 0 0 0 0 11 0 1 1 0 0 0 0 0 11 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 1 0 11 0 0 0 0 0 1 1 0 11 0 0 0 0 0 1 1 0 11 0 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 1 1
예제 출력 2
57
코드
const input = require('fs').readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt').toString().trim().split('\n');const [N, M] = input.shift().split(' ').map(Number);let [x, y, d] = input.shift().split(' ').map(Number);const graph = input.map(line => line.split(' ').map(Number));const visited = Array.from({ length: N }, () => Array(M).fill(false));const dx = [-1, 0, 1, 0];const dy = [0, 1, 0, -1];let answer = 0;let directionCount = 0;while (true) {if (!visited[x][y]) {visited[x][y] = true;graph[x][y] = -1;answer++;}if (directionCount === 4) {const backX = x + dx[(d + 2) % 4];const backY = y + dy[(d + 2) % 4];if (graph[backX][backY] === 1) break;else {x = backX;y = backY;directionCount = 0;}}const leftX = x + dx[(d + 3) % 4];const leftY = y + dy[(d + 3) % 4];if (graph[leftX][leftY] === 0) {x = leftX;y = leftY;directionCount = 0;} else {directionCount++;}d = (d + 3) % 4;}console.log(answer);
순환배열
순환 배열은 배열의 끝과 시작이 연결된 구조로, 마지막 요소 다음에는 첫 번째 요소가 오며, 첫 번째 요소 이전에는 마지막 요소가 위치한다. 이는 배열을 원형으로 생각하면 이해하기 쉽다.
다음 요소
(index + 1) % len
index + 1
은 다음 인덱스를 나타낸다.%len
은 배열의 끝에 도달하면 처음으로 돌아가게 한다.- ex) 배열 길이가 5일 때, 인덱스 4의 다음 요소는
(4 + 1) % 5 = 0
이다.
이전 요소
(index - 1 + len) % len
index - 1
은 이전 인덱스를 나타낸다.+len
은 음수 결과를 방지한다(JavaScript에서음수 % 양수
의 결과가 음수일 수 있음).%len
은 배열의 시작 이전으로 갔을 때 끝으로 돌아가게 한다.
예제 코드
function getAdjacentElements(arr, index) {const len = arr.length;const prevIndex = (index - 1 + len) % len;const nextIndex = (index + 1) % len;return [arr[prevIndex], arr[nextIndex]];}const myArray = [1, 2, 3, 4, 5];console.log(getAdjacentElements(myArray, 0)); // [5, 2]console.log(getAdjacentElements(myArray, 2)); // [2, 4]console.log(getAdjacentElements(myArray, 4)); // [4, 1]