- 백준 온라인저지 14503번 - 로봇 청소기
- https://www.acmicpc.net/problem/14503
- 완전탐색 문제로 문제에 나와있는 로직 그대로~ 작성하면 아무 문제없이 작동한다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n,m;
int a[50][50];
bool check[50][50] = {false,};
int r = -1;
int c = -1;
int d = -1; // 0 1 2 3 => 북쪽, 동쪽, 남쪽, 서쪽
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int ans = 0;
/*
1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.
*/
void print_map(){
cout << '\n';
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cout << check[i][j];
}
cout << '\n';
}
cout << "r : " << r << ' ' << "c : " << c << ' ' << "d : " << d << '\n';
}
int main (){
cin >> n >> m;
cin >> r >> c >> d;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++)
cin >> a[i][j];
}
while (true){
// 방문 안했다면 현재 위치를 방문으로 표시
if (check[r][c] == false){
check[r][c] = true;
ans++;
}
bool are_cleaned = true;
// 왼쪽부터 확인
for(int i=0; i<4; i++){
// 방향을 왼쪽 회전
d = (d==0) ? 3 : d-1;
// 현재의 왼쪽 좌표
int nx = r + dx[d];
int ny = c + dy[d];
//print_map();
//cout << nx << ' ' << ny << ' ' << '\n';
// 왼쪽이 비어있고 벽이 아니라면
if ( (check[nx][ny]==false) && (a[nx][ny] != 1)){
// 한칸 전진 후에 다시 처음부터 시작
r = nx;
c = ny;
are_cleaned = false;
break;
}
}
//print_map();
//char tmp;
//cin >> tmp;
if (!are_cleaned){
continue;
}
// 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는
if (are_cleaned
&& (a[r + dx[(d+2>3) ? d-2 : d+2]][c + dy[(d+2>3) ? d-2 : d+2]] == 1) ){
break;
}
// 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는 방향을 유지한 채 뒤로 후진
if (are_cleaned){
r = r + dx[(d+2>3) ? d-2 : d+2];
c = c + dy[(d+2>3) ? d-2 : d+2];
}
}
cout << ans << '\n';
return 0;
}
코드를 작성하는데는 1시간밖에 안걸렸지만 check[nx][ny]를 check[nx][nx]로 작성해버려서 2시간 동안 헤맸다... 이전에도 그랬지만 변수와 범위 신경 쓰자 거기서 판가름난다.