[C] 백준 14503번 로봇 청소기
안녕하세요 :D
벌써 설 연휴의 마지막 날이네요..... (매우 슬픔)
오늘은 연휴의 마지막 날을 맞아,, 삼성 SW 역량 테스트 기출문제를 풀어보았습니다.
14503번은 시뮬레이션 문제이기 때문에 문제에서 주어진 조건만 제대로 확인한다면 쉽게 구현할 수 있습니다!
1. 현재 위치를 청소하기
2. 현재를 기준으로 탐색하기
3. 청소하는 칸의 개수 구하기
저는 문제를 쉽제 해결하기 위해 주어진 단계를 크게 3가지로 나누어 보았습니다.
1. 현재 위치를 청소하기
현재 위치가 청소가 되었는지/되지 않았는지 여부를 확인하기 위해
입력으로 들어온 장소 배열(area) 외에 별도의 cleaned 배열을 선언하였습니다.
그리고 현재의 위치에 해당하는 cleaned 배열의 값을 1로 설정함으로써 청소가 되었음을 표현하였습니다.
2. 현재를 기준으로 탐색하기
(2-c와 2-d 구현)
저는 네 방향 모두 청소가 되어 있거나 벽인 경우의 예외 처리를 먼저 해주었습니다.
해당 케이스를 확인하기 위해서는 cleaned 배열과 area 배열의 값을 확인하면 됩니다.
이후 c와 d를 구분하기 위해 뒤쪽 방향이 벽이 아니라 후진이 가능한 경우(후진 후 2번으로 되돌아가기)와
가능하지 않은 경우(작동을 멈추고 출력)를 확인해주었습니다.
뒤쪽 방향이 벽인지를 확인하기 위해서는 아래의 사진과 같이 현재를 기준으로 area 값을 확인해봅니다.
예를 들어 현재 바라보는 방향이 북쪽인 경우,
현재를 기준으로 후진할 때 (i+1, j)의 좌표 값을 가집니다.
만약 현재 바라보는 방향이 남쪽인 경우에는 이와 반대로 후진했을 때 좌표값으로 (i-1, j)를 가지겠죠!
(2-a와 2-b 구현)
이후 왼쪽 방향부터 탐색을 진행해야 하기 위해 현재를 기준으로 했을 때의 왼쪽 방향을 파악합니다.
왼쪽 방향을 파악하기 위해서는 이전과 마찬가지로 좌표값을 알아야 합니다.
아래의 예시는 바라보는 방향이 북쪽인 경우 현재를 기준으로 왼쪽 방향의 좌표값을 나타냅니다.
현재가 (i, j)의 좌표를 가진다면 현재를 기준으로 왼쪽 방향은 (i, j-1) 값을 가지겠죠!
이후 방향을 회전시켜줘야 하는데, 현재를 기준으로 왼쪽 방향은 아래의 그림과 같습니다.
즉 현재 북쪽을 바라보고 있는 경우에는 서쪽으로 방향을 회전시켜주면 되는 것이겠죠.
이후 구현되어 있는 함수를 반복적으로 호출하면서 문제에서 주어진 작동 순서를 구현할 수 있습니다!
3. 청소하는 칸의 개수 구하기
청소가 되었는지 여부를 확인하는 cleaned 배열을 탐색하여 1인 경우를 count 해주었습니다.
이를 통해 문제의 최종적인 답을 구할 수 있습니다.
1~3번을 바탕으로 아래와 같은 코드를 작성하였습니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef struct map{
int area, cleaned;
}map;
map area[50][50];
int N, M;
typedef struct location{
int x, y, direction;
}location;
location now;
void clean();
int all_side_check();
void clean_explore();
int cleaned_check();
int main() {
scanf("%d%d", &N, &M);
scanf("%d%d%d", &now.x, &now.y, &now.direction);
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
scanf("%d", &area[i][j].area);
clean();
printf("%d\n", cleaned_check());
return 0;
}
// 1번
void clean() {
area[now.x][now.y].cleaned = 1;
clean_explore();
}
// 2 - c, d번 조건 check
int all_side_check() {
if ((area[now.x - 1][now.y].area == 1 || area[now.x - 1][now.y].cleaned == 1) && (area[now.x + 1][now.y].area == 1 || area[now.x + 1][now.y].cleaned == 1) && (area[now.x][now.y - 1].area == 1 || area[now.x][now.y - 1].cleaned == 1) && (area[now.x][now.y + 1].area == 1 || area[now.x][now.y + 1].cleaned == 1))
return 1;
else
return 0;
}
// 2번
void clean_explore() {
map left;
switch (now.direction) {
case 0:
if (all_side_check()) {
// 2 - c번
if (area[now.x + 1][now.y].area != 1) {
now.x++;
return clean_explore();
}
// 2 - d번
else
return;
}
left = area[now.x][now.y - 1];
now.direction = 3;
// 2 - a번
if (left.area != 1 && left.cleaned != 1) {
now.y--;
return clean();
}
// 2 - b번
else
return clean_explore();
break;
case 1:
if (all_side_check()) {
if (area[now.x][now.y - 1].area != 1) {
now.y--;
return clean_explore();
}
else
return;
}
left = area[now.x - 1][now.y];
now.direction = 0;
if (left.area != 1 && left.cleaned != 1) {
now.x--;
return clean();
}
else
return clean_explore();
break;
case 2:
if (all_side_check()) {
if (area[now.x - 1][now.y].area != 1) {
now.x--;
return clean_explore();
}
else
return;
}
left = area[now.x][now.y + 1];
now.direction = 1;
if (left.area != 1 && left.cleaned != 1) {
now.y++;
return clean();
}
else
return clean_explore();
break;
case 3:
if (all_side_check()) {
if (area[now.x][now.y + 1].area != 1) {
now.y++;
return clean_explore();
}
else
return;
}
left = area[now.x + 1][now.y];
now.direction = 2;
if (left.area != 1 && left.cleaned != 1) {
now.x++;
return clean();
}
else
return clean_explore();
break;
}
}
// 청소하는 칸의 개수 구하기
int cleaned_check() {
int cnt = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (area[i][j].cleaned == 1)
cnt++;
return cnt;
}저는 map이라는 구조체를 활용하여 입력으로 들어온 현재 장소의 상태(area)와 청소 여부(cleaned)를 한 번에 저장하였고,
(cleaned 배열이 1이면 청소가 된 것을 의미)
현재 로봇 청소기가 있는 칸의 좌표(r, c)와 바라보는 방향(d)을 나타내기 위해 location이라는 구조체를 선언하였습니다.
이 외에 앞서 설명한 부분은 각각의 함수로 구분하여 구현하였습니다.
clean 함수 -> 1. 현재 위치를 청소하기
clean_explore 함수 -> 2. 현재를 기준으로 탐색하기
cleaned_check 함수 -> 3. 청소하는 칸의 개수 구하기
특히 2번의 경우에는 현재 바라보는 방향을 기준으로 좌표값의 계산이 달라지기 때문에
now.direction을 기준으로 switch문을 사용하여 구분하였습니다.
시뮬레이션 문제는 구현 자체는 간단해서 재밌게 풀 수 있었던 것 같습니다!
다만 문제 읽기가 귀찮을 뿐....