문제 풀이
생각보다 조건이 되게 많은 문제다.
간단하게 생각해보면 현실에서 로봇 청소기를 생각해보자.
현재 위치와 방향에서 앞에 벽이 없다면? 아마도 전진한 다음 그곳을 청소한다.
현재 위치와 방향에서 앞에 벽이 있다면? 왼쪽이나 오른쪽으로 돌아 선 다음 그곳에서 다시 벽을 체크할 것이다.
이렇게 내가 로봇 청소기라면 어떻게 판단할지 생각하면서 문제를 다시 보자.
이제 하나씩 조건을 보면서 생각해보자.
1) 현재 위치를 청소한다.
말 그대로 현재 위치를 청소했다고 방문처리를 하고 청소 횟수를 +1 하면 된다.
(주의할 점이 로봇이 처음 주어진 좌표도 청소해야 되므로 초기값은 1이다.)
2) 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
말이 긴데 요약하면 현재 위치에서 왼쪽 방향부터 차례대로 보겠다는 뜻이다.
2-1) 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
일단 왼쪽 방향으로 틀고 한 칸 전진한 위치를 보고 판단하라는 것이다.
2-2) 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
청소할 공간이 없다는 건, 이미 청소를 했거나 혹은 벽을 뜻한다.
이럴 때는 어쩔 수 없이 다시 왼쪽 방향을 살펴보자.
2-3) 4 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
2-4) 4 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
2-3 조건과 2-4 조건은 비슷해서 한 번에 해석이 가능하다.
자동차를 떠올려보자. 둘러봤는데 앞으로 전진할 수 없으면 어떻게 할까? 후진해야 된다.
그런데? 후진할 공간도 벽이면 결국 내 위치에서 후진하는 쪽도 벽이 있다는 뜻이다.
그러면 그 청소기는 어떤 행동도 하지 못하고 결국 종료.
종료할 때 내가 청소했던 횟수를 출력하기만 하면 된다.
의미는 알겠는데 구현을 어떻게 할까..
현재 위치에서 왼쪽, 왼쪽, 왼쪽, 왼쪽 하면 자기 자신으로 돌아온다.
즉 4번 루프를 돌려서 모든 구역을 확인해보고 만약에 청소할 공간을 찾았다면? 종료시키고 그쪽으로 다음 상태를 전달하면 된다.
그런데 4번을 확인해도 찾지 못했다는 건?
2-3 조건과 2-4 조건을 체크해서 2-3에 해당한다면 로봇 청소기를 후진시켜서 다음 상태로 전달하면 되고,
2-4에 해당한다면 현재까지 청소한 횟수를 출력하고 종료하면 된다.
소스 코드
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 55;
const int dx[] = { -1,0,1,0 };
const int dy[] = { 0,1,0,-1 };
int N, M;
int board[MAX][MAX];
bool visit[MAX][MAX];
pair<pair<int, int>, int> init;
struct Robot
{
int x;
int y;
int d;
int cnt;
};
void input()
{
cin >> N >> M;
cin >> init.first.first >> init.first.second >> init.second;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cin >> board[i][j];
}
}
}
int nextDirection(int d)
{
if (d == 0) return 3;
else return d - 1;
}
void bfs()
{
queue<Robot> q;
int x = init.first.first;
int y = init.first.second;
int d = init.second;
int cnt = 1;
q.push({ x,y,d,cnt });
visit[x][y] = true;
while (!q.empty())
{
// 현재 로봇 청소기 상태
x = q.front().x;
y = q.front().y;
d = q.front().d;
cnt = q.front().cnt;
q.pop();
// 4방향을 탐색해본다.
int notFound = 0;
for (int i = 0; i < 4; i++)
{
int nd = nextDirection(d);
int nx = x + dx[nd];
int ny = y + dy[nd];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
// 청소할 공간을 찾았다면 탈출
if (board[nx][ny] == 0 && visit[nx][ny] == false)
{
visit[nx][ny] = true;
q.push({ nx,ny,nd,cnt + 1 });
break;
}
notFound++;
d = nd;
}
// 4방향 모두 청소할 공간을 찾지 못했다면
if (notFound == 4)
{
int nx = x - dx[d];
int ny = y - dy[d];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
{
cout << cnt << endl;
return;
}
if (board[nx][ny] == 1)
{
cout << cnt << endl;
return;
}
q.push({ nx, ny, d, cnt });
}
}
}
void solve()
{
input();
bfs();
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
