14503번-로봇청소기

문제

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

14503번: 로봇 청소기

---

접근방법

1) 접근 사고

DFS 문제로 생각하여 DFS를 활용해서 문제를 풀었습니다. 문제의 구현량은 간단하나 DFS의 이해도가 높지 않다면 어려움을 겪을수 있는 문제입니다. 문제 에서 깊이우선탐색을 활용한 응용하는 부분이 들어있습니다. 보통 DFS는 최하단으로 내려간뒤 가지를 치면서 탐색을 하는데 이 문제의 경우 가지를 치는 방식이 기존 코드와 다르게 한 개의 시작점 부터만 가지치기가 됩니다. (코드 내부에서 return을 주면 이런식으로 탐색이 가능합니다).

 

2) 시간 복잡도

모든 경우를 탐색해야 하므로 O(v^2)입니다.

 

3) 배운 점

DFS를 응용을 배운거 같습니다.

 

4) PS

객체지향적으로 구현하고 싶어서 구조체를 선언한 뒤에 각 기능마다의 함수로 구분하였습니다.!

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 50;
int board[MAX][MAX];
int n, m;
 
//+3 % 4
//북동남서
//남서북동
int moveY[] = {-1,0,1,0};
int moveX[] = {0,1,0,-1};
int backY[] = {1,0,-1,0};
int backX[] = {0,-1,0,1};
 
struct Robot{
    int n, m, dir,cnt;
    pair<int,int> pos;
    vector<vector<int>> board;
    bool visited[MAX][MAX];
 
    Robot(int n, int m) : n(n), m(m), cnt(1), board(n,vector<int>(m)){}
 
    /*
     * 로봇의 위치값과 board의 정보를 입력받습니다.
     */
    void init()
    {
        memset(visited, false, sizeof visited); //?
        cin >> pos.first >> pos.second >> dir;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++)
                cin >> board[i][j];
        }
        visited[pos.first][pos.second] = true;
    }
 
    /*
     * 각 탐색마다 방향이 왼쪽으로 변환되어야 합니다. (i + 3) % 4 수식을 통해 각 탐색마다 방향을 변환시켜줍니다.
     * 그런뒤에 다음 로봇청소기의 탐색위치가 배열의 범위를 초과하지 않는다면 갯수를 추가 시키고 다음 탐색을 진행합니다.
     * 그 다음에 있는 return은 이 문제의 핵심과도 같습니다. 다른 문제와 다르게 DFS롤 통해 탐색 갈래길이 여러가지로 나가는게 아니라 탐색이 성공되면 그 방향으로만 나가야 합니다.
     * 그런 뒤에 돌아와서 시작점의 뒤에 방향을 확인해야 합니다. 그렇게 back 배열을 선언해서 탐색의 위치값 기준 뒤에 값들을 탐색시켜줍니다.
     * 만약 뒤의 이동이 벽이라면 종료시켜줍니다.
     */
    void search(int y, int x, int d)
    {
 
        for(int i = d; i > d - 4; i--)
        {
            int tmpd = (i + 3) % 4;
            int ny = y + moveY[tmpd];
            int nx = x + moveX[tmpd];
 
            if(ny < 0 || ny >= n || nx < 0 || nx >= m)
                continue;
            if(!visited[ny][nx] && board[ny][nx] == 0)
            {
                cnt++;
                visited[ny][nx] = true;
                search(ny, nx, tmpd);
                return;
            }
        }
 
        if(board[y + backY[d]][x + backX[d]] == 1)
            return;
        else
            search(y + backY[d], x + backX[d], d);
    }
};
 
int main(void)
{
    fastio;
    cin >> n >> m;
    Robot R(n, m);
    //구조체 변수에 입력값을 받습니다.
    R.init();
    //재귀함수를 통해서 청소구역의 갯수를 확인해줍니다.
    R.search(R.pos.first, R.pos.second, R.dir);
    cout << R.cnt <<"\n";
}