c++ 14503 로봇 청소기 (BFS)

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

14503번: 로봇 청소기

 

풀이 방법

지문의 조건처럼 왼쪽으로 이동할 수 있으면 이동 후 청소를 하며 방향을 전환해야 한다.

 

그래서 각 방향마다 dx,dy 배열을 어디서 탐색할지 바꾸어 주어야 하는데 dir 을 이용하여 dir + i로 북 , 서 , 남  ,동을 순서대로 탐색하도록 하였고 만약 청소를 할 수 있다면 청소를 한 후 break 문을 통해서 반복을 끝내주고 청소를 하지 못했다면 후진을 하여 뒤에 벽이 나올 때 까지 다른 청소 할 수 있는지 확인을 해야 한다.

 

나의 경우 동서남북 방향과 왼쪽 오른쪽이 자주 사용되다보니 북 동 남 서 방향으로 진행을 했어서 한참 해맸다 마지막에 그래서 올바르게 고쳐주어서 맞게 되었다

 

if(d==1){

d=3;

}else if(d==3){

d=1;

}

이 바로 방향을 바꾼 부분이다.

 

조금 헷갈린 문제였었다.

 

 

#include <bits/stdc++.h>
using namespace std;

int n, m, r, c, d;

int arr[55][55];
int ch[55][55];

int dx[4] = {0, 1, 0, -1}; // 북 (0,1,0,-1)  서 (1,0,-1,0) 남 (0,-1,0,1) 동 (-1,0,1,0)
int dy[4] = {-1, 0, 1, 0}; // 북 (-1,0,1,0)  서 (0,1,0,-1) 남 (1,0,-1,0) 동 (0,-1,0,1)

queue<tuple<int, int, int, int>> q;

bool func(int x, int y)
{
    if (ch[x][y] > 0 || arr[x][y] == 1)
        return true;

    return false;
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> r >> c >> d;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
        }
    }

    if (d == 1)
    {
        d = 3;
    }
    else if (d == 3)
    {
        d = 1;
    }

    ch[r][c] = 1;
    q.push({r, c, d, 1});

    int ans = 0;

    while (!q.empty())
    {
        tuple<int, int, int, int> cur = q.front();
        q.pop();

        int x = get<0>(cur);
        int y = get<1>(cur);
        int dir = get<2>(cur);
        int cnt = get<3>(cur);

        // cout << x << " " << y << " " << dir << "\n";

        bool isFind = 0;

        for (int i = 0; i < 4; i++)
        {
            int num = (i + dir) % 4;
            int nx = x + dx[num];
            int ny = y + dy[num];

            if (func(nx, ny))
            {
                continue;
            }
            ch[nx][ny] = cnt + 1;
            q.push({nx, ny, (dir + i + 1) % 4, cnt + 1});
            isFind = 1;
            break;
        }

        if (isFind == 0)
        {
            int num = (dir + 1) % 4;
            int nx = x + dx[num];
            int ny = y + dy[num];

            if (arr[nx][ny] == 1)
                continue;

            q.push({nx, ny, dir, cnt});
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (ch[i][j] >= 1)
                ans++;
            // cout << ch[i][j] << " ";
        }
        // cout << "\n";
    }
    cout << ans;
}