[C++] 14503 - 로봇청소기 (골드5)

1. 문제 설명

 

14503번: 로봇 청소기

---

2. 아이디어

 

멘토 활동을 하다가 삼성 기출은 어떤 식으로 나오나 싶어서 몇 문제 풀어보던 중 발견한 문제.

 

문제에 모든 로직을 제공해줘서, 사실상 코드로 구현만 하면 되는 간단한 문제다.

이 문제가 쉽게 풀리지 않는다면 구현력 자체가 떨어지거나, 심한 경우엔 독해력이 떨어지는 것.

조롱의 의미가 아니라 후자의 경우면 문제를 꼼꼼하게 읽고, 논리적으로 분석하려는 노력을 남들보다 몇 배로 연습한다면 충분히 극복 가능하다.

 

각각의 로직을 어떻게 처리할지, 어떤 정보가 처리할지를 생각해보면 된다.

우선, 내가 이동할 방향의 공간은 3가지 경우가 있다.

  1. 청소가 안 된 곳

  2. 청소가 끝난 곳

  3. 벽

그래프에 이 세 공간을 구분할 수 있도록 처리해주면 된다.

예를 들어서, 청소가 안 된 곳은 0, 청소를 했다면 -1, 벽이면 1 이 정도로?

 

그 다음은 현재 바라보고 있는 방향값을 기준으로 MOD 연산으로 방향을 컨트롤 해주면 될 것이고,

이동 가능하다면, 재귀함수를 호출하여 계속 이동하면 된다.

단, 벽에 막힌 경우가 있을 수 있으므로 4방향 탐색 이후에 후진하는 경우도 추가하면 문제는 쉽게 풀린다.

 

재귀를 탈출하는 과정에서 결과가 꼬일 수 있는데, 그냥 exit 함수를 호출해서 프로그램을 종료시켜 버렸다.

---

3. 코드

 

#include <iostream>

using namespace std;

int n, m; 
int map[51][51];
int vector[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void dfs(int r, int c, int d, int cnt) {
    map[r][c] = -1;

    for (int i=0; i<4; i++) {
        int nxt_d = (d+3-i) % 4;
        int nxt_r = r + vector[nxt_d][0];
        int nxt_c = c + vector[nxt_d][1];

        if (0 <= nxt_r && nxt_r < n && 0 <= nxt_c && nxt_c < m && map[nxt_r][nxt_c] == 0)
            dfs(nxt_r, nxt_c, nxt_d, cnt+1);
    }

    int back_idx = (d+2) % 4;
    int back_r = r + vector[back_idx][0];
    int back_c = c + vector[back_idx][1];
    if (0 <= back_r && back_r < n && 0 <= back_idx && back_idx < m) {
        if (map[back_r][back_c] == 0 || map[back_r][back_c] == -1) 
            dfs(back_r, back_c, d, cnt); 
        else {
            cout << cnt << "\n";
            exit(0); 
        }
            
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int r, c, d; 
    cin >> n >> m >> 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, 1);
    return 0;
}