https://www.acmicpc.net/problem/14503
14503번: 로봇 청소기
로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어
www.acmicpc.net
최종 코드
hwayeon351/BEAKJOON-Algorithms
백준 코딩테스트 풀이. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ14503
//
// Created by Hwayeon on 2021/07/29.
//
#include <iostream>
using namespace std;
int N, M;
int map[50][50] = {0,};
struct robots{
int d;
int x;
int y;
};
robots robot;
//상 우 하 좌
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int clean_area = 0;
void clean(){
while(true){
//1. 현재 위치 청소
if(map[robot.y][robot.x] == 0){
map[robot.y][robot.x] = 2;
clean_area++;
}
//2.
bool check = false;
for(int i=0; i<4; i++){
int next_d = (4 + robot.d-1) % 4;
int nx = robot.x + dx[next_d];
int ny = robot.y + dy[next_d];
//2-a
if(map[ny][nx] == 0){
robot.d = next_d;
robot.x = nx;
robot.y = ny;
check = true;
break;
}
//2-b
robot.d = next_d;
}
if(!check){
int back_d = (4 + robot.d-2) % 4;
int back_x = robot.x + dx[back_d];
int back_y = robot.y + dy[back_d];
if(map[back_y][back_x] != 1){
robot.x = back_x;
robot.y = back_y;
}
//2-d
else return;
}
}
}
int main(int argc, const char * argv[]) {
cin >> N >> M;
cin >> robot.y >> robot.x >> robot.d;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> map[i][j];
}
}
clean();
cout << clean_area << endl;
return 0;
}풀이 과정
풀이 시간 33분
//
// main.cpp
// BJ14503
//
// Created by Hwayeon on 2021/07/29.
//
#include <iostream>
using namespace std;
int N, M;
//청소한 곳 -> 2, 청소 안한 곳 -> 0
int map[50][50] = {0,};
struct robots{
int d;
int x;
int y;
};
robots robot;
//상 우 하 좌
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int clean_area = 0;
void clean(){
while(true){
//1. 현재 위치 청소
if(map[robot.y][robot.x] == 0){
map[robot.y][robot.x] = 2;
clean_area++;
}
//2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 탐색
bool check = false;
for(int i=0; i<4; i++){
//현재 위치에서의 왼쪽 방향으로 방향 설정
int next_d = (4 + robot.d-1) % 4;
int nx = robot.x + dx[next_d];
int ny = robot.y + dy[next_d];
//2-a. 왼쪽 방향에 아직 청소하지 않은 공간이 있는 경우
if(map[ny][nx] == 0){
//로봇청소기의 방향을 회전하고, 한 칸 전진한 위치로 바꿔준 후, for문을 나간다
robot.d = next_d;
robot.x = nx;
robot.y = ny;
check = true;
break;
}
//2-b. 왼쪽 방향에 청소할 공간이 없는 경우
robot.d = next_d;
}
//네 방향 모두 청소할 곳이 없는 경우,
if(!check){
//후진 방향, 한 칸 후진할 위치를 찾는다
int back_d = (4 + robot.d-2) % 4;
int back_x = robot.x + dx[back_d];
int back_y = robot.y + dy[back_d];
//2-c. 후진할 곳이 벽이 아닌 경우, 로봇의 위치를 바꿔준다
if(map[back_y][back_x] != 1){
robot.x = back_x;
robot.y = back_y;
}
//2-d. 후진할 수 없는 경우 로봇청소기의 작동을 멈춘다
else return;
}
}
}
int main(int argc, const char * argv[]) {
cin >> N >> M;
cin >> robot.y >> robot.x >> robot.d;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> map[i][j];
}
}
clean();
cout << clean_area << endl;
return 0;
}
//시간복잡도 = O(n^2), 공간복잡도 = O(n^2)이전 풀이
풀이 시간 1시간 36분
//
// main.cpp
// BJ14503
//
// Created by Hwayeon on 2021/01/10.
//
#include <iostream>
#include <cmath>
using namespace std;
int N, M, d, r_x, r_y;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int back[4] = {2, 3, 0, 1};
int room[50][50];
bool clean[50][50] = {false,};
int cleaned_area = 0;
void cal_clean_area(){
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
if(clean[i][j]) cleaned_area++;
}
}
}
void clean_room(int x, int y, int dir){
if(clean[y][x] == false) clean[y][x] = true;
for(int i=1; i<=4; i++){
int left = (dir-i+4)%4;
int new_x = x+dx[left];
int new_y = y+dy[left];
if(room[new_y][new_x] == 0 && clean[new_y][new_x] == false){
clean_room(new_x, new_y, left);
return;
}
}
if(room[y+dy[back[dir]]][x+dx[back[dir]]] == 0) clean_room(x+dx[back[dir]], y+dy[back[dir]], dir);
else if(room[y+dy[back[dir]]][x+dx[back[dir]]] == 1) cal_clean_area();
}
int main(int argc, const char * argv[]) {
cin >> N >> M;
cin >> r_y >> r_x >> d;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> room[i][j];
}
}
clean_room(r_x, r_y, d);
cout << cleaned_area << endl;
return 0;
}1. 문제 이해하기
풀이 시간이 지체됐던 원인 중 하나이다. 나는 문제를 이해하는데에 30분 소요했다.
처음에 문제를 읽었을 때 내가 이해하지 못했던 부분은 2-a와 2-b에서 의미하는 "그 방향"이 어느 방향을 뜻하는 것인지이다.
여기에서 "그 방향"은 왼쪽 방향을 의미하는 것이었다.
나는 문제에 나와있는 예제를 노트에 그려, 로봇 청소기의 작동 순서를 직접 따라가보면서 이해할 수 있었다.
위 그림처럼 로봇의 이동경로를 따라가보면 로봇이 청소한 영역이 57인 것을 알 수 있다.
2. 재귀 함수 설계
문제의 로봇 청소기의 작동 순서를 읽어보면서 재귀로 문제를 풀어나가면 좋겠다고 생각했다.
void clean_room(int x, int y, int dir){
if(clean[y][x] == false) clean[y][x] = true;
for(int i=1; i<=4; i++){
int left = (dir-i+4)%4;
int new_x = x+dx[left];
int new_y = y+dy[left];
if(room[new_y][new_x] == 0 && clean[new_y][new_x] == false){
clean_room(new_x, new_y, left);
return;
}
}
if(room[y+dy[back[dir]]][x+dx[back[dir]]] == 0) clean_room(x+dx[back[dir]], y+dy[back[dir]], dir);
else if(room[y+dy[back[dir]]][x+dx[back[dir]]] == 1) cal_clean_area();
}로봇의 현재 위치와 방향을 매개변수로 한 재귀함수를 구현했다.
1. 현재 위치가 청소가 안 된 상태이면 청소를 한다.
2. 현재 방향을 기준으로 왼쪽 방향으로 회전하며, 청소를 할 공간이 있으면 청소해준다. -> clean_room(new_x, new_y, left)
그리고 함수를 종료한다.
3. 만약 2.과정에서 함수가 종료되지 않으면 4방향이 청소가 이미 된 상태이거나, 벽인 경우이다.
이 경우에서, 현재 위치에서 뒤로 한 칸 물러난 곳이
1) 벽이 아니라면(청소가 이미 된 곳을 의미), 현재 방향을 유지한 채 뒤로 한 칸 이동한다.
-> clean_room(x+dx[back[dir]], y+dy[back[dir]], dir)
2) 벽이라면 지금까지 청소한 구역을 세고 청소를 끝낸다. -> cal_clean_area()
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 13460 구슬 탈출 2 C++ (3) | 2021.01.18 |
|---|---|
| 백준 14888 연산자 끼워넣기 C++ (0) | 2021.01.17 |
| 백준 14890 경사로 C++ (0) | 2021.01.14 |
| 백준 14502 연구소 C++ (0) | 2021.01.11 |
| 백준 14889 스타트와 링크 C++ (0) | 2021.01.06 |