삼성 SW 역량테스트 백준 로봇청소기 14503

2020-09-11

1. 문제 링크

2. 문제 조건

장소 조건

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇청소기의 작동 방식

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

현재 위치를 청소한다.
현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

단, 로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

3. 컴퓨팅 사고

로봇이 북동남서의 방향에 따른 왼쪽 회전의 경우를 잘 생각해주어야 합니다.
로봇이 후진하는 경우에 대해서 좌표값을 잘 이해할 수 있어야합니다.

로봇이 왼쪽방향으로 부터 차례대로 탐색을 진행 할 수 있어야 한다.

북(0) → 서(3), 서(3) → 남(2), 남(2) → 동(1), 동(1) → 북(0)

하나의 예를 들어서 설명해보겠습니다. 첫번째 테스트 케이스를 예로 들어보겠습니다. 현재 방향이 북(0), r = 1, c = 1 의 값을 갖습니다. 현재 (1,1)의 위치에서 북쪽방향을 바라보고있는 로봇청소기 입니다. 로봇청소기가 이제 왼쪽으로 값을 회전시키기 위해서는 어떻게 할 수 있을까요?

1 2	int dx[4] = {-1,0,1,0}; int dy[4] = {0,1,0,-1};

현재 위치가 0번 즉, 북쪽을 바라보고 있습니다. 북쪽을 바라보고 있으면서 이제 로봇청소기가 왼쪽으로 탐색을 진행해야하기때문에 서쪽방향으로 이동할 수 있어야합니다. 그러면 현재 (1,1)의 위치에서 (현재 R 위치-1),(현재 C위치 - 0) 의 방향으로 이동을 시키면 왼쪽으로 이동시킬 수 있겠습니다.

그래서 dx,dy의 값의 기준도 (북→서, 서→남, 남→동, 동→북) 의 형식으로 dx,dy의 값을 기준을 잡았습니다.

방향 회전

그러면 이것을 방향회전하는 경우로 바꾸려면 어떻게 진행해야 할까요? 현재 북쪽을 제외한 나머지는 차이가 1이나는것을 확인할 수 있습니다.

북(0) → 서(3), 서(3) → 남(2), 남(2) → 동(1), 동(1) → 북(0)

이것을 코드로 표현한다면 북쪽을 제외한 나머지는 차이가 d-1만큼 차이가 나게됩니다. 그러면 북쪽의 값은 d-1이 음수가 되는경우 즉, d가 0(북쪽)일 경우 이 값을 3으로 변경해주면 됩니다.

코드에서 표현한 것은

1	int next_dir = d-1 < 0 ? 3 : d-1;

아래와 같이 표현할 수 있습니다.

또 다른 방식으로는

북쪽을 제외한 값들이 차이가 1이나고 북쪽(0)과 이동하려는 왼쪽의 서쪽값이(3)이 되기때문에 이것을 코드로 표현하면

1	int next_dir = (d+3) % 4

의 형태로도 나타낼 수 있습니다.

d = (0 + 3) % 4

몫: 0 나머지: 3

d = (1 + 3 )% 4

몫: 1 나머지: 0 

d = (2 + 3) % 4

몫: 1 나머지: 1

d = (3 + 3) % 4  

몫: 1 나머지: 2

의 형태를 띄기 때문에 이것을 표현한 것과 같습니다.

방향 후진

방향 후진의 경우에는 모든 4개의 방향을 탐색하고 나고나서도 청소가 되어있으면 다시 제자리로 돌아와서 후진을 해주면됩니다.

예를 들어서 서쪽 기준으로 (남,동,북,서)를 탐색한다고 생각을 하면 모든 방향이 청소가 되어 있거나 벽일 경우면 다시 제자리 서쪽으로 돌아오게 될 것입니다. 이제 서쪽기준으로 후진을 하게 되면 (1,0) 만큼 후진을 진행하게 될 것입니다. 남쪽 기준으로 탐색을 한다고 하면 다시 남쪽으로 돌아온다면 (0,-1)만큼 후진을 진행하면 됩니다.

1 2	int back_dx[4] = {1,0,-1,0}; int back_dy[4] = {0,-1,0,1};

이와 같이 후진하는 경우에 대해서도 배열형태로 확인을 할 수 있습니다.

4. 소스 코드


//
//  로봇청소기.cpp
//  algorithm-ps
//
//  Created by kgh on 2020/09/09.
//  Copyright © 2020 kgh. All rights reserved.
//

#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_SIZE = 51;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int back_dx[4] = {1,0,-1,0};
int back_dy[4] = {0,-1,0,1};

int ans = 0;
int map[MAX_SIZE][MAX_SIZE];
int n,m;
int r,c,d;

void dfs(int r,int c,int d){
    
    // 뒤에가 벽이라면 종료 시켜준다.
    if(map[r][c] == 1){
        return;
    }
    // 현재 위치 청소
    if(map[r][c] == 0){
        map[r][c] = 2;      // 현재 위치 청소
        ans++;
    }

    for(int i=0; i<4; i++){
        //int next_dir = d-1 < 0 ? 3 : d-1;
        int next_dir = (d+3) % 4;
        int next_x = r + dx[next_dir];
        int next_y = c + dy[next_dir];
        
        // 빈칸 이면 청소
        if(map[next_x][next_y] == 0){
            dfs(next_x, next_y, next_dir);
            return;
        }
        // 빈칸이 아닐 경우
        else {
            d = next_dir;
        }
    }
    // 4번의 방향을 모두돌고 다시 제자리로 돌아가는것이므로 만약에 0에서 시작해서 3까지 이동해서 모든 값들의 방향이 이동되어서 3일 경우 0의 자리로 돌아가주는것을 생각해주어야한다. 그리고 나서 후진을 한다.
    int next_x = r + back_dx[d]; // 기존의 방향대로 회전시켜준다.
    int next_y = c + back_dy[d];
    dfs(next_x, next_y, d);
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m;
    cin >> r >> c >> d;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> map[i][j];
        }
    }
    dfs(r,c,d);
    cout << ans << '\n';
}

AlgorithmSW역량테스트

1. 문제 링크

2. 문제 조건

3. 컴퓨팅 사고

4. 소스 코드