[BOJ, C++]#14503_로봇 청소, BFS, 그래프 탐색, 너비 우선 탐색, 미로 찾기, 미로 찾기 유형

#1. 문제

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

 

---

 

#2. 풀이

 

1. BFS

[자료구조]#6_그래프

BFS는 그래프의 모든 정점을 탐색하는 방법 중 하나로, 현재 정점과 인접한 정점들을 우선적으로 탐색하는 방법입니다. 일반적으로, BFS는 큐 자료구조를 활용합니다.

 

2. 방향 설정만 조심해 주는 미로 찾기 유형!

1. 먼저, dy와 dx를 인덱스에 맞춰 북, 동, 남, 그리고 서쪽으로 값을 설정해 줍니다.
2. BFS 구현 시, 큐 자료구조에 { 현재 방향, {현재 좌표 Y, 현재 좌표 X} } 형식으로 선언하여 활용합니다.
3. BFS 구현 중 현재 방향을 기준으로 반 시계방향으로 (cd + 3 - i) 회전시키며 빈칸을 찾아줍니다.
4. 만약, 3번에서 빈 칸을 못 찾았을 경우, 방향을 유지하고 후진해주어 종료되는지, 혹은 다시 탐색을 진행할 것인지 결정해 줍니다.

 

---

 

#3. 코드

@@ -0,0 +1,106 @@
/*
    @링크: https://www.acmicpc.net/problem/14503
*   @문제: 로봇 청소기
*   @설명
        1. BFS 활용
        2. 미로 찾기 유형
*/

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> p;

int N, M;
int startY, startX, startD;
int ans = 1;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
vector<vector<int>> graph;

void bfs()
{
    //@ {방향, 현재 좌표}
    queue<pair<int, p>> q;
    graph[startY][startX] = 2;
    q.push({startD, {startY, startX}});

    while(!q.empty())
    {
        //@현재 좌표, 방향
        int cd = q.front().first;
        int cy = q.front().second.first;
        int cx = q.front().second.second;

        q.pop();

        //@청소하지 않은 빈 칸 여부
        bool bFoundUncleaned = false;
        //@반 시계 방향으로 90도 회전
        for(int i=0; i<4; i++)
        {
            int nd = (cd +3 - i)%4;
            int ny = cy + dy[nd];
            int nx = cx + dx[nd];

            //@경계 밖, 혹은 이미 청소한 칸, 벽일 경우
            if(ny < 0 || ny >= N || nx < 0 || nx >= M || graph[ny][nx] == 1 || graph[ny][nx] == 2) continue;

            //@청소 완료는 2로 표시
            graph[ny][nx] = 2;
            q.push({nd, {ny, nx}});
            bFoundUncleaned = true;
            ans++;
            break;
        }
        //@반대 방향으로
        if(!bFoundUncleaned)
        {
            //@방향을 유지하고 반대로 한 칸
            int nd = (cd+2)%4;
            int ny = cy + dy[nd];
            int nx = cx + dx[nd];

            //@경계 밖, 혹은 벽일 경우 종료
            if(ny < 0 || ny >= N || nx < 0 || nx >= M || graph[ny][nx] == 1)
            {
                return;
            }

            //@방향 유지, 후진
            q.push({cd, {ny,nx}}); 
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    graph.resize(N, vector<int>(M));

    //@시작 좌표, 방향
    cin >> startY >> startX >> startD; 

    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<M; ++j)
        {
            cin >> graph[i][j];
        }
    }

    //@bfs
    bfs();

    cout << ans;

    return 0;
}

 

---