이번 문제는 백준 14503번 로봇 청소기 문제로, 삼성 역테 기출 시뮬레이션 문제입니다.
풀이
함수
- check : 탐색하는 위치가 벽인지 아닌지 판단 해주는 합수입니다.
- goback : 뒤로 한칸 이동하기 위해서 현재 바라보고 있는 방향의 반대 방향을 리턴해줍니다.
- search : 로봇청소기의 시뮬레이션 함수입니다.
알고리즘
{ 1) 청소기가 돌면서 4방향중 청소 안된 곳이 있는곳이 있는지 없는지 판단한다. 2) 4방향 다 청소가 되어있거나 벽이면 멈춰서서
2-1) 현방향의 뒤가 벽이라면 종료
2-2) 현방향의 뒤가 벽이 아니라면 뒤로 이동
}
코드 및 주석
#include <iostream>
#include <vector>
using namespace std;
/* 갈수 있는 바닥인지 아닌지 판단 */
bool check(vector <vector<int>> &list, int N, int M, int x, int y) {
if (list[x][y] != 0)
return false;
return true;
}
/* 한칸 뒤 방향을 리턴 */
int goBack(int direction) {
switch (direction) {
case 0:
return 2;
break;
case 1:
return 3;
break;
case 2:
return 0;
break;
case 3:
return 1;
break;
}
}
/* 로봇 시뮬레이션 */
int search(vector <vector<int>> &list, int N, int M, int x, int y, int direction) {
int answer = 0;
int count;
int doContinue = 1;
//북동남서
int wayX[] = { -1,0,1,0 };
int wayY[] = { 0,1,0,-1 };
// doContinue <= 4방향 모두 청소되어있거나 벽이며 뒷방향도 벽일때 0으로 바뀌어 반복문을 종료하도록 한다.
while (doContinue) {
if (list[x][y] == 0) {
answer++;
list[x][y] = 2;
} // 이동후 청소하는 부분 ( 0 : 청소 안됨 / 1 : 벽 / 2: 청소 완료.
count = 3; // 4번 돌기 위한 카운트
while (count >= 0) {
// direction 바라보는 방향. 0 : 북 1 : 동 2 : 남 3: 서
if (direction != 0)
direction--;
else
direction = 3;
if (check(list, N, M, x + wayX[direction], y + wayY[direction])) {
x = x + wayX[direction];
y = y + wayY[direction];
break;
} // 4방향 돌다가 해당 방향이 청소 가능할시 그방향으로 이동한다.
count--;
}
/* 만약 4방향다 돌고 청소할 곳을 못찾았으면 count 는 -1 이 된다. 이제 뒷방향이 벽이면 종료, 벽이 아니면 후진한 후 다시 처음으로 돌아간다.*/
if (count == -1) {
direction = goBack(direction);
if (list[x + wayX[direction]][y + wayY[direction]] == 1)
doContinue = 0; //
else {
x = x + wayX[direction];
y = y + wayY[direction];
direction = goBack(direction);
}
}
}
return answer;
}
int main() {
int N, M;
int x, y, direction;
cin >> N >> M >> x >> y >> direction;
vector <vector<int>> list(N, vector<int>(M, 0));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
cin >> list[i][j];
cout << search(list, N, M, x, y, direction);
return 0;
}