[백준]14503 로봇 청소기(C++)

 

백준 14503 로봇 청소기

위 문제는 삼성 SW 역량 테스트에 나왔던 문제이다.

시뮬레이션 문제인데 지문에서 제시한 방향에 대한 조건을 제대로 읽지 않아 푸는데 시간이 좀 걸렸다.

1. 문제

문제링크

2. 접근법

[ 문제 접근 ]

 

1. 로봇 청소기의 위치와 방향이 주어지고 청소기가 청소하는 칸의 개수를 출력하는 문제이다.

2. 로봇 청소기의 위치와 방향을 담기 위해 구조체를 선언하고 이 구조체를 자료형으로 큐를 만들어서 청소기의 위치와 방향을 담는다.

3. 지문에서 제시한 북, 서 남, 동 4 방향, 즉 반시계 방향으로 90도씩 회전하며 앞에 청소하지 않은 칸이 있다면 청소한 후 해당 위치의 체크 배열 상태를 true로 만든다.

4. 또한 반시계 방향으로 90도로 회전해야 하므로 북->서->남->동 (0->3->2->1) 즉 (해당 인덱스 + 3) % 4 를 해야 다음 인덱스를 구할 수있다.

• 인덱스 순으로 차례대로 북, 동, 남, 서 
• Dr = { -1, 0, 1, 0 }
• Dc = { 0, 1, 0, -1 }

5. 내가 잘못 읽었던 부분은 네 방향 모두가 청소가 되어 있을때 처리하는 부분인데, 

네 방향 모두 청소가 이미 되어 있거나 벽인 경우에는 바라보는 방향을 유지한 채 한칸 후진을 해야하는데 방향 유지를 하지 않고 구현하여 수정하는데 시간이 꽤 걸렸다.

3. 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <fstream>
using namespace std;

int map[51][51];
//북, 동, 남, 서
int Dr[4] = { -1, 0, 1, 0 };
int Dc[4] = { 0, 1, 0, -1 };
bool checked[51][51] = { false, };
struct Pos
{
	int r, c, dir;
};
Pos pos;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//ifstream cin;
	//cin.open("input.txt");
	int ans = 0;
	int N, M;
	cin >> N >> M;
	cin >> pos.r >> pos.c >> pos.dir;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
		}
	}

	queue<Pos> Q;
	Q.push(pos);

	while (!Q.empty())
	{
		Pos curr = Q.front();
		Q.pop();

		if (map[curr.r][curr.c] == 0 && checked[curr.r][curr.c]==false)
		{
			checked[curr.r][curr.c] = true;
			ans++;
		}
		for (int i = 0; i < 4; i++)
		{
			Pos next;
			//90도 회전했을때 벽이거나 청소한 경우에는 
			//다시 90도 돌려야하므로 -i 해준다.
			next.dir = (curr.dir + 3 - i) % 4;
			next.r = curr.r + Dr[next.dir];
			next.c = curr.c + Dc[next.dir];
		
			//예외처리
			if (next.r < 0 || next.r >= N || next.c < 0 || next.c >= M
			|| map[next.r][next.c] == 1 || checked[next.r][next.c] == true)
			{
				continue;
			}
			
			Q.push(next);
			
			//청소기는 하나뿐이므로 하나 넣고 바로 break시킨다.
			break;
		}
		//후진 처리
		if(Q.empty())
		{
			Pos next;
			//***방향은 유지***
			next.dir = curr.dir;
			next.r = curr.r + Dr[(curr.dir + 2) % 4];
			next.c = curr.c + Dc[(curr.dir + 2) % 4];

 
			//뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
			if (next.r < 0 || next.r >= N || next.c < 0 || next.c >= M
				|| map[next.r][next.c] == 1)
			{
				break;
			}
			
			Q.push(next);
		}
	}	
	cout << ans << "\n";
	return 0;
}

4. 시간복잡도

map 사이즈가 최대 50이고 4방향으로 탐색하므로 50*4=200이 되어 1초 내에 구현하기 충분하다. 

5. 결과