728x90
https://www.acmicpc.net/problem/14503
문제
입력
출력
로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int N, M;
int r, c, d;
int adj[51][51];
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; //0 1 2 3
int ans = 0;
bool isZero = false;
bool visited[51][51];
void dfs(int x, int y){
isZero = false;
// 1번
if(adj[x][y] == 0 && !visited[x][y]){
visited[x][y] = true;
ans++;
}
//3번
for(int i=0; i<4; ++i){
int d2 = (d + 3 - i) % 4;
int nx = x + dir[d2][0];
int ny = y + dir[d2][1];
if(nx < 0 || nx >= N){
continue;
}
if(ny <0 || ny >= M){
continue;
}
if(adj[nx][ny] == 0 && !visited[nx][ny]){
d = d2;
dfs(nx, ny);
isZero = true;
break;
}
}
if(!isZero){
// 2번
int d2 = (d+2) % 4;
int nx = dir[d2][0] + x;
int ny = dir[d2][1] + y;
if(nx >= 0 && nx < N && ny >= 0 && ny < M && adj[nx][ny] == 0){
dfs(nx, ny);
}
else{
return;
}
}
}
int main(void){
cin >> N >> M;
cin >> r >> c >> d;
memset(visited, false, sizeof(visited));
for(int i=0; i<N; ++i){
for(int j=0; j<M; ++j){
cin >> adj[i][j];
}
}
dfs(r, c);
cout << ans;
}
케이스들을 잘 쪼개면 풀 수 있는 문제이다.
이 때, 문제를 잘 읽어봐야 할게 만약 칸의 값이 1이면 청소 된 상태가 아닌 벽이라는 뜻으로 청소 된 상태를 확인해주는 visited 배열을 하나 더 선언해야 한다. (이걸 잘 못읽어서 좀 많이 헤맸다...)
그리고 주목해야할 점이 방향이 반시계 방향으로 90도 가는 점이나 후진하는 점인데 이 방향들을 %연산자를 사용해 잘 해결해 주었다.
1. int d2 = (d + 3 - i) % 4; (반시계 방향으로 90도)
2. int d2 = (d+2) % 4; (바라보는 방향의 반대 방향)
728x90
반응형
'PS > DFS, BFS' 카테고리의 다른 글
[16234] 인구 이동 (0) | 2023.07.18 |
---|---|
[16236] 아기 상어 (0) | 2023.07.13 |
[9205] 맥주 마시면서 걸어가기 (0) | 2023.06.18 |
[2573] 빙산 (0) | 2023.06.18 |
[2644] 촌수계산 (0) | 2023.06.13 |