본문 바로가기
알고리즘/SW역량테스트 기출문제

[백준 14503번] 로봇 청소기 (시뮬레이션)

by 지칸 2021. 4. 16.

본 포스팅에서는 삼성 SW 역량테스트 기출문제 중 시뮬레이션 유형을 풀이하려고 합니다. 백준 사이트의 14503번 문제 로봇 청소기입니다. 이 문제는 문제에서 요구하는 프로세스를 순서대로 지켜가면서 요구하는 동작을 수행하도록 코딩하면 됩니다. 어떤 알고리즘이 사용되는 문제는 아니기 때문에 문제 이해도를 중요시합니다.

 

2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 14503번] 로봇 청소기 (시뮬레이션)

2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 15685번] 드래곤 커브 (시뮬레이션)

2021.04.17 - [알고리즘/SW역량테스트 기출문제] - [백준 14891번] 톱니바퀴 (시뮬레이션)

 

안녕하세요. 지칸입니다.

오늘 풀이할 문제는 시뮬레이션 유형의 백준 14503번 로봇 청소기입니다. 채용과정인 역량테스트 A형 말고 B형으로 가보면 대부분이 시뮬레이션 + Hash 문제이고 실제 현업에서도 대부분 요구사항 구현 방법에 더 치중하는 편입니다. 어떤 알고리즘을 쓰는 경우는 매우 드물었습니다...

 

1) 문제 이해

2) 구조 잡기

 

저의 결론) 시뮬레이션 문제가 사실 가장 까다롭고 문제 유형을 만들 수가 없다. 알고리즘을 이용한 문제는 대부분 기본 틀이 존재하기 때문에 약간의 수정으로 풀이가 가능하지만 이런 시뮬레이션 유형은 문제 이해도에 달려있다.

1) 문제 이해

문제 출처 : www.acmicpc.net/problem/14503

 

문제)

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1 ×1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

  1. 현재 위치를 청소한다.
  2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색을 진행한다.
    1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
    2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
    3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
    4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

 

-> 문제 해석

  • 2차원 맵의 크기 NxM
  • 빈칸, 벽, 청소한 곳
  • 무한루프로 계속 반복하다가 2-4. 조건으로 탈출
  • 현재 방향 기준으로 왼쪽 좌표 필요, 2-1에서 왼쪽 방향 빈칸 여부 체크용
  • 현재 방향 기준으로 뒤쪽 좌표 필요, 2-4에서 뒤쪽 후진 또는 벽 체크 용

입력)

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈칸은 0, 벽은 1로 주어진다. 지도의 첫 행, 마지막 행, 첫 열, 마지막 열에 있는 모든 칸은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈칸이다.

 

-> 입력 해석

  • 맵의 최대 크기 50
  • d 0123 -> 북동 남서, 북 기준으로 시계방향,  dydx방식을 쓸 건지 고민, 어떤 식으로 방향을 체크할지..
  • 빈칸 0, 벽 1, 청소 2
  • 벽으로 둘러싸임, 현재 기준 4방향 좌표의 상태를 확인할 때 맵 범위 체크할 필요 없음

출력)

로봇 청소기가 청소하는 칸의 개수를 출력한다.

 

-> 출력 해석

  • 1번 청소하기 할 때만 카운트 증가

2) 구조 잡기

시작은 항상 동일하게 시작합니다.

2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비

2-1) 초기 세팅

input를 입력받는 기본 뼈대를 잡아줍니다. 기존 조합, DFS 등의 문제와 다르게 청소기의 위치, 방향 말고는 별로도 저장할 필요가 없습니다.

#include <iostream>
using namespace std;
#define MAX_N 50
#define EMPTY 0
#define WALL 1
#define CLEAR 2
int N, M;
int map[MAX_N][MAX_N] = { 0, };
struct coor
{
	int r;
	int c;
};
coor sweeper;  //청소기의 위치  r,c
int direct = 0; //청소기의 방향
int sol = 0; // 청소 횟수

int main() {
	//input
	cin >> N >> M;
	int r, c, dr;
	cin >> r >> c >> dr;  // 0북 1동 2남 3서  항상 방향의 왼쪽만 필요
	sweeper.r = r;
	sweeper.c = c;
	direct = dr;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> map[i][j];
		}
	}
	// 1. 현재 위치 청소 0->1
	// 2. 탐색
	// 2-1. 왼쪽방향에 청소가능? 가능하다면 왼쪽으로 회전, 1칸 전진, 1번으로
	// 2-2. 왼쪽방향에 청소불가능? 불가능하다면 왼쪽으로 회전
	// 2-3. 4방향 모두 청소 불가능? 방향 유지, 1칸 후진 2번으로
	// 2-4. 4방향 모두 청소 불가능, 뒤쪽 벽이면? 종료

	cout << sol;
	return 0;
}

코드 작성을 옛날 시험 보기 전에 공부하면서 작성하던 내용을 가져왔습니다. 그래서 현재 기준 왼쪽 방향, 뒤쪽 방향등 찾아가는 방식이 스마트하지 못하게 코딩되어있습니다. 다만 훨씬 직관적이라 생각하여 수정 없이 가져왔습니다. 현재 청소기의 위치와 현재 방향만 저장해두세요.

 

2-2) 1단계 현재 위치 탐색

시작하자마다 1단계를 시작하고, 이후 2-1단계에서 1단계로 다시 되돌아 가는 과정이 있습니다. 이 부분은 아래처럼 1단계만 따로 수행하고 2단계 무한반복의 2-1단계 동작에서 1단계 함수를 바로 호출하도록 하였습니다.

void process1() {// 1. 현재 위치 청소 EMPTY -> CLEAR
	map[sweeper.r][sweeper.c] = CLEAR; //현재 청소기 위치를 청소
	sol++;  //청소 횟수 1증가
}

int main() {
	//.. 기존코드 생략..
	process1();
	while (exitcheck) {
		bool actionCheck = false;
		actionCheck = process2_3();
		if (!actionCheck) { // false면 2단계부터 다시
			process2();
		}
	}
    
	cout << sol;
	return 0;
}

맵의 상태를 빈칸에서 청소했으므로 변경해주고 카운트를 증가시키면 끝입니다.

 

2-3) 2-1단계, 2-2단계 왼쪽 탐색 구현하기

2단계로 들어오면 현재 청소기의 방향 기준으로 왼쪽 방향에 청소 가능한 빈칸이 있는지 체크하는 과정이 필요합니다. 이후 빈칸이 있으면 2-1단계, 빈칸이 없으면 2-2단계로 분기하는 동작을 구현합니다.

bool IsCleanable() { // 왼쪽방향에 청소 가능한 칸이 있는가
	//현재 방향에서의 왼쪽?
	int checkPoint_r = 0;
	int checkPoint_c = 0;

	if (direct == 0) {
		checkPoint_r = sweeper.r;
		checkPoint_c = sweeper.c - 1;
	}
	else if (direct == 1) {
		checkPoint_r = sweeper.r - 1;
		checkPoint_c = sweeper.c;
	}
	else if (direct == 2) {
		checkPoint_r = sweeper.r;
		checkPoint_c = sweeper.c + 1;
	}
	else if (direct == 3) {
		checkPoint_r = sweeper.r + 1;
		checkPoint_c = sweeper.c;
	}

	if (map[checkPoint_r][checkPoint_c] == EMPTY) 
		return true;
	else 
		return false;
}

void process2() {
	if (IsCleanable()) { // 2-1. 왼쪽방향에 청소가능? 가능하다면 왼쪽으로 회전, 1칸 전진, 1번으로
		if (direct == 0) {
			direct = 3;  // 회전
			sweeper.c = sweeper.c - 1; // 1칸 전진		
		}
		else if (direct == 1) {
			direct = 0;
			sweeper.r = sweeper.r - 1;			
		}
		else if (direct == 2) {
			direct = 1;
			sweeper.c = sweeper.c + 1;			
		}
		else if (direct == 3) {
			direct = 2;
			sweeper.r = sweeper.r + 1;			
		}
		process1();  // 1번으로
	}
	else { // 2-2. 왼쪽방향에 청소불가능? 불가능하다면 왼쪽으로 회전, 2번에서 시작
		if (direct == 0) direct = 3; //회전
		else if (direct == 1) direct = 0;
		else if (direct == 2) direct = 1;
		else if (direct == 3) direct = 2;
	}
}

코드에서 보는 것처럼 청소기의 현재 방향 기준으로 왼쪽을 찾는 과정이 스마트하지 않습니다. 노가다로 북쪽일 때의 왼쪽 좌표, 동쪽일때의 왼쪽좌표 등등 4방향에 대해 모두 검색하도록 했습니다. 왼쪽 좌표를 찾았다면 맵에서 해당 좌표가 빈칸인지를 조건문으로 검색하면 IsCleanable 함수가 구현됩니다.

 

IsCleanable 함수의 결과에 따라 2-1, 2-2로 분기하고 각 단계의 동작을 구현합니다. 2-1단계의 경우, 왼쪽으로 회전하고, 그 좌표로 청소기의 위치를 이동시킵니다. 그리고 1단계를 수행하도록 합니다. 앞에서 설명한 것처럼 이 부분에서 문제 요구사항과 코드 간에 약간의 동작 순서에 이상함을 느낄 수 있습니다. 2-2단계는 단순히 회전만 시키면 됩니다.

 

2-4) 2-3단계, 2-4단계 청소할 곳이 없을 때의 동작 구현하기

이분도 노가다의 형태로 코드를 작성해봤습니다. 4방향이 모두 청소할 곳이 없는지 체크하는 함수와 청소기의 뒤가 벽인지 체크하는 함수를 별도로 구현했습니다. 

bool Isallcleaning() {
	bool check = true; // true면 4방향 모두 청소됨
	int checkPoint_r = 0;
	int checkPoint_c = 0;

	checkPoint_r = sweeper.r;
	checkPoint_c = sweeper.c + 1;
	if (map[checkPoint_r][checkPoint_c] == EMPTY) check = false;

	checkPoint_r = sweeper.r;
	checkPoint_c = sweeper.c - 1;
	if (map[checkPoint_r][checkPoint_c] == EMPTY) check = false;

	checkPoint_r = sweeper.r + 1;
	checkPoint_c = sweeper.c;
	if (map[checkPoint_r][checkPoint_c] == EMPTY) check = false;

	checkPoint_r = sweeper.r - 1;
	checkPoint_c = sweeper.c;
	if (map[checkPoint_r][checkPoint_c] == EMPTY) check = false;

	return check;
}
bool Isbackwall() { //뒤쪽이 벽인가? 1이면 벽, 0이면 벽아님
	int checkPoint_r = 0;
	int checkPoint_c = 0;
	if (direct == 0) {
		checkPoint_r = sweeper.r + 1;
		checkPoint_c = sweeper.c;
	}
	else if (direct == 1) {
		checkPoint_r = sweeper.r;
		checkPoint_c = sweeper.c - 1;
	}
	else if (direct == 2) {
		checkPoint_r = sweeper.r - 1;
		checkPoint_c = sweeper.c;
	}
	else if (direct == 3) {
		checkPoint_r = sweeper.r;
		checkPoint_c = sweeper.c + 1;
	}

	if (map[checkPoint_r][checkPoint_c] == WALL)
		return true;
	else 
		return false;
}
bool process2_3() {
	bool action = false; // true면 다시 2-3부터 false면 2번으로
	if (Isallcleaning() & !Isbackwall()) { // 2-3. 4방향 모두 청소 불가능, 뒤쪽 벽아니면? 방향 유지, 1칸 후진 2번으로 
		if (direct == 0) sweeper.r = sweeper.r + 1; // 1칸 후진
		else if (direct == 1) sweeper.c = sweeper.c - 1;
		else if (direct == 2) sweeper.r = sweeper.r - 1;
		else if (direct == 3) sweeper.c = sweeper.c + 1;
		action = true;
	}
	else if (Isallcleaning() & Isbackwall()) {// 2-4. 4방향 모두 청소 불가능, 뒤쪽 벽이면? 종료
		exitcheck = 0;
		action = true;
	}
	return action;
}

Isallcleaning 함수는 4방향 중 한 곳이라도 빈칸이 존재하면 false를 발생하도록 했습니다. 그러면 2-2단계에 의해 청소기를 회전시키면서 그 빈칸을 찾아서 청소하도록 되어 순서가 흘러가도록 했습니다. Isbackwall 함수는 IsCleanable 함수와 다른 것이 없습니다. 바라보는 좌표와 벽인지 빈칸인지의 차이만 존재합니다.

 

2-3단계는 4방향 모두 청소할 곳이 없고 뒤가 벽이 아니면 후진하는 동작이고 2-4단계는 뒤가 벽이면 종료하도록 하는 동작입니다. exitcheck가 유일하게 이곳에서만 false로 변경되고 무한 반복문을 빠져나올 수 있습니다.

반응형
저작자표시 비영리 변경금지

'알고리즘 > SW역량테스트 기출문제' 카테고리의 다른 글

[백준 15685번] 드래곤 커브 (시뮬레이션)  (0) 2021.04.16
[백준 14888번] 연산자 끼워넣기 (순열)  (0) 2021.04.16
[백준 14889번] 스타트와 링크 (조합)  (0) 2021.04.14
[백준 15686번] 치킨배달 (조합)  (0) 2021.04.08
[백준 14502번] 연구소 (조합, BFS)  (0) 2021.04.08

관련글

댓글

티스토리툴바