[백준알고리즘] 14503번 : 로봇 청소기 #스터디 3주차

문제는 아래 사이트에 들어가면 확인 할 수 있다. 

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

 

 

먼저 선언한 변수 및 배열들이다.

N : map 의 세로 크기 

M : map 의 가로 크기

r : row

c : column 

d : 방향  //0 : 북쪽 , 1 : 동쪽, 2 : 남쪽, 3 : 서쪽

cnt : 청소하는 칸의 개수를 세어주기 위한 변수

p : 현재 좌표 위치에서 북 동 남 서쪽으로의 위치값을 표현하기 위한 2차원 배열

map : N*M짜리 청소하기 위한 전체 배열

 

< main함수 >

입력에서 주어진 대로 첫째줄에 N과 M을 띄어쓰기 구분자로 받을 수 있게 했다. 

또 두번째 줄에도 r, c, d를 입력받았다. 

 

for문을통해 map의 각 칸마다 벽인지, 벽이 아닌지를 입력받았다. 

 

그 후 dfs 를 돌리면 된다.  

 

< dfs 함수 >

현재 로봇 청소기가 위치한 row와 column, 그리고 바라보고 있는 방향을 매개변수로 입력받는다. 

 

map[r][c] == 0 이면 청소하지 않은 구역이므로 그 구역을 -1 값으로 바꿔준다. 

-1이 들어간 배열의 칸은 청소했다고 표시를 해주는 것이다. 

또 청소한 칸의 개수를 세어주기 위하여 -1로 변하는 순간에 같이 cnt 값도 1증가시켜 주었다. 

 

for문으로 i를 0 부터 4까지 총 네번 돌리는데 이는 동서남북을 다 확인하기 위해서이다. 

반시계 방향 순으로 순회하므로 새로운 d 를 할당해주기 위하여 nd라는 변수를 생성했다. 

nd 는 (d + 3 - i) % 4 하게 될 경우 반시계 방향으로 회전한 값이 된다. 

또 nr과 nc라는 변수로 새로 업데이트 된 로봇이 바라보는 방향에 따른 새로운 좌표값을 할당해주었다. 

nd는 새로운 방향이므로 0, 1, 2, 3번째 인덱스에 (북, 동, 남, 서) 존재하는 각 값들을 확인하여 r 과 c에 더함으로서 새로운 좌표값이 된다. 

 

또 nr 과 nc가 map 밖을 벗어나는지 확인해주었으며, 

map[nr][nc] 값이 1이 아닐때  == 청소하지 않은 구역 일 때 dfs를 재귀로 불러주었다.

 

중요한 것은 조건 c인데, 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다 는 조건이다. 

그경우는  for문을 다돌고 나왔을 때이다. 바라보는 방향을 유지한 채 한칸 후진을 하기 떄문에 nd는 생성하지 않았고, 

(d + 2) % 4 를 계산하면 180도 방향으로 갈 수 있으므로 새로 nr과 nc값을 주었다. 

그리고 그 nr, nc좌표값에 존재하는 것이 벽이면 작동을 멈춘다. 

벽이 아닐 경우엔  dfs를 다시 재귀호출 해준다. 

 

 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<iostream> #include<queue> #define MAX 50 using namespace std; int N, M, r, c, d; int cnt = 0; int p[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; //위의 d를 인덱스 삼아 나타낸 방향 상대값들 //북 동 남 서 int map[MAX][MAX] = { 0 };   void dfs(int r, int c, int d) {     if (map[r][c] == 0) {//청소         cnt++;         map[r][c] = -1;     }     for (int i = 0; i < 4; i++) {         int nd = (d + 3 - i) % 4;         int nr = r + p[nd][0];         int nc = c + p[nd][1];         if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;         if (!map[nr][nc]) dfs(nr, nc, nd);              }       int nr = r + p[(d + 2) % 4][0];     int nc = c + p[(d + 2) % 4][1];     if (map[nr][nc] == 1) {         cout << cnt << '\n';         exit(0);     }     dfs(nr, nc, d); } int main() {     cin >> N >> M;     cin >> r >> c >> d;     for (int i = 0; i < N; ++i) {         for (int k = 0; k < M; ++k) {             cin >> map[i][k];         }     }     dfs(r, c, d);     return 0; } Colored by Color Scripter

cs