ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 14503.로봇청소기
    알고리즘/백준 BAEK JOON 2020. 6. 1. 00:51

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

     

    14503번: 로봇 청소기

    로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

    www.acmicpc.net

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

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

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

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

     

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

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

     

     


     

    < Code 설명 >

     

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <deque>
    #define MAX 51
     
    using namespace std;
     
    // 북 동 남 서
    int dx[4= { -1010 };
    int dy[4= { 010-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<intint>> 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;
    }
    cs

     

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1074.Z  (0) 2020.08.15
    15686.치킨배달  (0) 2020.08.11
    14503.로봇청소기  (0) 2020.06.01
    16236.아기상어  (1) 2020.05.31
    14890.경사로  (0) 2020.05.28
    1697.숨바꼭질  (0) 2020.05.27

    댓글 0

Designed by Tistory.