[BOJ] 14503번 로봇 청소기 문제풀이 (C++)

2017.10.9에 쓰여진 글 입니다.

---

문제링크

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

풀이방법

시뮬레이션 문제로 시키는 대로 하면 된다.

코드 길이도 길지 않음.

풀이방식은 2가지로 풀어봤음.

1번은 재귀 2번은 큐

최대한 다양한 방법으로 풀어보는것이 도움이 되는듯하다.

 

문제이해가 어려우신 분들을 위한 테스트케이스 2번째꺼 진행과정이니 참고..

흑백1 == 벽

노란빈칸 == 청소안된구역

빨간1 == 시작 지점

숫자 == 로봇청소기 이동순서 

 

 

소스코드

소스코드1 (재귀 ver)

#include <iostream>
 
using namespace std;
 
enum DIR { NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3 };
enum { BLANK = 0, WALL = 1, CLEAR = 2 };
 
int N, M;               //세로 가로 길이
int map[50][50];        //맵
int Answer;             //정답
int dx[] = { -1,0,1,0 };//방향 복동남서
int dy[] = { 0,1,0,-1 };
 
void solve(int cur_x, int cur_y, int cur_dir, int cur_cnt)
{
    if (cur_cnt >= 4) {
        //cur_dir = ((cur_dir - 1) + 4) % 4;    //현재방향의 왼쪽방향설정
        int new_x = cur_x - dx[cur_dir];    //현재바라보는방향에서 후진
        int new_y = cur_y - dy[cur_dir];
        if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < M        //범위안에있고
            &&map[new_x][new_y] == CLEAR)                      //청소된구역이면
            solve(new_x, new_y, cur_dir, 0);
        return;
    }
    map[cur_x][cur_y] = CLEAR;
    int new_dir = ((cur_dir - 1) + 4) % 4;    //현재방향의 왼쪽방향설정
    int new_x = cur_x + dx[new_dir];
    int new_y = cur_y + dy[new_dir];
    if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < M) {
        if (map[new_x][new_y] == BLANK)
            solve(new_x, new_y, new_dir, 0);
        else if (map[new_x][new_y] == WALL || map[new_x][new_y] == CLEAR)
            solve(cur_x, cur_y, new_dir, cur_cnt + 1);
    }
}
 
int main()
{
    Answer = 0;
    cin >> N >> M;
    int cur_x, cur_y, cur_dir;
    cin >> cur_x >> cur_y >> cur_dir;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> map[i][j];
    solve(cur_x, cur_y, cur_dir, 0);                        //solve함수 호출
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j] == CLEAR)
                Answer++;            //청소구역 체크하자
    cout << Answer << endl;            //정답출력
 
    return 0;
}

소스코드2 (큐 ver)

#include <iostream>
#include <queue>
 
using namespace std;
 
enum DIR { NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3 };
enum { BLANK = 0, WALL = 1, CLEAR = 2 };
 
int N, M;                //세로 가로 길이
int map[50][50];        //맵
queue < pair < pair < int, int >, int > > q;
//(좌표x,y),방향
int Answer;                //정답
int dx[] = { -1,0,1,0 };//방향 복동남서
int dy[] = { 0,1,0,-1 };
 
void solve()
{
    while (!q.empty()) {        //큐빌때까지 돌림
        int cur_x = q.front().first.first;    //현재좌표 저장
        int cur_y = q.front().first.second;
        int cur_dir = q.front().second;        //현재방향저장
        q.pop();                            //큐빼주고
        map[cur_x][cur_y] = CLEAR;            //현재좌표 청소해줌
        int tmp_cnt = 0;                    //임시 카운트 0으로
        int tmp_dir = ((cur_dir - 1) + 4) % 4;    //임시방향(현재방향의 왼쪽방향설정)
        for (int i = 0; i < 4; i++) {
            int new_dir = ((tmp_dir - i) + 4) % 4;    //차례대로 왼쪽방향으로 돌림
            int new_x = cur_x + dx[new_dir];
            int new_y = cur_y + dy[new_dir];
            if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < M) {        //범위안에있을때
                if (map[new_x][new_y]==BLANK) {                            //빈공간이면
                    q.push(make_pair(make_pair(new_x, new_y), new_dir));//큐에넣어줌
                    break;                                                //탈출
                }
                else if (map[new_x][new_y] == WALL || map[new_x][new_y] == CLEAR)
                    tmp_cnt++;    //벽이거나 청소된구역이면 임시카운트증가
            }
        }
        if (tmp_cnt == 4) {                        //임시카운트가 4면 이동 못한것임
            int new_x = cur_x - dx[cur_dir];    //현재바라보는방향에서 후진
            int new_y = cur_y - dy[cur_dir];
            if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < M        //범위안에있고
                &&map[new_x][new_y]==CLEAR)                            //청소된구역이면
                q.push(make_pair(make_pair(new_x, new_y), cur_dir));//큐에넣어줌(벽이면 이동못하는거고 끝)
        }
    }
}
int main()
{
    Answer = 0;
    cin >> N >> M;
    int cur_x, cur_y, cur_dir;
    cin >> cur_x >> cur_y >> cur_dir;
    q.push(make_pair(make_pair(cur_x, cur_y), cur_dir));    //큐에 시작좌표 넣어줌
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> map[i][j];
    solve();                        //solve함수 호출
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j] == CLEAR)
                Answer++;            //청소구역 체크하자
    cout << Answer << endl;            //정답출력
 
    return 0;
}