백준 14503번 로봇 청소기 (C++)

문제 링크 : www.acmicpc.net/problem/14503

14503번: 로봇 청소기

문제 풀이는 다음과 같다.

1. 회전하는 순서대로 북 -> 동 -> 남 -> 서를 회전방향에 저장한다.

 my[] = {-1,0,1,0}, mx[] = {0,1,0,-1}, 

2. 배열의 크기를 입력받고, 최대로 입력 가능한 크기 만큼의 int형 배열과 bool문형 배열을 선언한다.

3. 청소기의 위치와 방향을 입력 받는다. 이때 주의할 점이 맵이 0,0부터 시작한다는 점이다.

나는 계산을 편하게 하기 위해 0,0이 아닌 1,1부터 값을 입력받는 습관이 있는데, 이 문제는 로봇의 위치가 0,0을 기준으로 입력받기 때문에 이 점을 간과하면 틀릴 수 있다.

3. 배열의 값을 입력 받는다. 이때 배열의 값이 1일 경우 (=벽) 해당 위치의 bool문형 배열을 true로 표시해준다.

3. while문을 진행한다. 맨 먼저 오는 코드는 현재 위치를 방문한 적이 없을 경우 true로 표시해주고 정답을 +1해준다.

    while(true){
        if(!ch[y][x]){
            ans++;
            ch[y][x] = true;
        }
        ...

4. bool문 go의 값을 구해준다. go4가 의미하는 뜻은, 만약 4방위에서 하나라도 갈 수 있는 곳이 있다면 true를 반환, 그렇지 않다면 false를 반환한다.

bool go4(int y, int x){
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(!ch[ny][nx]) return true;
    }
    return false;
}

...
// while문 내부
bool go = go4(y,x);

5. go가 true로 나와서 4방위 중 한 방향이라도 갈 수 있다면, 문제에서 제시한데로 왼쪽방향으로 회전한다.

왼쪽 방향으로 진행했는데 해당 방향은 갈 수없는 방향(벽이거나, 이미 갔었거나)이라면 그대로 무시하고 if문을 종료해준다.

어차피 while문이 반복되어 또 다시 왼쪽방향으로 회전을 진행할 것이다.

        if(go){ // 네 방향 중 하나라도 칸이 있다면 회전부터 하기
            dir-=1;
            if(dir<0) dir = 3;
            ny = y+my[dir];
            nx = x+mx[dir];
            if(!ch[ny][nx]){
                y = ny;
                x = nx;
            }
            else;
        }

6. 반대로 go가 false가 나와서 4방위 중 한 곳이라도 갈 수 있다면, 후진을 할 수 있냐 마냐를 판단해야한다.

        else{ // 네 방향 모두 청소가 끝났다 -> 후진이 되냐 안되냐로 따지기
            if(dir<2) bdir=dir+2;
            else bdir=dir-2;
            ny = y+my[bdir];
            nx = x+mx[bdir];
            if(arr[ny][nx]==1) break;
            else{
                y = ny;
                x = nx;
            }
        }

이때 주의할 점이, 후진한 방향으로 방향을 저장해주는게 아니라 반대 방향으로 후진하되, 방향값은 기존의 방향을 그대로 유지해준다는 점이다.

만약 후진할 수 없다면 while문을 빠져나오면된다.

 

8. while문을 빠져나와 정답을 출력해준다.

#include <iostream>
#include <algorithm>
#define MAX 50
using namespace std;
// 북 동 남 서
int arr[MAX][MAX], ans=0, my[] = {-1,0,1,0}, mx[] = {0,1,0,-1}, y,x,ny,nx,m,n,dir,bdir;
bool ch[MAX][MAX];

bool go4(int y, int x){
    for(int i=0; i<4; i++){
        ny = y+my[i];
        nx = x+mx[i];
        if(!ch[ny][nx]) return true;
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    cin >> y >> x >> dir;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> arr[i][j]; // 빈칸 = 0, 벽 = 1
            if(arr[i][j]==1) ch[i][j] = true;
        }
    }
    while(true){
        if(!ch[y][x]){
            ans++;
            ch[y][x] = true;
        }
        bool go = go4(y,x);
        if(go){ // 네 방향 중 하나라도 칸이 있다면 회전부터 하기
            dir-=1;
            if(dir<0) dir = 3;
            ny = y+my[dir];
            nx = x+mx[dir];
            if(!ch[ny][nx]){
                y = ny;
                x = nx;
            }
            else;
        }
        else{ // 네 방향 모두 청소가 끝났다 -> 후진이 되냐 안되냐로 따지기
            if(dir<2) bdir=dir+2;
            else bdir=dir-2;
            ny = y+my[bdir];
            nx = x+mx[bdir];
            if(arr[ny][nx]==1) break;
            else{
                y = ny;
                x = nx;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}