반응형
[BOJ][C++] 14503 로봇청소기
풀이
1. 청소를 한다.
이 때 한 번 청소한 곳은 또 방문하면 안되기 때문에 visited를 이용합니다. 방향을 바꿀땐 사방을 다 탐색하면 후진해야하기 때문에 이를 cnt를 이용해 꼭 체크해줍니다.
1-1. map[nx][ny]가 청소할 수 있을 때 (map[nx][ny]==0 && visited[nx][ny]==0) : 다음 좌표, dir 바꾸어 func호출
1-2. map[nx][ny]가 청소할 수 없을 때 : 청소기의 방향 회전이 필요합니다. = dir, cnt+1 로 func호출
2. 후진해야 하는 경우 (cnt==4)
cnt==4 일때는 사방이 벽이거나 청소를 한 경우입니다. 이 때, 후진을 해줘야하는데 후진을 할 수 있다면 다음 좌표로 옮기면 되고, 후진이 불가능하면 종료해주면 됩니다.
2-1. 후진이 가능한 경우 : 범위체크와 벽이 아닌 경우 = 다음 좌표, dir 그대로
2-2. 후진이 불가능한 경우 : 종료(return)
코드
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string.h>
using namespace std;
int n, m;
int r, c, d;
int res = 1;
int map[51][51];
int visited[51][51];
int dx[] = { 0,-1,0,1 }; // 회전 좌표
int dy[] = { -1,0,1,0 };
int bx[] = {1,0,-1,0}; // 후진 좌표
int by[] = {0,-1,0,1};
void cleaning(int x, int y, int dir, int cnt) {
if (cnt == 4) {
//후진
int nx = x + bx[dir];
int ny = y + by[dir];
if (map[nx][ny] == 1 || nx <= 0 || ny <= 0 || nx >= n - 1 || ny >= m - 1) {
return;
}
else {
cleaning(nx, ny, dir, 0);
}
}
else {
int nx = x + dx[dir];
int ny = y + dy[dir];
//청소가능
if (map[nx][ny] == 0 && visited[nx][ny]==0) {
res++;
visited[nx][ny] = 1;
if (dir - 1 < 0) dir = 4;
cleaning(nx, ny, dir - 1, 0);
}
//불가능
else {
if (dir - 1 < 0) dir = 4;
cleaning(x, y, dir - 1, cnt + 1);
}
}
}
int main() {
scanf("%d %d", &n, &m);
scanf("%d %d %d", &r, &c, &d); //현재위치rc, 방향d
memset(visited, 0, sizeof(visited));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%d", &map[i][j]);
}
}
visited[r][c] = 1;
cleaning(r, c, d, 0);
printf("%d", res);
}
반응형
'CS > Algorithm' 카테고리의 다른 글
[BOJ][16234] 인구이동 (0) | 2019.09.01 |
---|---|
[BOJ][17144] 미세먼지 안녕! (2) | 2019.08.13 |
[BOJ][C++] 15686 치킨배달 (0) | 2019.06.13 |
[SWEA][C++] 5650 핀볼게임 (0) | 2019.03.28 |
[SWEA][C++] 2117 홈방범서비스 (0) | 2019.03.09 |
댓글