[좋은문제]백준 14503: 로봇 청소기 - javascript(구현)

문제 출처 

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

14503번: 로봇 청소기

문제

로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 방은 �×�$N \times M$ 크기의 직사각형으로 나타낼 수 있으며, 1×1$1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 (�,�)$(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0)$(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (�−1,�−1)$(N-1, M-1)$이다. 즉, 좌표 (�,�)$(r, c)$는 북쪽에서 (�+1)$(r+1)$번째에 있는 줄의 서쪽에서 (�+1)$(c+1)$번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

로봇 청소기는 다음과 같이 작동한다.

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

입력

첫째 줄에 방의 크기 �$N$과 �$M$이 입력된다. (3≤�,�≤50)$(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 (�,�)$(r, c)$와 처음에 로봇 청소기가 바라보는 방향 �$d$가 입력된다. �$d$가 0$0$인 경우 북쪽, 1$1$인 경우 동쪽, 2$2$인 경우 남쪽, 3$3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 �$N$개의 줄에 각 장소의 상태를 나타내는 �×�$N \times M$개의 값이 한 줄에 �$M$개씩 입력된다. �$i$번째 줄의 �$j$번째 값은 칸 (�,�)$(i, j)$의 상태를 나타내며, 이 값이 0$0$인 경우 (�,�)$(i, j)$가 청소되지 않은 빈 칸이고, 1$1$인 경우 (�,�)$(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.

예제 입력 1 복사

3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 1 복사

1

예제 입력 2 복사

11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제 출력 2 복사

57

문제 풀이 힌트 

구현을 푸는 핵심은 문제를 어떻게 짜임새있게 풀어낼 건지인 것 같다. 

여러 풀이를 봤는데, 한 분의 풀이가 참 대단했다. 

구성은, 

- 전체적인 코드는,  while(1){

} 반복문 안에서 계속 실행된다. 

1) 현재 있는 곳이 `graph[x][y] === 0` 빈칸이면 청소한다. 

2) 현재 바라보고 있는 곳에서 90도 왼쪽으로 이동했을 때 빈칸이 아니면 cnt++, 빈칸이면  이동을 해서 청소를 하면 된다.  

3) cnt값이 4가 됐다는 건, 사방면이 다 청소 되어있다는 뜻이다. 

=> 그때 후진을 시도 한다. 

=> 뒤에값 `graph[x][y] === 1` 이 벽이면 반복문을 벗어나는 break; 

벽이 아니라면 또 청소 시작 ~ 

정답 풀이 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [n,m] = input.shift().split(' ').map(Number); 
const [x,y,d] = input.shift().split(' ').map(Number);
const graph = input.map(v => v.split(' ').map(Number)); 

function solution(n,m,x,y,d,graph){
    let ds = [[-1,0],[0,1],[1,0],[0,-1]]; 
    const visited = [...Array(n)].map(()=> Array(m).fill(false)); 
    let answer = 0; 
    let cnt = 0; 
    while(1){
        if(!visited[x][y]){
            visited[x][y] = true; 
            graph[x][y] = 2; 
            answer++; 
        }
        const [nextx, nexty] = [x + ds[(d+3)%4][0], y +ds[(d+3)%4][1]]; 
        if(graph[nextx][nexty] === 0){
            x = nextx; 
            y = nexty; 
            cnt = 0; 
        }else{
            cnt++; 
        }
        d = (d+3)%4; 
        
        if(cnt === 4){
            const [backx, backy] = [x + ds[(d+6)%4][0], y +ds[(d+6)%4][1]]; 
            if(graph[backx][backy] === 1) break; 
            else{
                x = backx;
                y = backy; 
                cnt = 0; 
            }
        }
    }
    return answer; 
}
const answer = solution(n,m,x,y,d,graph); 
console.log(answer)

의사 코드 추가

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [n,m] = input.shift().split(' ').map(Number); 
const [x,y,d] = input.shift().split(' ').map(Number);
const graph = input.map(v => v.split(' ').map(Number)); 

function solution(n,m,x,y,d,graph){
    let ds = [[-1,0],[0,1],[1,0],[0,-1]]; //위, 오른쪽, 아래, 왼쪽
    const visited = [...Array(n)].map(()=> Array(m).fill(false)); //그래프 방문했는지 체크
    let answer = 0; // 청소 칸 개수
    let cnt = 0; //사방면 확인하며 청소안해도 되는 곳 +1씩 올려줄 것임 
    while(1){
    //내가 있는 칸을 방문하지 않았다면 방문해서 청소해라 
        if(!visited[x][y]){
            visited[x][y] = true; 
            graph[x][y] = 2; 
            answer++; 
        }
        //주변 4칸 중 청소되지 않은 빈 칸이 있는 경우 확인 
        //있는 경우 그 쪽으로 이동 (반시게 방향으로 이동)
        const [nextx, nexty] = [x + ds[(d+3)%4][0], y +ds[(d+3)%4][1]]; 
        if(graph[nextx][nexty] === 0){
            x = nextx; 
            y = nexty; 
            cnt = 0; 
        }else{
            cnt++; 
        }
        d = (d+3)%4; 
        
        //위에서 사방면이 다 청소할 필요 없을 때 후진 시도 
        //후진가능하면 거기서부터 다시 청소시작 , 탐색 시작 
        //후진 불가하면 반복문 break; 
        if(cnt === 4){
            const [backx, backy] = [x + ds[(d+6)%4][0], y +ds[(d+6)%4][1]]; 
            if(graph[backx][backy] === 1) break; 
            else{
                x = backx;
                y = backy; 
                cnt = 0; 
            }
        }
    }
    return answer; 
}
const answer = solution(n,m,x,y,d,graph); 
console.log(answer)