[ 백준 14503 - 로봇청소기 ]

### 문제 분석

1. 처음에는 반복문으로 구현하려고 시도 했으나 반복문으로 구현하려다 보니 오히려 더 복잡해졌다.
2. 이후 재귀(DFS)를 이용하는 쪽으로 문제푸는 방식을 수정했다.

시간 복잡도

최악의 경우 로봇 청소기가 모든 곳을 청소해야 하기 때문에 시간 복잡도는 O(NM)이다

구현

왼쪽 및 반대 방향 구하기 ( Modulo 성질 이용 )

Modulo의 성질은 알아두면 매우 유용한 성질인것 같다. 특히 cyclic 하게 무언가를 반복해야할 때 매우 유용한것 같다.

헤맸던 부분

처음에 문제를 풀이 할 때 반복문을 이용하고자 했으나 반복문을 이용해서 풀려고 하니 이해가 코드의 흐름이 지저분해지고 잘 이해가 가지 않았다.

재귀를 이용해서 풀었을때는 반복문을 이용했을때 보다는 코드를 직관적으로 작성할 수 있었다.

얻은 것

1. 반복과 재귀의 복습

2. Modulo의 활용

전체 코드 [ 내 코드 ]

#include <iostream>
#include <algorithm>

using namespace std;

void init(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}

int Board[52][52];
int Board_origin[52][52];
int Clean[52][52];
int Row, Col;
int Row_cor, Col_cor;
int Dir;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, 1, 0,-1};

// 0 : 북
// 1 : 동
// 2 : 남
// 3 : 서

void print_clean(){
    cout << "\n";
    for(int i = 0; i < Row; i++){
        for(int j = 0 ; j < Col; j++){
            cout << Clean[i][j] << " ";
        }
        cout << "\n";
    }
}

int get_left_dir(int dir){
    return (dir + 3) % 4;
}// 왼쪽 방향을 반환

int get_opposite_dir(int dir){
    return (dir + 2) % 4;
}// 반대 방향을 반환

int impossible = 0;
void clean(const int cur_row , const int cur_col, const int cur_dir, const int c){

    if(impossible) return;
    if(c) Clean[cur_row][cur_col] = c;

    int left_dir = cur_dir;
    for(int i = 0 ; i < 4; i++){
        left_dir = get_left_dir(left_dir);

        int nr = cur_row + dx[left_dir];
        int nc = cur_col + dy[left_dir];

        if(nr < Row && nc < Col && nc >= 0 && nr >= 0
        && Board[nr][nc] == 0
        && Clean[nr][nc] == 0
        ){
            clean(nr,nc,left_dir,1);
            return;
        }
    }

    int opp_dir = get_opposite_dir(cur_dir);
    int opp_r = cur_row + dx[opp_dir];
    int opp_c = cur_col + dy[opp_dir];

    if( Board[opp_r][opp_c] != 1 ) {
        clean(opp_r, opp_c, cur_dir, 0);
        // clean에 들어가는 0과 1은 해당칸을 치울지 말지를 결정
        // 후진할 경우 해당 칸을 1로 바꾸어주면 안되기 때문에 더 확실하게 해주기 위해서 이렇게 해주었다.
        return;
    }else{
        impossible = 1;
        return;
    }
}

void get_input(){
    cin >> Row >> Col;
    cin >> Row_cor >> Col_cor >> Dir;

    for(int i = 0; i < Row; i++){
        for(int j = 0 ; j < Col; j++){
            int input;
            cin >> input;
            Board[i][j] = input;
            Board_origin[i][j] = input;
        }
    }
}

int main(void){
    init();
    get_input();
    clean(Row_cor, Col_cor, Dir, 1);
    int ans = 0 ;
    for(int i = 0 ; i < Row; i++){
        for(int j = 0 ; j < Col; j++){
            if(Clean[i][j]) ans++;
        }
    }

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

느낀점

아직 구현력이 많이 부족한것 같다.

참조

반복문을 이용한 코드

참조 코드
정리를 상당히 깔끔하게 잘 해놓으셔서 이해하기 쉽게 되어있다.

재귀를 이용한 코드

참조 코드
거의 대부분의 사람들이 DFS로 문제를 해결했는데 반복문으로 문제를 상당히 깔끔하게 해결하셨다.