[백준 14503] 로봇 청소기

문제 바로가기

14503번: 로봇 청소기

 

삼성 역량테스트 기출 문제를 풀어보았다

어렵지는 않은데 까다로운 문제..

국어도 잘해야 빨리 풀 수 있을 것 같다

 

나는 동이랑 서 방향을 헷갈려서 거기서 오래걸렸다

헷갈리기 시작하면 끝도 없으니까 한 방에 제대로 이해하고 풀어야겠다

 

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int visited[50][50];
int map[50][50];
pair<int, int> start;
int dir;//0은 북, 1은 동, 2는 남, 3은 서
int pos[4][2] = { {-1,0}, {0, 1}, {1,0}, {0,-1} };
int clean_cnt;

void bfs(int x, int y)
{
	queue<pair<int, int>> Q;

	Q.push(make_pair(x, y));
	visited[y][x] = 1;
	clean_cnt++;

	while (!Q.empty())
	{
		int cx = Q.front().first;
		int cy = Q.front().second;
		Q.pop();

		int cnt = 0;
		while (1)
		{
			cnt++;
			int new_dir = (dir - 1);
			if (new_dir == -1)
				new_dir = 3;

			int nx = cx + pos[new_dir][1];
			int ny = cy + pos[new_dir][0];

			if (!map[ny][nx] && !visited[ny][nx]) //a 경우
			{
				visited[ny][nx] = 1;
				Q.push(make_pair(nx, ny));
				dir = new_dir;
				clean_cnt++;
				break;
			}

			if (cnt == 4)
			{
				nx = cx - pos[new_dir][1];
				ny = cy - pos[new_dir][0];

				if (map[ny][nx] == 1)//후진 못하는 경우(d)
				{
					return;
				}
				else
				{
					Q.push(make_pair(nx, ny));
					dir = new_dir;
					break;
				}
			}
			dir = new_dir;
		}
	}
}

int main()
{
	cin >> N >> M;

	cin >> start.second >> start.first;

	cin >> dir;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> map[i][j];
		}
	}

	bfs(start.first, start.second);

	cout << clean_cnt << endl;

	return 0;
}