[백준][BFS] 14503번 로봇 청소기

문제 정의

로봇 청소기의 주어진 작동방법을 통해서 청소하는 영역의 개수를 구하는 프로그램을 작성하는 것이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

문제 출처 : 백준 온라인 저지(https://www.acmicpc.net/problem/14503)

문제 풀이

벽으로 막힌 곳이 아닌 곳을 다니며 청소만 하는 청소기였다면 BFS로 바로 풀 수 있는 문제다. 이 문제에서는 청소기가 향하는 방향이 있고 그 방향먼저 탐색하면서 BFS를 수행해야한다. 청소기의 방향을 나타내는 전역변수를 하나 둬서, BFS를 수행할 때 그 방향에 +1 ~ +4를 해주며 방향을 계속 탐색한다. 이 때 %를 사용해서 오버플로우가 안나게 해야한다.

라고 썼었는데 그래서 이 문제를 풀지 못했었다. 이 문제에서는 한번 전진하면 회전하던 방향으로 돌아보던 그 과정을 다시 백트래킹해서 하는게 아니라 계속 전진해서 문제를 풀면된다. while문 안에서 계속 x, y좌표를 고치면서 전진을 하도록 고쳤다. 사실 처음에 문제가 애매모호하다고 느껴져서 헷갈렸다. 그리고 입력예제가 11 10 이어서 손으로 막상 그려볼 엄두가 안났다. 그래서 생각하는데 시간이 오래걸린 것 같다. 언제 방향전환을 해주는지만 잘 파악하면 된다. 내코드에서는 어차피 4방향 모두 청소가 되어있거나 벽이 있는 경우는 for문에서 4번 방향전환이 이루어져서 결국 다시 원래 방향이라서 방향전환을 안해주는 경우가 없이 보이는 것처럼 짰다. 무조건 어떤 방법을 써야겠다고 해서 풀려고 하니까 잘 안풀렸던 것 같다. 문제 조건을 좀 꼼꼼히 읽어서 풀어야겠다.

코드

void DFS(int x, int y)

{

int i, j; 

int idx, idy;

int check=0;

while(1){

if(state[x][y] == 0){

state[x][y] = 3; //청소하기

cnt++;

}

check=0;

for(i=0; i<4; i++)

{

dir = (dir+3)%4;

idx = x + dx[dir];

idy = y + dy[dir];

if( state[idx][idy] != 0 || idx < 0 || idx >= N || idy < 0 || idy >=M){

check++;

continue; //갈필요없음

}

if(state[idx][idy] == 0){

x = idx;

y = idy;

break;

}

}

if( check == 4 ){ //4방향 전부 막혀있을 경우 방향을 유지

if(state[x-dx[dir]][y-dy[dir]] == 1 || x-dx[dir] < 0 || x-dx[dir] >= N || y-dy[dir] < 0 || y-dy[dir] >=M )

break;

else{ //후진

x = x-dx[dir];

y = y-dy[dir];

}

}

}

}