[JS] 백준 14503번: 로봇 청소기

hxx_1 2025. 5. 23. 22:09

https://www.acmicpc.net/problem/14503

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

let [n, m] = input[0].split(" ").map(Number);
let [r, c, d] = input[1].split(" ").map(Number); // 로봇 청소기 좌표, 방향
let room = Array.from({ length: n }, () => Array(m).fill(0));
let visited = Array.from({ length: n }, () => Array(m).fill(false));

let start = 2;
for (let i = 0; i < n; i++) {
  let state = input[start].split(" ").map(Number);
  for (let j = 0; j < m; j++) {
    room[i][j] = state[j];
  }
  start++;
}

// 북 동 남 서
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
let count =0;

while(true){
  if(room[r][c]==0 && !visited[r][c]){
    count++;
    visited[r][c] = true;
  }
  let found = false;

  for(let i=0;i<dx.length;i++){
    d = (d + 3) % 4;
    let nx = r+dx[d];
    let ny= c+dy[d];

    if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
      if (room[nx][ny] === 0 && !visited[nx][ny]) { 
        r=nx;
        c=ny;
        found=true;
        break;
      }
    }
  }

  if(!found){
    let back = (d+2)%4;
    let bx = r+dx[back];
    let by= c+dy[back];

    if (bx < 0 || bx >= n || by < 0 || by >= m || room[bx][by] === 1) {
      break; 
    }
    r = bx;
    c = by; 
  }
}

console.log(count);

✏️ 풀이 방법

1. 각 방의 상태를 저장하기 위한 room 이라는 2차원 배열 생성, 해당 방의 방문 여부를 확인하는 visited 2차원 배열 생성

2. 무한 루프 반복문을 돌기

: 현재 위치의 방이 청소가 되지 않은 상태이면 count 값 증가, visited 를 true 로 변경

: 현재 위치를 기준으로 주변의 방 상태를 확인

=> 반시계 방향으로 회전 후 현재 위치를 nx,ny 에 저장

=> nx 와 ny 의 값이 방의 크기를 벗어나지 않고, 청소 가능한 상태(0) 이고 방문한 적이 없으면

: 위치 변경(전진), 반복문 종료

3. 만약 청소 가능한 곳을 찾지 못했으면

=> 후진 후 현재 위치를 bx,by 에 저장

=> bx 또는 by 가 방의 크기를 벗어나거나 room[bx][by] 가 청소 가능한 상태가 아니면(1)

: 반복문 종료(전체 무한루프)

=> 그렇지 않은 경우

: 다시 반복문

4. 무한 루프 반복문이 종료되면 count 값 출력

⁉️ 문제에서 헷갈렸던 부분

1️⃣ 왜 청소되지 않은 빈 칸이 있는지 확인하기 전에 회전을 하는가?

청소되지 않은 빈 칸이 있는 경우 회전하는게 아닌가? 왜 그걸 확인하기 전에 반시계 방향으로 회전을 하지 라는 의문을 가졌다. 하지만 실제 시뮬레이션은 왼쪽 방향부터 차례로 4번 회전하며, 회전한 방향의 앞 칸이 빈 칸이면 이동하고 아니면 또 왼쪽으로 회전해서 반복하는, 즉 왼쪽부터 차례로 4방향을 확인하는 것이 문제의 의도라고 한다.

2️⃣ (d + 3) % 4 이 전진이고, (d + 2) % 4 가 후진이 되는 이유는?

let dx = [-1, 0, 1, 0]; // 북,동,남,서
let dy = [0, 1, 0, -1];

문제에서 북은 0, 동은 1, 남은 2, 서는 3으로 지정해두었기 때문에 방향 인덱스 또한 위와 같이 지정을 해줘야한다. 왼쪽(반시계)는 d-1 을 해야하는데, 이렇게 할 경우 음수가 되는 경우가 있으므로 이를 방지하기 위해 (d+3)%4 와 같이 해주고, 뒤쪽(180도) 의 경우에는 (d+2)%4 와 같이 해주면 된다.

✍🏻 느낀점

오랜만에 문제를 푸니까 뭔가 너무 머리가 안돌아가는 느낌이었다. 이런 방향 회전 문제를 자주 접하게 되는데, 아직도 많이 부족하다는 것을 깨달았다. 좀 더 문제에 익숙해질 수 있도록,, 사고가 좀 유연해질 수 있도록 1일 1문제 풀기 다시 시작해야겠다🥹