백준 14503 - 로봇 청소기

문제

 

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

14503번: 로봇 청소기

 

 

풀이

 

문제에 나와있는 조건을 순서대로 구현하면 되는 문제이다. 청소할 공간이 있으면 이동하고 이동한 장소에서 다시 청소할 공간을 찾기 때문에 dfs 탐색을 이용해서 구현을 한다. 

 

이동은 현재 바라보는 방향 d를 기준으로 이루어지는데 0, 1, 2, 3이 각각 북, 동, 남, 서 를 의미한다. 다음에 청소할 공간은 d를 기준으로 왼쪽이기 때문에 다음과 같이 나타낼 수 있다.

go[0] : 현재 d가 0(북쪽) 이므로 다음으로 확인할 공간은 서쪽이 된다. (현재 i,j + (0, -1))

go[1] : 현재 d가 1(동쪽) 이므로 다음으로 확인할 공간은 북쪽이 된다. (현재 i,j + (-1, 0))

go[2] : 현재 d가 2(남쪽) 이므로 다음으로 확인할 공간은 동쪽이 된다. (현재 i,j + (0, 1))

go[3] : 현재 d가 3(서쪽) 이므로 다음으로 확인할 공간은 남쪽이 된다. (현재 i,j + (1,0))

 

다음번에 이동할 공간에서 청소를 해야하면 dfs 탐색을 실행하고 return을 해준다.

 

 

4방향 모두 청소를 할 수 없거나 이미 청소를 한 경우라면 현재 방향 d를 기준으로 뒤로 움직여준다. 

back[0] : 현재 d가 0(북쪽) 이므로 뒤로 이동하는 좌표는 남쪽 이동과 같다. (현재 i,j + (1, 0))

back[1] : 현재 d가 1(동쪽) 이므로 뒤로 이동하는 좌표는 서쪽 이동과 같다. (현재 i,j + (0, -1))

back[2] : 현재 d가 2(남쪽) 이므로 뒤로 이동하는 좌표는 북쪽 이동과 같다. (현재 i,j + (-1, 0))

back[3] : 현재 d가 3(서쪽) 이므로 뒤로 이동하는 좌표는 동쪽 이동과 같다. (현재 i,j + (0, 1))

 

뒤로 이동할 수 있으면 움직인 후 dfs 탐색을 실행하고, 움직일 수 없다면 탐색을 종료한다.

 

코드

 

#include <iostream>
#include <cstring>
 
using namespace std;
 
int N, M;
int r, c, d;
int graph[52][52];
bool visit[52][52];
int result;
 
pair<int, int> go[4] = {{0,-1}, {-1,0}, {0,1}, {1,0}};
pair<int, int> back[4] = {{1,0}, {0,-1}, {-1,0}, {0,1}};
 
int get()
{
    if (d - 1 < 0) return 3;
    else return d-1;
}
 
void dfs(int x, int y)
{
    if (!visit[x][y])
    {
        visit[x][y] = true;
        result++;
    }
 
    for (int i=0; i<4; i++)
    {
        int next_x = x+go[d].first;
        int next_y = y+go[d].second;
        d = get();
        if (!visit[next_x][next_y] && !graph[next_x][next_y])
        {
            dfs(next_x, next_y);
            return;
        }
    }
 
    if (graph[x+back[d].first][y+back[d].second]) return;
    else dfs(x+back[d].first, y+back[d].second);
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> M;
    cin >> r >> c >> d;
 
    memset(graph, 1, sizeof(graph));
 
    for (int i=1; i<=N; i++)
        for (int j=1; j<=M; j++)
            cin >> graph[i][j];
    
    dfs(r+1, c+1);
    cout << result;
    return 0;
}