삼성 코딩테스트 기출_(백준)로봇 청소기

난이도 ★☆☆

 

문제출처

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

14503번: 로봇 청소기

포인트

1. clean(int r, int c, int dir)

현재 위치(r,c)를 청소하는 함수. 청소 후 탐색을 위해 현재 방향인 dir정보가 필요하다.

 

2. search(int r, int c, int dir)

현재 위치(r,c)와 방향(dir)을 기준으로 다음 청소할 곳을 탐색하는 함수. switch문으로 네 방향 구분해주고 네 개의 case는 모두 같은 로직이다. 문제에서 준 조건을 그대로 코드에 옮기면 되는 단순 구현으로 짰다.

 

3. 주의할 점

문제의 조건이 굉장히 장황하므로 글로써 이해를 잘 하는 것이 중요한 문제인듯..

 

정답코드

#include <iostream>
using namespace std;

int map[51][51];
int n, m, r, c, dir;
int ans = 0;

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

void search(int r, int c, int dir);

void clean(int r, int c, int dir) {
	map[r][c] = 1;// 1. 현재 위치를 청소한다
	ans++;//청소된 영역 카운트

	search(r, c, dir);// 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
}

void search(int r, int c, int dir) {
	int nextDir;
	if (dir == 0)nextDir = 3;
	else nextDir = dir - 1;

	switch (dir) {
	case 0://현재북쪽 다음서쪽
		if (!map[r][c - 1]) clean(r, c - 1, nextDir); //a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, ...(조건)
		else {
			bool unfinished = false;
			for (int i = 0; i < 4; i++) {
				int nr = r + dy[i];
				int nc = c + dx[i];
				if (!map[nr][nc]) {
					unfinished = true;
					break;
				}
			}
			if (unfinished) { //b. 왼쪽 방향에 청소할 공간이 없다면, ...(조건)
				search(r, c, nextDir);
			}
			else {
				if (map[r + 1][c]!=-1)search(r + 1, c, dir); //c. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, ...(조건)
				else return; //d. 네 방향 모두 청소가 이미 되어있거나 벽이면서, ...(조건)
			}
		}
		break;
	case 1://현재동쪽 다음북쪽
		if (!map[r-1][c]) clean(r-1, c, nextDir);
		else {
			bool unfinished = false;
			for (int i = 0; i < 4; i++) {
				int nr = r + dy[i];
				int nc = c + dx[i];
				if (!map[nr][nc]) {
					unfinished = true;
					break;
				}
			}
			if (unfinished) {
				search(r, c, nextDir);
			}
			else {
				if (map[r][c-1]!=-1)search(r, c-1, dir);
				else return;
			}
		}
		break;
	case 2://현재남쪽 다음동쪽
		if (!map[r][c+1]) clean(r, c+1, nextDir);
		else {
			bool unfinished = false;
			for (int i = 0; i < 4; i++) {
				int nr = r + dy[i];
				int nc = c + dx[i];
				if (!map[nr][nc]) {
					unfinished = true;
					break;
				}
			}
			if (unfinished) {
				search(r, c, nextDir);
			}
			else {
				if (map[r-1][c]!=-1)search(r-1, c, dir);
				else return;
			}
		}
		break;
	case 3://현재서쪽 다음남쪽
		if (!map[r+1][c]) clean(r+1, c, nextDir);
		else {
			bool unfinished = false;
			for (int i = 0; i < 4; i++) {
				int nr = r + dy[i];
				int nc = c + dx[i];
				if (!map[nr][nc]) {
					unfinished = true;
					break;
				}
			}
			if (unfinished) {
				search(r, c, nextDir);
			}
			else {
				if (map[r][c+1]!=-1)search(r, c+1, dir);
				else return;
			}
		}
		break;
	}
}

int main() {
	cin >> n >> m;
	cin >> r >> c >> dir;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if(map[i][j]==1)map[i][j]=-1;
		}
	}

	clean(r, c, dir);

	cout << ans << '\n';

	return 0;
}