[BOJ][C++] 백준 14503번: 로봇 청소기

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

14503번: 로봇 청소기

 

문제

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

(중략)

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

 

출력

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

 

풀이

문제에 나와있는대로 순차적으로 구현하는 구현 문제다.

 

우선 입력값을 받아서 벡터에 저장해준 뒤, 로봇청소기의 경로를 시뮬레이션 하자

1: 벽

0: 빈공간(청소안함)

2: 빈공간(청소함)

 

 

1번 조건 > 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.

현재 위치 v[r][c]에 청소했다는 의미로 2로 값을 변경한다.

1(벽으)로 표시하지 않게 주의하자. 청소한 공간은 벽과 달리 후진(3번 조건)할 때 지나갈 수 있다

        if(v[r][c]==0) {
            ans++;
            v[r][c] = 2;
        }

 

 

3번 조건 > 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,

for문을 돌려서 네 방향을 탐색한다.

"반시계" 방향에 유의하자. 문제에서 주어진 d는 북 서 남 동  이지만

반시계 방향은 북 동 서 남 이다. 즉 d를 감소시켜야한다

 

그렇게 돌린 방향의 좌표 v[nx][ny] 가 청소 여부를 검사한다

청소가 되어있다면(값이 0) 이동시킨다. r=nx, c=ny, d=nd

그리고 1번으로 돌아간다. -> 방향 탐색용 for문 break

        bool isMoved = false;
        for(int i=0; i<4; i++) {
            // 3-1. 반시계 방향으로 90도 회전
            int nd = (d-i+3)%4; 
            int nx = r+dx[nd];
            int ny = c+dy[nd];
            
            // 3-2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
            if(v[nx][ny] == 0) { 
                r = nx;
                c = ny;
                d = nd;
                isMoved = true;
                break; // 3-3. 1번으로 돌아간다.
            }

 

 

3번 조건 > 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,

아래 코드에 진입하는 경우는 두가지다

1) 청소되지 않은 칸을 발견해서 한 칸 전진하고 break로 도달. isMoved = true;

2) 청소되지 않은 칸이 주변에 없어서 for문을 다 돌고 도달. isMoved = false;

두가지 경우를 구분해주기 위해 2번 경우에만 아래 코드가 실행된다 (1번 경우는 실행되지 않고 바로 1단계로 돌아간다 #while)

 

현재 방향 d를 기준으로 뒤로 가는 방향(back = (d+2)%4;)으로 이동한다(r += dx[back]; c += dy[back];) 

후진한 위치가 벽이면 작동을 멈춘다. -> while문 break

벽이 아니라면 잘 후진한거니 스무스하게 while 따라 1단계로 돌아간다

 

        if(!isMoved) {
            // 3-1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
            int back = (d+2)%4;
            r += dx[back];
            c += dy[back];
            
            // 3-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
            if(v[r][c] == 1) break;
        }

 

코드

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>

using namespace std;

// 북, 서, 남, 동
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};

int main() {
    // 입력
    int n,m, r,c,d;
    cin >> n >> m >> r >> c >> d;
    vector<vector<int>> v(n, vector<int>(m));
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            cin >> v[i][j];
        }
    }
    
    int ans=0; // 청소 카운트
    while(true) {
        // 1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
        if(v[r][c]==0) {
            ans++;
            v[r][c] = 2;
        }
        
        // 3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
        bool isMoved = false;
        for(int i=0; i<4; i++) {
            // 3-1. 반시계 방향으로 90도 회전
            int nd = (d-i+3)%4; 
            int nx = r+dx[nd];
            int ny = c+dy[nd];
            
            // 3-2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
            if(v[nx][ny] == 0) { 
                r = nx;
                c = ny;
                d = nd;
                isMoved = true;
                break; // 3-3. 1번으로 돌아간다.
            }
        }
        
        // 2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우
        if(!isMoved) {
            // 3-1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
            int back = (d+2)%4;
            r += dx[back];
            c += dy[back];
            
            // 3-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
            if(v[r][c] == 1) break;
        }
    }
    
    cout << ans;
}

 

예제가 틀렸나요?

예제2의 답이 57이 아닌 52로 나왔다면

로봇의 4방향 중 한 곳이라도 청소할 수 있는 곳이 있는 경우 무.조.건 반시계 방향으로 90도 회전이 먼저 이루어져야 함.

이 조건을 만족하는지 확인하자.

직진할 수 있으면 직진하는게 아니다 !!!

 

예를들어 아래와 같은 순서로 간다면 (알파벳 순서대로 청소한다고 생각하면 됨)

로봇이 직진이 가능하면 직진 먼저 되는 경우로 잘못 된 경우다

1 1 1 1 1 1 1 1 1 1 
1 r q p o n m l k 1 
1 s 0 0 1 1 1 1 j 1 
1 t 0 1 1 0 0 0 i 1 
1 u 1 1 d e f g h 1 
1 v � � c � � � � 1 
1 w � � b � 0 1 � 1 
1 x � � a � 1 1 � 1 
1 y � � � � 1 1 � 1 
1 z a b c d e � � 1 
1 1 1 1 1 1 1 1 1 1

 

제대로 된 경우는 아래 순서로 가야한다

1 1 1 1 1 1 1 1 1 1 
1 � � � � � � � � 1 
1 � � � 1 1 1 1 � 1 
1 � � 1 1 � � � � 1 
1 � 1 1 � � f e 0 1 
1 � � l k � � d c 1 
1 � n m j i 0 1 b 1 
1 p o b a h 1 1 z 1 
1 q r c d g 1 1 y 1 
1 u s t e f v w x 1 
1 1 1 1 1 1 1 1 1 1