[백준 BOJ] 14503번 - 로봇 청소기 (C++)

📌 참고

교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏

💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers

교공 알고리즘 스터디 21주차 삼성기출

14503번: 로봇 청소기 | 문제 바로가기

문제풀이 (2022-01-27 THU 💻)

🤔 사담

처음에 문제 이해하는데 시간이 조금 걸리긴 했지만
조건 이해한 후에 순수 코딩하는 시간으로만은
그동안 풀었던 구현 문제 중에서 그나마 제일 금방 풀었던 문제였다

⭐ 풀이의 핵심

문제를 이해하는 데는 아래 블로그의 그림을 참고하였다
cf) https://royhelen.tistory.com/14

재귀 호출 을 활용하여 풀었고
clean이라는 함수와 checkBack이라는 함수 두 가지를 만들었다

• clean 함수에서 문제의 1, 2-a, 2-b 조건을 수행하고 cleanAble이라는 bool 타입 변수를 통해 해당 변수의 값이 false일 경우 즉, 네 방향 모두 청소가 이미 되었거나 벽인 경우 checkBack 함수 호출
• checkBack 함수에서 후진할 수 있는지 확인 후 clean 함수로 돌아감
  • 후진이 불가능할 경우 return false
  • 또는 후진이 가능할 경우 후진한 후 return true
• clean 함수로 돌아와 checkBack 함수의 return 값에 따라
  • true일 경우 clean 함수를 재귀 호출하여 청소 계속
  • 또는 false일 경우 clean 함수 종료
    
    

🔽 코드 (C++)

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

#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3

// 0:NORTH↑ 1:EAST→ 2:SOUTH↓ 3:WEST← 
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

// 세로 크기 N과 가로 크기 M
int N, M;

// 로봇청소기가 있는 칸의 좌표 (r,c)와 바라보는 방향 d
struct Robot {
    int r, c, d;
};

Robot robot;
int answer = 0;

bool checkBack(vector<vector<int>> map) {
    // 후진 방향 설정
    int backD;
    if (robot.d == NORTH || robot.d == SOUTH) {
        backD = 2-robot.d; // 0:NORTH <-> 2:SOUTH
    } 
    else { // robot.d == EAST || robot.d == WEST
        backD = 4-robot.d; // 1:EAST <-> 3:WEST
    }
    int backR = robot.r + dr[backD];
    int backC = robot.c + dc[backD];

    // 후진 가능 여부 체크 
    // d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
    if (map[backR][backC] == 1) { // 후진 불가능 (종료)
        return false;
    }
    // c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
    else { // 후진 가능 (후진 실시)
        robot.r = backR;
        robot.c = backC;
        return true;
    }
}

void clean(vector<vector<int>> &map) {
    // 1. 현재 위치를 청소한다.
    if (map[robot.r][robot.c] == 0) {
        map[robot.r][robot.c] = -1; // 청소 완료 칸은 -1로 표시
        answer++;
    }

    int nextD = robot.d;
    int nextR, nextC;
    bool cleanAble = false;

    for (int i=0; i<4; i++) {
        // 2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
        // NORTH -> WEST -> SOUTH -> EAST 순으로 회전
        nextD = (nextD + 3) % 4;
        nextR = robot.r + dr[nextD];
        nextC = robot.c + dc[nextD];

        // a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
        if (map[nextR][nextC] == 0) {
            robot.r = nextR;
            robot.c = nextC;
            robot.d = nextD;
                
            cleanAble = true;
            break;
        }

        // b. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
    }

    // cleanAble이 false라면 네 방향 모두 청소가 이미 되어있거나 벽인 경우이므로
    // 뒤쪽 방향의 벽 여부를 체크하여 후진 실시 or 종료가 이루어져야 함
    if (!cleanAble) {
        if (!checkBack(map)) {
            return;
        }
    }

    clean(map);
}


int main() {
    // 첫째 줄 입력
    scanf("%d %d", &N, &M);

    // 둘째 줄 입력
    scanf("%d %d %d", &robot.r, &robot.c, &robot.d);

    // 셋째 줄 이후 입력
    vector<vector<int>> map(N, vector<int>(M, 0));
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            scanf("%d", &map[i][j]);
        }
    }

    clean(map);
    printf("%d", answer);

    return 0;
}

스터디 (2022-02-06 SUN 📚)

✅ 스터디에서 얻은 Tip

👉 후진 방향 설정하는 부분을 나와 한 분을 제외하고는 모두
(robot.d+2) % 4 와 같이 깔꼼하게 한 줄로 계산해오셨다
한 번 아니고 두 번 회전하면 그것이 곧 후진 방향 인 것을..
한 번 회전하는 것은 (robot.d+3)%4 로 잘 계산해놓고
후진 방향은 다소 일차원적으로 계산해놓은 나는.. 멍청이....

// 후진 방향 설정 내 코드
int backD;
if (robot.d == NORTH || robot.d == SOUTH) {
    backD = 2-robot.d; // 0:NORTH <-> 2:SOUTH
} 
else { // robot.d == EAST || robot.d == WEST
    backD = 4-robot.d; // 1:EAST <-> 3:WEST
}

👉 갑자기 선배님이 재귀를 쓴 이유가 있나요? 라고 질문하셔서 당황..
질문은 항상 쉬운 것이든 어려운 것이든 머리를 하얗게 만든다 헝헝..
아직 그만큼 자신이 없어서겠지 😥
사실상 입력 값이 3<=N,M<=50 으로 상당히 작아서
내맘대로 구현하면 되겠다~! 하고 짠 코드라서
의식의 흐름.. 이었습니다.. 라고 대답했는데 머쓱 💧

선배님도 사실상 이 문제는 입력 값이 작아서 상관 없지만
재귀는 최대 깊이가 커지면 문제가 될 수도 있기 때문에 꼭 염두에 두라고 말씀해주셨다

참고로 이 문제를 재귀로 풀면
최대 깊이는 모든 칸을 청소한다고 가정할 경우
지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽 이라는 조건 때문에
물론 정확히 N*M은 아니겠지만.. N*M 정도 라고 생각하면 될듯싶다