11주차(시뮬레이션) - [C++]백준14503 로봇 청소기

26 Nov 2022 in Study on Algorithm

백준14503 로봇 청소기 링크

문제

예제 입력

---

코드

#include<iostream>
using namespace std;

int map[50][50];
int n, m;
int r, c, d;
int answer = 0;

// 상 우 하 좌
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    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];
            if (map[i][j] == 1)
                map[i][j] = 2; // 미방문0 방문1 벽2
        }
    }
    int round = 0; // 탐색 횟수

    while (true) {
        if (map[r][c] == 0) { // 빈칸일 경우 방문, 다시 탐색, 정답 갱신
            map[r][c] = 1;
            round = 0;
            answer++;
        }

        d = (d + 3) % 4; // 0 3 2 1
        round++;

        if (round > 4) { // 더이상 탐색할때 없음 = 2-3, 2-4조건
            d = (d + 1) % 4;
            int back = (d + 2) % 4;
            int bdr = r + dr[back];
            int bdc = c + dc[back];

            if (0 > bdr || bdr >= n || 0 > bdc || bdc >= m) break;
            if (map[bdr][bdc] == 2) // 벽만 가지 못하니 종료
                break;
            else {
                r = bdr;
                c = bdc;
                round = 0;
                continue;
            }
        }
        int ndr = r + dr[d];
        int ndc = c + dc[d];

        if (0 > ndr || ndr >= n || 0 > ndc || ndc >= m) continue;
        if (map[ndr][ndc] > 0) continue;
        r = ndr;
        c = ndc;
    }

    cout << answer;
}

설명

이 문제는 시뮬레이션 알고르즘으로 다른 알고리즘이 미숙해도 풀 수 있으며, 구현실력을 크게 늘릴 수 있는 경험이 될 것입니다. 요즘 코딩테스트에서 특정 알고리즘보단 특정 조건에 맞는 코딩을 하는 시뮬레이션류의 문제가 많이 나오고 있는 것 같습니다. 문제를 풀때 팁은 아래와 같습니다.

 1. 모듈화(함수화)
 2. 데이터의 자료구조 
 3. 조건or행동의 데이터화

개인적인 생각으로는 먼저 성공 경우를 만들고 그 후에 특정 조건을 만드는게 좋을 것 같습니다. C++ STL(표준 템플릿 라이브러리)를 사용하여 구현하는 것보다 기본적인 개념을 토대로 까다로운 조건을 구현하는 것이 목적이라 그것에 맞게 구현했습니다. 먼저 현재 지점을 청소하고 바라보는 곳을 기준으로 계속 왼쪽(나선형)으로 나아가다가 더이상 탐색을 못하면 뒤로 돌아가서 놓친 곳을 청소하며 더이상 청소할 곳이 없으면 종료합니다. 알고리즘은 생각해본다면 BFS랑 비슷한 것 같습니다.

---

결과