[Baekjoon] #14503 - 로봇 청소기

문제

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

로봇 청소기가 있는 방은 $N \times M$ 크기의 직사각형으로 나타낼 수 있으며, $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 $(r, c)$로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 $(0, 0)$, 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 $(N-1, M-1)$이다. 즉, 좌표 $(r, c)$는 북쪽에서 $(r+1)$번째에 있는 줄의 서쪽에서 $(c+1)$번째 칸을 가리킨다. 처음에 빈 칸은 전부 청소되지 않은 상태이다.

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

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

입력

첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽, $1$인 경우 동쪽, $2$인 경우 남쪽, $3$인 경우 서쪽을 바라보고 있는 것이다.

셋째 줄부터 $N$개의 줄에 각 장소의 상태를 나타내는 $N \times M$개의 값이 한 줄에 $M$개씩 입력된다. $i$번째 줄의 $j$번째 값은 칸 $(i, j)$의 상태를 나타내며, 이 값이 $0$인 경우 $(i, j)$가 청소되지 않은 빈 칸이고, $1$인 경우 $(i, j)$에 벽이 있는 것이다. 방의 가장 북쪽, 가장 남쪽, 가장 서쪽, 가장 동쪽 줄 중 하나 이상에 위치한 모든 칸에는 벽이 있다. 로봇 청소기가 있는 칸은 항상 빈 칸이다.

출력

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

---

풀이

풀이과정

헤헤

풀기 전에

귀여운 로봇청소기 아리스를... 보고가세요

나는 좌표와 관련된 탐색 문제가 나올 때마다 이 인덱스 유효범위 검사가 가장 헷갈린다.
배열의 기본 인덱스가 0부터 시작하기 때문인 것이 원인인데, 그래서 마지막이 N인지 N-1인지 N+1인지 헷갈릴 때가 굉장히 많다...
이게 나의 가장 큰 약점이다. 눈에 보이지 않는 것을 잘 생각해내지 못한다.
그래서 프론트가 잘 맞는 것일 수도...
그래도 연습하다보면 늘겠지!!! 화이팅

확실히 알고리즘 써서 푸는 것보다는 빡구현이 나한테 더 잘 맞고 재밌는 것 같다.
골드 문제를 거의 처음 풀어보는데도 어렵지 않게 풀 수 있었다.

dx와 dy를 쓰는 등의 테크닉은 어쩔 수 없이 문제를 많이 풀어보면서 터득해나가야 하는 것같다.

최종 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

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

//방향을 반시계 방향으로 90도 회전시키는 함수
void turn(){
    //0이면 3으로
    if(dir==0)
        dir = 3;
    else   
        dir--;

    //dir = (dir + 3) % 4; // 반시계로 90도 << 지피티가 이렇게 줄여줬지만.. 내 머리로는 이걸 떠올려낼 수 없을 듯하다
}
// 앞 칸 좌표 반환
pair<int, int> checkFront(int x, int y) {
    return {x + dx[dir], y + dy[dir]};
}

// 뒤 칸 좌표 반환
pair<int, int> checkBack(int x, int y) {
    int backDir = (dir + 2) % 4; // 뒤 방향 << 이것도 GPT발..
    return {x + dx[backDir], y + dy[backDir]};
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  
    int N, M;
    cin >> N >> M;
    int x, y;
    cin >> x >> y >> dir;

    vector<vector<int>> map(N, vector<int>(M));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> map[i][j];

    int cnt = 0;
    while (true) {
        // 1. 현재 칸 청소
        if (map[x][y] == 0) {
            map[x][y] = -1;
            cnt++;
        }

        bool moved = false;

        // 2. 주변 4칸 확인
        for (int i = 0; i < 4; ++i) {
            turn(); //문제와 다르게 그냥 아묻따 turn()을 해줘도 되는 이유는, 어차피 사방4칸에 청소할 칸 없으면 4번 회전해서 기존 방향으로 돌아오기 때문에.
            pair<int, int> front = checkFront(x, y);
            int fx = front.first, fy = front.second;

            if (fx < 0 || fy < 0 || fx >= N || fy >= M) continue;

            if (map[fx][fy] == 0) {
                x = fx;
                y = fy;
                moved = true;
                break;
            }
        }

        if (moved) continue;

        // 3. 후진
        pair<int, int> back = checkBack(x, y);
        int bx = back.first, by = back.second;

        if (bx < 0 || by < 0 || bx >= N || by >= M || map[bx][by] == 1)
            break; // 벽이면 종료
        else {
            x = bx;
            y = by;
        }
    }

    cout << cnt << "\n";
    return 0;
}

의문점

의문점은 아니지만... GPT 정말 대단하다
내가 코드를 100줄로 쓰면 10줄로 줄여준다...
인간은 인공지능을 이길 수 있을까?..