14503.로봇청소기

이번에 풀어볼 문제는 백준 14503 로봇청소기이다. 시뮬레이션 분류의 문제이며 문제 이해만 잘하면 풀 수 있는 문제이다.

14503번: 로봇 청소기

하지만 제대로 이해못하거나 설계를 잘못하면 미궁속에 빠져서 푼거 또 풀고 푼거 또 풀게된다...

나 역시 1주일전에 풀다가 틀린 부분을 못찾아서 1주일 후에 다시 푸는데 성공했다(그사이에 늘긴 늘었다보다..)

내가 실수했던 부분은 후진에 대한 내용이다. 4방향모두 갈곳이 없을 때 청소한 곳을 지나갈 수 있는 방법은 후진뿐인데

잘못이해해서 후진말고도 갈 수 있는거 아닌가 라고 착각했다.

 

역시나 설계가 제일 중요하다!

=> 이제는 구현은 허접하게라도 할 수있는 레벨이므로 설계를 잘해야한다.

 

 

---

 

< Code 설명 >

 

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#define MAX 51
 
using namespace std;
 
// 북 동 남 서
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
 
int n, m;
int r, c, d;
int cnt = 0; // 탐색횟수
int ans = 1; // 정답저장변수
int map[MAX][MAX];   // 맵이 저장되는 배열
int check[MAX][MAX]; // 청소한 곳 체크할 배열
 
int before_x, before_y; // 3방향 뒤져서 막혀있으면 되돌아갈 좌표
int tmp_x, tmp_y; // 임시 좌표가 저장될 변수
 
deque<pair<int, int>> t;// 방향이 저장된 deque
 
void showme(){ // 보여줘 배열상태를!!
    cout << "\n";
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            printf("%2d ", map[i][j]);
        }
        cout << "\n";
    }
    cout << "\n";
    cout << "\n";
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            printf("%2d ", check[i][j]);
        }
        cout << "\n";
    }
    cout << "\n";
}
 
void turn_set(){ // 청소기 시작방향 선정될 함수
    for (int i = 0; i < 4; i++) // 기준 방향 순차적 저장
        t.push_back(make_pair(dx[i], dy[i]));
    
    for (int i = 0; i < d; i++){ // 시작방향 셋팅
        t.push_back(t.front());
        t.pop_front();
    }
}
 
void turn(){ // 방향 전환 함수
    t.push_front(t.back());
    t.pop_back();
}
 
 
 
void search(int x, int y){
    turn(); // 좌측을 방향 전환
    int ax = x + t.front().first; //좌측 x좌표 
    int ay = y + t.front().second;//좌측 y좌표
    if (ax <= 0 || ay <= 0 || ax >= n || ay >= m){ //범위확인
        cnt += 1; // 청소할 수 없는 경우로 탐색 숫자 +1
        return;
    }
 
    // 청소가 가능한 경우 (벽이 아니면서 청소안된구역)
    if (map[ax][ay] != 1 && check[ax][ay] == 0){ 
        ans += 1; // 청소횟수 증가
        check[ax][ay] = ans; // 청소 횟수 저장
        tmp_x = ax; // 청소한 x좌표 저장
        tmp_y = ay; // 청소한 y좌표 저장
        cnt = 0;    // 청소했으니 탐색 숫자 초기화
    }
    else // 청소가 불가능하면 탐색 +1 그 방향 회전 후 탐색은 다시돌아가서하게됨
        cnt += 1;
}
 
 
int main(){
    freopen("14503.txt", "r", stdin);
    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];
        }
    }
    tmp_x = r; // 시작 x좌표 저장
    tmp_y = c; // 시작 y좌표 저장
    check[r][c] = 1; //시작 좌표 청소 
    turn_set();  // 방향 설정
    while (true){
        search(r, c);// 탐색 
        //showme();
        r = tmp_x; // 탐색 후 청소된 x좌표 저장
        c = tmp_y; // 탐색 후 청소된 y좌표 저장
        if (cnt == 4){ // 4방향 탐색 후 갈곳이 없다면 후진!
        // 후진은 가려는 방향의 반대이므로 반대로 계산하는 로직
            if (t.front().first < 0 && t.front().second == 0){ 
                r += -1 * t.front().first;
            }
            else if (t.front().first > 0 && t.front().second == 0){
                r -= t.front().first;
            }
            else if (t.front().first == 0 && t.front().second < 0){
                c += -1 * t.front().second;
            }
            else if (t.front().first == 0 && t.front().second > 0){
                c -= t.front().second;
            }
            if (map[r][c]==1) // 4방향 탐색 후 후진시에 벽이나오면
                break; // 시동끈다
            cnt = 0; // 후진했으니 탐색 숫자 초기화
            tmp_x = r; // 후진한 x좌표 저장
            tmp_y = c; // 후진한 y좌표 저장
        }
    }
 
    cout << ans << "\n";
    return 0;
}