3 분 소요

Intro

image

image

image

문제해결 및 소스코드

/*							<문제규칙>
			1. 현재 칸이 청소되지 않은 경우, 현재 칸을 청소한다.
			2. 현재 칸의 주변 4칸(상하좌우)중 청소되지 않은 빈칸이 없는경우
				2-1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 후진하고 1로 돌아간다.
				2-2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
			3. 현재 칸의 주변 4칸 중 청소되지 않은 빈칸이 있는경우
				3-1. 반시계 방향으로 90도 회전한다.
				3-2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈칸일 경우 전진한다.
				3-3. 1번으로 돌아간다.


							<문제해결>
			문제를 이해하는데만해도 오래 걸렸던것같다.
			나는 DFS를 사용하기로했고, 재귀호출을 사용하여 구현했다. 

			최초 청소기가 있는곳에서 DFS를 호출한다. 최초의 방을 청소하고,
			Check() 함수(상하좌우에 청소안된 빈방이 있는지 확인)를 호출하여 
			주변을 탐색했다. 

			1. 만약 청소안된 빈방이 있으면 청소기 방향을 반시계로 돌리고
				1.1 그 방향으로 전진가능하면, 다음 좌표에서 DFS를 호출했다.
			2. 청소안된 빈방이 없다면 방향을 유지한채로 후진시켰다.
				2.1 뒤쪽에 벽이있다면 최종 카운트를 출력하고 종료시켰다.

			그런데, 문제는 
			- 청소기방향(d)에 따라 다음 나아갈 방향(next_dir)을 결정하고
			- 방향에 따른 다음 좌표(next_dx, next_dy)를 결정하는 것
			
			위 두개를 어떻게 구할것인지인데, 머리가 지끈거려 바보가 되기로했다.
			코드가 길어지고 보기싫어지고 비효율적이고....
			그렇지만 if else문으로 하나하나 처리해버렸다..
*/

#include <iostream>
#define MAX 50

using namespace std;

int n, m;					// 방의 크기 가로x세로

int rooms[MAX][MAX];		// 방의 크기 최대 50x50
int cleaned[MAX][MAX];		// 청소했는 지 여부

int dx[4] = { -1,0,1,0 };	// 상-우-하-좌 순서
int dy[4] = { 0,1,0,-1 };

int cnt;					// 청소한 방의 갯수

// 상하좌우에 청소안된방이 있는지 탐색
bool Check(int x, int y)
{
	int exist = false;				// 청소 안된방이 있으면 true, 없으면 false

	// 상-우-하-좌 탐색
	for (int i = 0; i < 4;i++)
	{
		int next_dx = dx[i] + x;
		int next_dy = dy[i] + y;

		// 유효 범위를 벗어나면 무시
		if (next_dx < 0 || next_dx >= n || next_dy < 0 || next_dy >= m)
			continue;

		// 청소 안된방이 있을 때
		if (!cleaned[next_dx][next_dy] && rooms[next_dx][next_dy] == 0)
		{
			exist = true;
			break;
		}
	}

	return exist;
}


void DFS(int x, int y, int dir)
{
	// 해당 방이 청소되지 않았을 때
	if (!cleaned[x][y])
	{
		cleaned[x][y] = true;			// 해당 방을 청소했음을 기록
		cnt += 1;
	}
	
	// 1. 주변에 청소가 안된방이 있을 때(방향설정 후 전진)
	if (Check(x, y))
	{
		int next_dir = (dir == 0) ? 3 : dir - 1;
		int next_dx;
		int next_dy;

		
		if (next_dir == 0)
		{
			next_dx = x - 1;
			next_dy = y;
		}
		else if (next_dir == 1)
		{
			next_dx = x;
			next_dy = y + 1;
		}
		else if (next_dir == 2)
		{
			next_dx = x + 1;
			next_dy = y;
		}
		else
		{
			next_dx = x;
			next_dy = y - 1;
		}

		// 유효범위 AND 빈방, 청소안된방일 때
		if (next_dx >= 0 && next_dy >= 0 && next_dx < n && next_dy < m && rooms[next_dx][next_dy] == 0
			&& !cleaned[next_dx][next_dy])
			DFS(next_dx, next_dy, next_dir);
		// 청소기 방향만 바꿔주기
		else
			DFS(x, y, next_dir);
	}
	// 2. 주변방 청소가 끝났을 때(후진)
	else
	{
		int next_dir = dir;			// 방향을 유지
		int next_dx;
		int next_dy;

		if (next_dir == 0)
		{
			next_dx = x + 1;
			next_dy = y;
		}
		else if (next_dir == 1)
		{
			next_dx = x;
			next_dy = y - 1;
		}
		else if (next_dir == 2)
		{
			next_dx = x - 1;
			next_dy = y;
		}
		else
		{
			next_dx = x;
			next_dy = y + 1;
		}

		if(next_dx >= 0 && next_dy >= 0 && next_dx < n && next_dy < m && rooms[next_dx][next_dy] == 0)
			DFS(next_dx, next_dy, next_dir);
		else
		{
			cout << cnt;
			exit(0);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int r, c;				// 최초 청소기가 있는 칸의 좌표
	int d;					// 청소기의 방향(0:상, 1:우, 2:하, 3:좌)

	// 방 크기 입력
	cin >> n >> m;

	// 처음 로봇청소기가 있는 칸의 좌표와 방향
	cin >> r >> c >> d;

	// 방 상태 입력(0:빈칸, 1:벽)
	for (int i = 0;i < n;i++)		// - N : 세로
	{
		for (int j = 0;j < m;j++)	// - M : 가로
		{
			cin >> rooms[i][j];
		}
	}

	// 청소시작(좌표:(r,c) 방향:d, 청소한 방의 갯수: cnt)
	DFS(r, c, d);
}

이렇게 “무식한 방법말고도 있을텐데…” 하며 울면서 코드를 짰다.

다른사람이 풀어놓은 코드를 보니 내 코드의 반정도밖에 안됐다.

그걸 보고 나는 아직 멀었구나 라는걸 느꼈다…

댓글남기기

참고