[백준 14503] 로봇 청소기

문제설명

 

알고리즘

1. 입력 받기 : 그래프 크기, 현재 위치, 방향, 그래프 형태

2. 방향 설계 -> 북 서 남 동 순으로 회전하기 때문에 dx,dy에 전진할때 발생하는 값을 정의해 둔다

3. 왼쪽으로 돌고, 안갔으면 간다. 단 갔으면 왼쪽으로 돈다

4. 4방향 다 돌았는데 갈 수 있는 곳이 없는 경우 그 자리에서 1칸 후진한다

5. 후진하려는데 그 뒤도 막혔으면 종료

---

코드

1) 시행착오

#include<iostream>

using namespace std;
//탐색
int dx[4] = { 0,-1,0,1 }; //d=0 ~ 3일때 x의 이동 값
int dy[4] = {-1,0,1,0 }; //d=0 ~ 3일때 y의 이동 값
//후진
int bx[4] = { 1,0,-1,0 }; //d=0 ~ 3일때 x의 이동 값  
int by[4] = { 0,-1,0,1 }; //d=0 ~ 3일때 y의 이동 값

int main() {
   int N, M, d;
   int x, y, result =1;

   cin >> N >> M >> x >> y >> d;//input
   
   int **graph = new int*[N];//공간할당
   for (int i = 0; i <= M; i++)
      graph[i] = new int[M];

//   fill(&graph[0][0], &graph[N][M], -1);//초기화 

   for (int i = 0; i < N; i++) //그래프 값 입력
   {
      for (int j = 0; j < M; j++)
      {
         cin >> graph[i][j];
      }
   }
   graph[x][y] = 1;
   while (1) {
      bool on = false; //4방향 중 청소 할 곳 있는지 확인

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

         int nx = x + dx[d];
         int ny = y + dy[d];

         if (nx >= N || ny >= M || nx < 0 || ny < 0) //범위를 벗어난 경우 탐색 불가
            continue;

         if (graph[nx][ny] == 0) { //왼쪽이 청소 가능한 경우 -> 회전 후 이동
            result++;//청소
            graph[nx][ny] = result;//청소 됨 표시 
            x = nx; //이동할 좌표 업데이트
            y = ny;
            on = true; //청소함
         }

         //방향 업데이트
         if (d == 0)
            d = 3;
         else
            d -= 1;

         if (on)
            break;
      }
               
      if (!on) {//4방향 탐색했지만 이동하지 못한 경우 후진
         x = x + bx[d];
         y = y + by[d];
         if (graph[x][y] == 1) //후진하려는 곳이 벽인 경우 중지
            break;
      }
   }

   for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++)
      {
         printf("%2d ", graph[i][j]);
      }cout << endl;
   }

   cout << result; 
}

이 코드도 돌아가기는 한다

문제는, 모든 케이스에서 작동하지는 않는다

제출시 segmentation fault가 발생한다 

아무래도 bfs와 dfs를 섞어서 짜서 몇몇 경우에선 반복문을 탈출하지 못하는 것 같다

 

2) 정답

#include<iostream>

using namespace std;
//탐색
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int graph[51][51];
int N, M, result;

void dfs(int x, int y, int d) {

	if (graph[x][y] == 0) {
		result++;
		graph[x][y] =2;//청소 됨 표시 
	}

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

		int nd = (d + 3 - i) % 4; //북-> 서-> 남 -> 동 (왼쪽 회전)
		//왼쪽으로 회전한 방향에 한칸 전진 할 좌표
		int nx = x + dx[nd];
		int ny = y + dy[nd];

		if (nx >= N || ny >= M || nx < 0 || ny < 0) //범위를 벗어난 경우 탐색 불가
			continue;

		if (graph[nx][ny] == 0) { //왼쪽이 청소 가능한 경우 -> 회전 후 이동               
			dfs(nx, ny, nd);
		}
	}

	//4방향 탐색했지만 이동하지 못한 경우 후진
	int nd = (d + 2) % 4;
	int nx = x + dx[nd];
	int ny = y + dy[nd];

	if (graph[nx][ny] == 1) //후진하려는 곳이 벽인 경우 중지
	{
		cout << result ;
		exit(0);
	}

	dfs(nx, ny, d); //좌표는 이동하되, 방향은 안바꾸고 후진 

}
int main() {

	int r, c, d;

	cin >> N >> M >> r >> c >> d;//input


	for (int i = 0; i < N; i++) //그래프 값 입력
	{
		for (int j = 0; j < M; j++)
		{
			cin >> graph[i][j];
		}
	}
	dfs(r, c, d); //탐색시작

}

---

고찰

이 문제는 코드를 bfs,dfs섞어서 짜서 이상하게 동작했다

되는 케이스도 있었고 안되는 것도 있어서 결국 다 뜯어 고치느라 오래걸렸다

참고한 테스트 케이스들은 다음과 같다

https://www.acmicpc.net/board/view/67476

글 읽기 - [로봇 청소기] 테스트 케이스(반례) 공유합니다.

https://www.acmicpc.net/board/view/83808

글 읽기 - 로봇청소기 테케 2번 청소를 다해버립니다..