[BOJ] 백준 14503 로봇 청소기 / 구현

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

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

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

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

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

 

구현 문제이기에 문제 조건을 잘 구현하는 것에 집중했다.

 

 

💭 풀이 과정

 

 

풀이를 좀 찾아봤는데, 재귀를 사용해서 BFS, DFS 방식으로 풀어낸 분들도 꽤 있었다.

 

근데 그냥 반복문과 if문으로도 풀 수 있을 것 같다는 생각에 문제 조건을 그대로 구현하는 것에 집중해보았다.

 

1. 현재 위치가 청소가 가능한데 안되어있는 곳(0)이라면 청소를 수행한다.(2로 변경)

2. 사방이 벽이거나 청소가 되어있는 곳이라면 후진을 한다. 그런데 후진을 한 곳이 벽이라면 청소 작업을 종료한다.

   (반복문 탈출해서 결과 출력으로 이어짐)

3. 위의 조건에 걸리지 않았다면 네 방향 중 청소할 곳이 남아있다는 것이다.

    제자리에서 돌면서 네 방향 중 청소할 곳을 찾고, 찾았다면 그 방향으로 회전한 상태로 그 칸으로 이동한다.

4. 다시 1번 작업부터 시작하면서 2번의 종료 조건을 만족할 때까지 반복문을 수행한다.

 

 

작성 언어: C++

#include <iostream>
#include <algorithm>
using namespace std;

int grid[51][51] = {0, };

int findNextDir(int dir) {
    return (dir == 0) ? 3 : dir - 1;
}

int main() {
    int n = 0, m = 0;
    int r = 0, c = 0, dir = 0;
    int cleans = 0;
    // (북 동 남 서) 각 방향 기준 좌측 좌표 이동
    int dr[4] = {0, -1, 0, 1};
    int dc[4] = {-1, 0, 1, 0};
    
    // read
    cin >> n >> m;
    cin >> r >> c >> dir;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }
    
    while (1) {
        if (grid[r][c] == 0) {
            // 현재 위치가 청소가 안된 곳이라면 청소(청소하고 2로 표시)
            grid[r][c] = 2;
            cleans += 1;
        }
        
        // 사방이 청소되었거나 벽인 경우 현재 방향을 유지하고 후진
        if ((grid[r][c-1] == 1 || grid[r][c-1] == 2) && (grid[r][c+1] == 1 || grid[r][c+1] == 2) && (grid[r-1][c] == 1 || grid[r-1][c] == 2) && (grid[r+1][c] == 1 || grid[r+1][c] == 2)) {
            if (dir == 0)   r += 1; // 북쪽을 보고 있다면 한 행 아래로
            else if (dir == 1)  c -= 1; // 동쪽을 보고 있다면 한 열 왼쪽으로
            else if (dir == 2)  r -= 1; // 남쪽을 보고 있다면 한 행 위로
            else if (dir == 3)  c += 1; // 서쪽을 보고 있다면 한 열 오른쪽으로
            
            // 후진한 곳이 벽이면 정지
            if (grid[r][c] == 1)    break;
            
            continue;
        }
        
        // 네 방향 중 청소할 곳이 남아있는 경우
        while (1) {
            // 현재 방향 기준 좌측 좌표
            int nr = r + dr[dir];
            int nc = c + dc[dir];
            
            // 좌측에 청소할 곳이 남아있다면 그 방향으로 회전하고 이동해서 청소하고,
            // 청소할 곳이 아니라면 좌측으로 회전하고 다시 작업 수행
            if (grid[nr][nc] == 0) {
                r = nr; c = nc;
                dir = findNextDir(dir);
                break;
            }else {
                dir = findNextDir(dir);
            }
        }
    }
    
    cout << cleans << endl;
    
    return 0;
}

 

 

 

 

🏆 배운 점

 

 

이번에 우테코(우아한 테크 코스)에 지원하면서 설명회 영상이랑 각종 후기들을 열심히 찾아봤다.

코테에 논리적인 사고력을 요구하는 문제들을 출제하신다고 하길래 구현 문제를 좀 풀어봐야 하나.. 싶어서 백준에서 처음 도전해보는 구현 문제이다.

 

문제 난이도에 비해 시간을 좀 오래 써서 느낀 바가 많다,,,

일단 성급하게 접근하지 말고 먼저 테스트케이스들을 직접 완벽하게 풀어내 보자!!(제발😱)

 

구현 문제는 더더욱 문제를 꼼꼼히 확인하고 직접 손으로 풀어보면서 예외사항을 잘 체크하는 것이 중요한 것 같다.