8. 백준[14503번 / C++] 로봇 청소기

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

두통이 너무 심한 상태로 시작한 문제 풀이. 간단한 구현 문제였다.

 

정말 문제에 있는 것을 그대로 구현만 하면 되는 문제였는데 아마 DFS, BFS에 익숙한 사람이라면 더 쉽게 풀었을 것이다.

 

문제에 조건이 좀 애매하게 적혀있어서 여기서 내가 다시 정리해보겠다.

 

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다.
2. 현재 칸의 주변 네 칸 중 청소되지 않은 빈 칸이 없는 경우,
   1. 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다.
   2. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다.
3. 현재 칸의 주변 네 칸 중 청소되지 않은 빈 칸이 있는 경우,
   1. 반시계 방향으로 90도 회전한다.
   2. 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸인 경우 한 칸 전진한다.
   3. 1번으로 돌아간다.

 

자 이제 조건이 명확히 된다. 그 다음 문제를 보자.

 

문제 입력 조건

 

이제 구현해야 하는 부분을 살펴보자.

 

1. 방향 d의 조건에 맞게 북쪽, 동쪽, 남쪽, 서쪽을 정확하게 구현해야 한다.
2. 문제에서 좌표의 시작이 (0, 0)인 것을 유념하자.
3. 값이 0이 입력되면 (i, j)가 청소되지 않은 빈 칸이다. 1인 경우에는 벽이있다. 또한, N x M 크기에 대하여 외벽또한 있다.
4. 청소를 하면 청소가 됐다는 상태를 저장해야한다. 난 여기서 값 2로 상태값을 저장했다.

 

바로 코드를 보자

 

#include<bits/stdc++.h>
using namespace std;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1}; // 방향 구현
int n, m, dir, y, x, a[54][54], ret; // a[54][54]가 방들의 상태

int main(){
	cin >> n >> m >> y >> x >> dir;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i][j]; 
		}
	}
	while(true){
		if(a[y][x] == 0){ // 조건 1
			ret++; // 청소한 방 + 1
			a[y][x] = 2; // 청소했음을 2라는 상태값으로 저장
		}
		int flag = 0; // 조건 2와 3을 구분하기 위한 flag
		for(int i = 0; i < 4; i++){
			int ny = y + dy[i];
			int nx = x + dx[i];
			if(ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 1) continue;
			if(a[ny][nx] == 0) flag = 1; // 주변에 청소하지 않은 방이 있다!
		}
		if(flag == 0){ // 조건 2
			int ny = y - dy[dir];
			int nx = x - dx[dir]; // 바라보는 방향에서 한 보 후퇴
			if(ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 1) break; // 청소기 stop!
			y = ny;
			x = nx; // 이동
            // 다시 조건 2로 이동
		}else{ // 조건 3
			while(true){
				dir = (dir + 3) % 4; // 반시계 방향으로 90도만큼 회전
				int ny = y + dy[dir];
				int nx = x + dx[dir];
				if(ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 1) continue;
				if(a[ny][nx] == 0){
					y = ny;
					x = nx; // 이동 
					break; // 청소할 수 있으니 조건 1로 다시 이동
				}
			}
		}
	}
	cout << ret << "\n";
}

 

주석에 적힌대로 문제에서 정의된 조건을 그대로 구현했다. 솔직하게 말해서 어렵진 않은 문제였는데, 머리에 두통이 너무 심해서 (i, j) = 1일 때 벽임을 확인 못해서 한 번 틀렸다.