반응형
14503번: 로봇 청소기
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어
www.acmicpc.net
풀이 )
문제에 주어진 조건에 따라 구현하면 된다.
청소하지 않은 칸은 0, 벽은 1로 입력 받았기 때문에, 청소한 칸은 2를 입력하여 따로 방문 여부를 나타내기위한 배열을 사용하지않았다.
현재 로봇 청소기의 위치를 청소하고, 왼쪽 방향(d = (d+3)%4) 다음칸(board[nr][nc])을 확인하여 청소하지 않은 칸이면 이동한다.
주위 4칸이 모두 청소됐거나 벽일 경우 왼쪽으로 4번 회전하여 원래의 방향이므로 현재 방향의 뒷방향으로 이동하기 위해, br = r-dx[d]; bc = c-dy[d];를 취해준 후, 뒤로 이동한다. 이때 뒤가 벽(1)이면 로봇청소기는 멈춘다.
(br, bc)에 대해서는 입력 테두리가 모두 벽으로 둘러쌓였기 때문에 배열 범위 밖으로 나가는 유효성 검사를 해주지 않았다.
마지막으로 배열에서 '2'인 칸의 수를 센다.
#include <iostream>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int board[50][50];
int main(void){
int n, m;
cin >> n >> m;
int r, c, d;
cin >> r >> c >> d;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
cin >> board[i][j];
int cnt = 0;
while(1){
board[r][c] = 2;
bool flag = false;
for(int i = 0; i < 4; ++i){
d = (d+3)%4;
int nr = r+dx[d];
int nc = c+dy[d];
if(!board[nr][nc]){
flag = true;
r = nr;
c = nc;
break;
}
}
if(flag)
continue;
int br = r-dx[d];
int bc = c-dy[d];
if(board[br][bc] == 1)
break;
r = br;
c = bc;
}
int ans = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(board[i][j] == 2)
ans++;
cout << ans << '\n';
}
반응형
'문제풀이 > 백준' 카테고리의 다른 글
| [C++] 백준 - 1107 : 리모컨 (0) | 2020.12.28 |
|---|---|
| [C++] 백준 - 17471 : 게리맨더링 (0) | 2020.12.24 |
| [C++] 백준 - 1719 : 택배 (0) | 2020.12.22 |
| [C++] 백준 - 15684 : 사다리 조작 (0) | 2020.12.21 |
| [C++] 백준 - N과 M 모음 (15649, 15650, 15651, 15652, 15654, 15655, 15656, 15657, 15663, 15664, 15665, 15666) (0) | 2020.12.19 |
