백준 14503 로봇 청소기 - Node.js

문제

문제는 여기에서 확인

문제풀이

N, M의 크기가 크지 않고 모든 방향을 탐색해야 하므로 완전 탐색을 사용한다. 청소 가능한 방향을 우선으로 깊이 탐색하므로 DFS를 사용했다.

 

1.청소한 곳을 방문 처리할 visited 배열을 생성한다.

2. 문제에 적힌 대로 북동남서(0, 1, 2, 3) 방향 배열을 생성한다.

// 북, 동, 남, 서
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];

3. 현재 위치를 방문처리 하고 DFS를 수행한다.

POINT

1. 반시계 방향으로 회전하므로 방향은 +1이 아닌 +3으로 계산해야 한다.
2. 네 방향 모두 청소하여 후진할 때는 방향을 유지한 채로 이동한다.

전체 코드

const fs = require("fs");
const [[n, m], [r, c, d], ...graph] = fs.readFileSync("/dev/stdin").toString().trim().split("\n")
    .map(line => line.split(" ").map(Number));
const visited = Array.from(new Array(n), () => Array(m).fill(false));
// 북동남서
const dr = [-1, 0, 1, 0];
const dc = [0, 1, 0, -1];
let answer = 1; // 현재 위치 카운트

visited[r][c] = true; // 현재 위치 방문 처리
dfs(r, c, d);
console.log(answer);
        
function dfs(r, c, d) {    
    for (let i = 0; i < 4; i++) {
        d = (d + 3) % 4; // 반시계 방향으로 90도 회전
        const nr = r + dr[d];
        const nc = c + dc[d];
        
        // 범위를 벗어나면 패스
        if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
        // 벽이면 패스
        if (graph[nr][nc] === 1) continue;
        // 아직 청소하지 않았으면
        if (graph[nr][nc] === 0 && !visited[nr][nc]) {
            visited[nr][nc] = true;
            answer++;
            dfs(nr, nc, d);
            return; // 네 방향 탐색 종료
        }
    }
    
    // 네 방향 모두 이미 청소했으면
    d = (d + 2) % 4; // 후진 방향
    const nr = r + dr[d];
    const nc = c + dc[d];

    // 범위를 벗어나면 종료
    if (nr < 0 || nr >= n || nc < 0 || nc >= m) return;
    // 벽이면 종료
    if (graph[nr][nc] === 1) return;
    // 빈 칸이면 후진
    if (graph[nr][nc] === 0) dfs(nr, nc, (d + 2) % 4); // 방향을 유지한 채로 후진
}