[BOJ] 14503 - 로봇청소기

안녕하세요.

여행벌입니다.

오늘은 백준사이트의 14503번 '로봇청소기' 문제 풀이를 해보겠습니다.

---

[문제해석]

한글 문제라 따로 다루지 않겠습니다.

 

[알고리즘설계]

1. 시작 점부터 반시계 방향으로 돌며 청소를 안 한 곳이 있으면 청소를 해나간다.

(청소를 하지 않은 곳은 0, 벽은 1, 청소를 한 곳은 2를 저장해나가며 청소를 진행한다.)

2. 모든 방향을 돌았는데, 갈 곳이 없다면 후진을 한다.

- 후진을 할 수 있으면 후진 후 다시 1번부터 진행.

- 후진을 할 수 없다면(뒤가 벽이라면) 종료한다.

#include<iostream>

using namespace std;

int map[50][50];
int dx[4] = { 0,-1,0,1 };
int dy[4] = { -1, 0, 1, 0 };

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int row, column;
	cin >> row >> column;
	int x, y, dir;
	// dir 0 북 1 동 2 남 3 서
	cin >> x >> y >> dir;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < column; j++)
			cin >> map[i][j];

	int count = 0;
	int flag = 1; // 조건을 만족하면 0으로 바꾸고 while을끝낸다.
	while (flag) {
		if (!map[x][y])
			count++;
		map[x][y] = 2;
		for (int i = 0; i < 5; i++) {
			if (i == 4) { // 4바퀴를 다 돌았는데도 for문이 안깨짐 -> 후진하거나 멈춰야됨.
				int next_x = x + dx[(dir + 3) % 4];
				int next_y = y + dy[(dir + 3) % 4];
				if (0 <= next_x && next_x < row && 0 <= next_y && next_y < column && map[next_x][next_y] != 1) {
					x = next_x;
					y = next_y;
				}
				else
					flag = 0;
                break;
			}
			int next_x = x + dx[dir];
			int next_y = y + dy[dir];
			dir = (dir + 3) % 4;
			if (0 <= next_x && next_x < row && 0 <= next_y && next_y < column && !map[next_x][next_y]) {
				x = next_x;
				y = next_y;
				break;
			}
		}
	}
	cout << count;
}

[중요코드]

int dx[4] = {0,-1,0,1};
int dy[4] = {-1,0,1,0};

// 뒤로 후진해야하는경우.
int next_x = x + dx[(dir + 3) % 4];
int next_y = y + dy[(dir + 3) % 4];

// 왼쪽으로 반시계방향으로 도는 경우
int next_x = x + dx[dir];
int next_y = y + dy[dir];
dir = (dir + 3) % 4;

0(북), 1(동), 2(남), 3(서) 를 의미하고 우리는 반시계 방향(왼쪽)으로 회전하면서 청소할 공간이 있는지 찾아볼 것이다.

또, 모든 방향에 청소할 공간이 없다면 뒤로 후진을 해야 한다.

따라서 dx, dy 배열을 다음과 같이 선언하고 next_x, next_y를 위와 같이 다루면 깔끔하게 탐색을 진행할 수 있다.

---

dx, dy 배열을 선언하고 next_x, next_y 변수를 다루는데 미숙해 생각보다 구현하는데 오래 걸렸다.

 

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.