728x90
반응형
이 문제는 시뮬레이션, bfs문제이다.
- 현재 위치를 청소한다.
- 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
- 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
- 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
- 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.
우선 왼쪽 방향으로 전진하는 함수, 후진하는 함수를 따로 작성해뒀다.
int turnDirection(int pd){
int direction;
switch(pd){
case 0:
return 3;
case 1:
return 0;
case 2:
return 1;
default:
return 2;
}
}
int backDirection(int pd){
switch(pd){
case 0:
return 2;
case 1:
return 3;
case 2:
return 0;
default:
return 1;
}
}
현 위치에서 4가지 방향에 대해 청소를 하지않은 공간을 탐색한다.
1이라면, 왼쪽 방향으로 회전 후, 앞으로 전진한 좌표를 queue에 삽입한다.
방향을 바꿨으므로 현 위치에서 4가지 방향을 살펴볼 이유가 없기 때문에 반복문을 탈출한다.
그리고 2인지 3인지를 확인할 필요가 없다는 boolean값을 설정한다.
tuple<int,int,int> node = q.front();
q.pop();
int direction = get<2>(node);
for(int i = 0; i < 4; i++){
direction = turnDirection(direction);
int dx = directx[direction] + get<0>(node);
int dy = directy[direction] + get<1>(node);
if(dx < n && dx >= 0 && dy < m && dy >= 0 && vertex[dx][dy] == 0){
answer++;
vertex[dx][dy] = 2;
isBlocked = false;
q.push({dx,dy,direction});
break;
}
}
그렇지만 4가지 방향에 대해 청소를 하지 않은 공간을 찾지 못했다면 뒤쪽 방향이 벽인지 확인 후 후진한다,
그리고 방향과 좌표를 queue에 삽입한다.
if(isBlocked){
int direction = backDirection(get<2>(node));
int dx = directx[direction] + get<0>(node);
int dy = directy[direction] + get<1>(node);
if(dx >= 0 && dx < n && dy >= 0 && dy < m && vertex[dx][dy] != 1){
q.push({dx,dy,get<2>(node)});
}
}
완성된 코드는 이렇다.
//로봇 청소기
#include <iostream>
#include <queue>
#include <tuple>
using namespace std;
int vertex[50][50];
int directx[] = {-1,0,1,0};
int directy[] = {0,1,0,-1};
int n,m;
int turnDirection(int pd){
int direction;
switch(pd){
case 0:
return 3;
case 1:
return 0;
case 2:
return 1;
default:
return 2;
}
}
int backDirection(int pd){
switch(pd){
case 0:
return 2;
case 1:
return 3;
case 2:
return 0;
default:
return 1;
}
}
int bfs(int x, int y, int d){
queue<tuple<int,int,int>> q;
q.push({x,y,d});
vertex[x][y] = 2;
int answer = 1;
while(!q.empty()){
bool isBlocked = true;
tuple<int,int,int> node = q.front();
q.pop();
int direction = get<2>(node);
for(int i = 0; i < 4; i++){
direction = turnDirection(direction);
int dx = directx[direction] + get<0>(node);
int dy = directy[direction] + get<1>(node);
if(dx < n && dx >= 0 && dy < m && dy >= 0 && vertex[dx][dy] == 0){
answer++;
vertex[dx][dy] = 2;
isBlocked = false;
q.push({dx,dy,direction});
break;
}
}
if(isBlocked){
int direction = backDirection(get<2>(node));
int dx = directx[direction] + get<0>(node);
int dy = directy[direction] + get<1>(node);
if(dx >= 0 && dx < n && dy >= 0 && dy < m && vertex[dx][dy] != 1){
q.push({dx,dy,get<2>(node)});
}
}
}
return answer;
}
int main(void){
cin >> n >> m;
int x, y, d;
cin >> x >> y >> d;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> vertex[i][j];
}
}
cout << bfs(x,y,d);
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 경사로 (0) | 2020.12.23 |
---|---|
[algorithm] 백준 - 연산자 끼워넣기 (0) | 2020.12.22 |
[algorithm] 백준 - 구슬탈출(2) (0) | 2020.12.18 |
[algorithm] 백준 - 스도쿠 (0) | 2020.11.19 |
[algorithm] 백준 - 숨바꼭질 2 (0) | 2020.11.17 |