백준 14503 : 로봇 청소기

문제 링크입니다 https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

문제에서 주어진 조건 그대로 만! 차례 차례 구현하면 되는 문제였습니다.

주어진 맵을 따로 건드리지 않고 청소를 한 곳은 bool형 check배열을 true로 만들면서 진행하였습니다.

 

구체적인 설명은 주석 참고해주세요! 밑에 주석 없는 코드도 포스팅 했습니다.

 

 

[소스코드 + 주석]

 

// [백준] 삼성 SW 역량 테스트 기출 문제 : 로봇 청소기(14503)
 
#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 50 + 10;
 
// 좌표와 방향을 저장하기 위한 구조체
struct p {
    int y, x, dir;
};
queue <p> q;
bool check[MAX][MAX];    // bfs에서 visit 체크하는 배열
int n, m, r, c, d, map[MAX][MAX];
 
const int dy[] = { -1, 0, 1, 0 };    // 0인 경우 북쪽, 2인 경우 남쪽
const int dx[] = { 0, 1, 0, -1 };    // 1인 경우 동쪽, 3인 경우 서쪽
 
// 좌표와 방향을 인자로 받아서 p type으로 바꿔주는 함수
p make_p(int y, int x, int dir) {
    p temp;
 
    temp.y = y, temp.x = x, temp.dir = dir;
    return temp;
}
 
// 입력받는 함수
void _input(void) {
    scanf("%d%d%d%d%d", &n, &m, &r, &c, &d);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &map[i][j]);
}
 
// 로봇 청소기의 현재 위치부터 청소를 하는 함수
int bfs(int y, int x, int dir) {
 
    int clean_cnt = 0;    // 로봇 청소기가 청소한 칸을 세어주는 변수 바로 선언
 
    q.push(make_p(y, x, dir));
 
    while (!q.empty()) {
        p cur = q.front();
        q.pop();
 
        int dd, yy, xx, d = cur.dir;
        
        // 후진 할 때 청소 했던곳을 재방문 할 수도 있어서 이미 청소가 되어있으면
        // clean_cnt를 늘리면 안됩니다!
        if (!check[cur.y][cur.x]) clean_cnt++;
 
        check[cur.y][cur.x] = true;    // 문제 조건 1번, 현재 위치를 바로 청소해버립니다
 
        bool flag = false;
        for (int i = 0; i < 4; i++) {
            
            // 문제 조건 2번, 현재 방향을 기준으로 왼쪽 방향을 봐야한다
            // 북쪽(0)을 보고있다면 서쪽(3)을, 서쪽(3)을 보고있다면 남쪽(2)을, 
            // 남쪽(2)을 보고있다면 동쪽(1)을, 동쪽(1)을 보고있다면 북쪽(0)을 봐야하기 때문에
            dd = (d + 3) % 4;
 
            yy = cur.y + dy[dd], xx = cur.x + dx[dd];    // 그 다음칸의 좌표
 
            // 문제 조건 2 - A번, 왼쪽 방향에 청소 아직 안했으면 바로하셈
            if (0 <= yy && yy < n && 0 <= xx && xx < m && map[yy][xx] == 0 && !check[yy][xx]) {
                
                q.push(make_p(yy, xx, dd));
                flag = true;
                break;
            }
            else d = dd;
        }
 
        if (flag) continue;
        else {
            // 위에 flag가 false라는 것은 네 방향 모두 이미 청소가 되어있거나 벽이라는 뜻
            
            dd = (cur.dir + 2) % 4;    // 후진 하려면 +2를 해줘야하네...
 
            yy = cur.y + dy[dd], xx = cur.x + dx[dd];
 
            // 문제 조건 2 - D번, 뒤쪽 방향이 벽이라 후진도 모다네
            if (map[yy][xx] || yy < 0 || yy >= n || xx < 0 || xx >= m) return clean_cnt;
 
            // 문제 조건 2 - C번, 네 방향 모두 이미 청소가 되어있거나 벽이라면 후진해라
            else q.push(make_p(yy, xx, cur.dir));    // 방향은 그대로하고 후진해야함!
        }
    }
}
 
void solve(void) {
    _input();
    printf("%d", bfs(r, c, d));
}
 
int main(void) {
    solve();
    return 0;
}

 

 

[주석 없는 소스코드]

 

#include<cstdio>
#include<queue>
using namespace std;
const int MAX = 50 + 10;
 
struct p {
    int y, x, dir;
};
queue <p> q;
bool check[MAX][MAX];
int n, m, r, c, d, map[MAX][MAX];
 
const int dy[] = { -1, 0, 1, 0 };    
const int dx[] = { 0, 1, 0, -1 };    
 
p make_p(int y, int x, int dir) {
    p temp;
 
    temp.y = y, temp.x = x, temp.dir = dir;
    return temp;
}
 
void _input(void) {
    scanf("%d%d%d%d%d", &n, &m, &r, &c, &d);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            scanf("%d", &map[i][j]);
}
 
int bfs(int y, int x, int dir) {
 
    int clean_cnt = 0;    
    q.push(make_p(y, x, dir));
 
    while (!q.empty()) {
        p cur = q.front();
        q.pop();
 
        int dd, yy, xx, d = cur.dir;
        if (!check[cur.y][cur.x]) clean_cnt++;
        check[cur.y][cur.x] = true;    
 
        bool flag = false;
        for (int i = 0; i < 4; i++) {
            dd = (d + 3) % 4;
            yy = cur.y + dy[dd], xx = cur.x + dx[dd];
 
            if (0 <= yy && yy < n && 0 <= xx && xx < m && map[yy][xx] == 0 && !check[yy][xx]) {
                q.push(make_p(yy, xx, dd));
                flag = true;
                break;
            }
            else d = dd;
        }
        if (flag) continue;
        else {
            dd = (cur.dir + 2) % 4;    
            yy = cur.y + dy[dd], xx = cur.x + dx[dd];
 
            if (map[yy][xx] || yy < 0 || yy >= n || xx < 0 || xx >= m) return clean_cnt;
            else q.push(make_p(yy, xx, cur.dir));    
        }
    }
}
 
void solve(void) {
    _input();
    printf("%d", bfs(r, c, d));
}
 
int main(void) {
    solve();
    return 0;
}