https://www.acmicpc.net/problem/14503
문제
> 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.
> 로봇 청소기가 있는 방은 NxM 크기의 직사각형으로 나타낼 수 있으며, 1x1 크기의 정사각형 칸으로 나누어져 있다.
> 각각의 칸은 벽 또는 빈 칸이다.
> 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다.
> 방의 각 칸은 좌표 (r, c)로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 (0, 0),
가장 남쪽 줄의 가장 동쪽 칸의 좌표가 (N-1, M-1)이다.
> 즉, 좌표 (r, c)는 북쪽에서 (r+1)번째에 있는 줄의 서쪽에서 (c+1)번째 칸을 가리킨다.
> 처음에 빈 칸은 전부 청소되지 않은 상태이다.
> 로봇 청소기는 다음과 같이 작동한다.
1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우,
2-1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
2-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우,
3-1. 반시계 방향으로 90도 회전한다.
3-2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
3-3. 1번으로 돌아간다.접근
문제에 주어진대로 로봇청소기의 움직임을 정의한다.
1. 현재 칸 청소(방문처리 해줌)
2. 사방탐색하고 벽이 아니라면 방문처리 검사해서 방문 안한 좌표있으면 4번으로 가고 없으면 3번으로 감
3. 방향 유지한 상태로 뒤 좌표 벽인지 보고 후진, 다시 1번으로감
4. 일단 반시계로 회전하고 보고있는 좌표 앞쪽 방문처리 검사해서 방문 안했으면 전진, 다시 1번으로 감
위의 내용을 메소드로 만들어준다.
로봇청소기의 방향을 북동남서를 0,1,2,3인덱스로 해주지만 문제에서는 반시계로 돌기 때문에 북서남동 순서로 탐색한다.
문제해결
> 방의 크기를 입력받고, 시작점의 좌표와 방향을 입력받은 뒤, 방의 구조(벽, 빈곳)를 입력받는다.
> 로봇청소기의 움직임을 정의한 CleanUp메소드에 주어진 시작위치와 방향을 넣고 호출한다.
> 처음 위치를 일단 기준으로 fr,fc,fd로 잡고 while문에 들어간다. 처음부터 1번의 내용인 현재칸을 청소한다를 청소안한 위치면 해주고 수를누적한다.
> 사방을 탐색하며 벽이 아닌 곳에서 청소할 곳이 있으면 isClean이 false로 반환되고 없으면 true로 반환된다.
> 사방을 북동남서로 정의했지만 탐색은 반시계로 하기 위해 idx를 현재 방향fd에 i-1을 더한뒤 4로 나눈 나머지로 수식화 해서 따져준다.
> isClean에 따라 true면 후진하기 위해 바라보는 방향에 맞게 현재 좌표에서 계산해준 뒤 벽인지 확인해준다.
> 벽이라면 작동을 종료하고 아니면 현 위치를 계산해준 좌표로 이동한다.
> isClean이 false면 사방탐색으로 반시계로 돌면서 벽이 아닌 청소안한 곳(방문처리 안된곳)으로 좌표를 계산해 이동해준뒤 while문의 처음으로 돌아가 청소를 시작한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//14503 로봇청소기
int N, M;
vector<vector<int>> room;
vector<vector<bool>> clean;
int dir[4] = { -1, 0, 1, 0 }; //북동남서
int dic[4] = { 0, 1, 0, -1 };
int cnt = 0;
struct state
{
int row;
int col;
int pos;
};
void CleanUp(int r, int c, int d)
{
int fr = r;
int fc = c;
int fd = d;
bool active = true;
while (1)
{
if (!clean[fr][fc]) {
clean[fr][fc] = true;
cnt++;
}
bool isClean = true; //true면 주변이 다 깨끗함, false면 더러운데 있음
for (int i = 4; i > 0; i--) //사방 청소X 탐색
{
int idx = (fd + i - 1) % 4;
int nr = fr + dir[idx];
int nc = fc + dic[idx];
if (room[nr][nc] == 1) continue; //주변이 벽이면 넘겨
if (!clean[nr][nc]) //주변에 청소 안한곳이 있음
{
isClean = false;
}
}
if (isClean) //전부 깨끗이라면
{
if (room[fr - dir[fd]][fc - dic[fd]] == 1) // 후진이 벽이면
{
active = false;
break; //작동 정지
}
fr = fr - dir[fd];
fc = fc - dic[fd];
fd = fd;
}
else //안깨끗한데가 있다면
{
for (int i = 4; i > 0; i--) //사방 청소X 탐색
{
int idx = (fd + i - 1) % 4;
int nr = fr + dir[idx];
int nc = fc + dic[idx];
int nd = idx;
if (room[nr][nc] == 1) continue; //주변이 벽이면 넘겨
if (!clean[nr][nc]) //주변에 청소 안한곳이 있음
{
fr = nr;
fc = nc;
fd = nd;
break;
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
state first;
cin >> first.row >> first.col >> first.pos;
room.resize(N, vector<int>(M));
clean.assign(N, vector<bool>(M, false));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> room[i][j]; //1은 벽, 0은 더러움
}
}
CleanUp(first.row, first.col, first.pos);
cout << cnt << '\n';
}
후기
전체적인 움직임의 흐름을 정의하는 것과 방향을 수식화해주기 위한 부분이 좀 까다로웠지만 재밌었다.
