반응형
https://www.acmicpc.net/problem/14503
로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
로봇 청소기가 있는 방은 N X M 크기의 직사각형으로 나타낼 수 있으며, 1 X 1 크기의 정사각형 칸으로 나누어져 있다.
각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0,0) 가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다. 즉, 좌표 (r,c) 는 북쪽에서 (r + 1)번째에 있는 줄의 서쪽에서 (c + 1)번째 칸을 가리킨다.
처음에 빈 칸은 전부 청소되지 않은 상태이다. 로봇 청소기는 다음과 같이 작동한다.
- 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
- 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
- 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
- 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
- 반시계 방향으로 90도 회전한다.
- 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
- 1번으로 돌아간다.
#include <iostream>
#include<memory.h>
int N, M;
int r[50][50];
int v[50][50];
//d = 0 북
//d = 1 동
//d = 2 남
//d = 3 서
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int count = 0;
bool DFS(int x, int y, int d)
{
//std::cout << y << "," << x << std::endl;
if (v[y][x] == 0)
{
v[y][x] = 1;
count++;
}
for (int i = 0; i < 4; ++i)
{
int nd = (d + 3 - i) % 4;
int nx = x + dx[nd];
int ny = y + dy[nd];
if (r[ny][nx] == 0 && v[ny][nx] == 0)
{
v[ny][nx] = 1;
count++;
if (DFS(nx, ny, nd) == false)
return false;
}
}
int bd = (d + 2) % 4;
int bx = x + dx[bd];
int by = y + dy[bd];
if (r[by][bx] == 0)
{
if (DFS(bx, by, d) == false)
return false;
}
else if(r[by][bx] == 1)
return false;
return true;
}
int main()
{
std::ios::ios_base::sync_with_stdio(false);
memset(r, -1, sizeof(r));
std::cin >> N >> M;
int x, y, d;
std::cin >> y >> x >> d;
for (int i = 0; i < N; ++i)
{
for (int ii = 0; ii < M; ++ii)
{
std::cin>> r[i][ii];
}
}
DFS(x, y, d);
std::cout << count;
}
이동하는 모습을 디버깅해보면서 풀면 된다.
반응형