C - 백준 14503 로봇 청소기 (feat. 시뮬레이션, 재귀)

참조 포스트

2025.01.09 - [Computer Science/자료구조 & 알고리즘] - [알고리즘] 시뮬레이션 문제는 왜 어려울까? (feat. 설계의 중요성)

[알고리즘] 시뮬레이션 문제는 왜 어려울까? (feat. 설계의 중요성)

 

 

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

 

BOJ_14503_로봇 청소기

 

백준의 14503번 문제는 로봇 청소기의 동작을 구현하는 시뮬레이션 문제입니다. 로봇은 지정된 방 안에서 주어진 동작 규칙에 따라 움직이며, 청소 가능한 모든 칸을 청소합니다.

이 문제는 재귀와 조건문을 활용한 시뮬레이션 문제로, 4방향 탐색과 후진 로직 구현이 핵심입니다.

시뮬레이션 문제인 만큼, 주어진 조건을 더 자세히 볼 필요가 있습니다.

 

---

Checkpoint

 

1. 요구사항 (프로세스) 정의

1. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소합니다.
2. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우:
   • 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 후진합니다.
   • 후진할 수 없으면 작동을 멈춥니다.
3. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우:
   • 반시계 방향으로 90도 회전합니다.
   • 바라보는 방향을 기준으로 앞쪽 칸이 청소되지 않은 빈 칸이라면 전진합니다.

 

2. 프로세스 별 알고리즘 분류 및 설계

 

"청소 안한 곳(0)을 반시계 방향으로 회전하면서 찾기 찾았을 경우 이를 반복" 이기 때문에 조건 2는 재귀로 설계해야한다는 것을 인지 해야합니다.

 

반복을 재귀로 구현하기로 결정했다면 기저 조건(base case)가 필요한데 이는 조건 3이 되겠습니다.

 

조건 1일 경우 자기 자신의 청소여부만 확인하면 되기 때문에 재귀 함수의 시작부분에서 청소가 안되어 있으면(0) 청소를 한 것으로 처리(1) 하고 count를 1증가 시키면 됩니다.

 

---

구현 코드

 

#include <stdio.h>

// 방향 설정: 북(0), 서(1), 남(2), 동(3)
int direction_x[4] = {0, -1, 0, 1}; // x 좌표 이동
int direction_y[4] = {-1, 0, 1, 0}; // y 좌표 이동
int room[50][50];                   // 방의 상태를 저장하는 배열
int N, M;                           // 방 크기
int count = 0;                      // 청소한 칸의 개수

void backtracking_cleaning(int x, int y, int d) {
    // 1. 현재 칸 청소
    if (room[y][x] == 0) {
        room[y][x] = -1; // 청소 완료 표시
        count++;
    }

    // 3. 주변 4칸 중 청소되지 않은 빈 칸 탐색
    for (int i = 0; i < 4; i++) {
        int nd = (d + i) % 4; // 반시계 방향으로 90도 회전
        int nx = x + direction_x[nd];
        int ny = y + direction_y[nd];

        // 청소되지 않은 빈 칸 발견 시 이동
        if (0 <= nx && nx < M && 0 <= ny && ny < N && room[ny][nx] == 0) {
            backtracking_cleaning(nx, ny, nd);
            return;
        }
    }

    // 2. 청소되지 않은 빈 칸이 없는 경우 후진
    int nd = (d + 2) % 4; // 뒤쪽 방향
    int nx = x + direction_x[nd];
    int ny = y + direction_y[nd];

    // 후진 가능하면 후진, 불가능하면 종료
    if (0 <= nx && nx < M && 0 <= ny && ny < N && room[ny][nx] != 1) {
        backtracking_cleaning(nx, ny, d); // 방향 유지 후 후진
    } else {
        return; // 종료
    }
}

int main() {
    int r, c, d;
    scanf("%d %d", &N, &M);         // 방의 크기 입력
    scanf("%d %d %d", &r, &c, &d); // 초기 위치와 방향 입력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &room[i][j]); // 방의 상태 입력
        }
    }
    backtracking_cleaning(c, r, d); // 로봇 청소기 시작
    printf("%d\n", count);          // 청소한 칸 개수 출력
    return 0;
}

 

 

1. 방향 설정

int direction_x[4] = {0, -1, 0, 1}; // x 좌표 이동
int direction_y[4] = {-1, 0, 1, 0}; // y 좌표 이동

• 방향 정의: 북(0), 서(1), 남(2), 동(3)의 순서로 정의됩니다.
• 이동 배열:
  • direction_x와 direction_y는 각각 x축과 y축 이동을 정의하며, 이를 통해 로봇 청소기가 각 방향으로 이동할 수 있습니다.

---

2. 입력 처리

scanf("%d %d", &N, &M);         // 방 크기 입력
scanf("%d %d %d", &r, &c, &d); // 초기 위치와 방향 입력
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        scanf("%d", &room[i][j]); // 방의 상태 입력
    }
}

• 방 크기 (N, M): 방의 세로와 가로 크기를 입력받습니다.
• 로봇 초기 상태 (r, c, d):
  • r, c: 로봇 청소기의 초기 좌표 (y, x 순서로 저장).
  • d: 초기 방향.
• 방 상태 (room):
  • 0: 청소되지 않은 빈 칸.
  • 1: 벽.
  • -1: 청소 완료된 칸.

---

3. 백트래킹 함수

void backtracking_cleaning(int x, int y, int d) {

1단계: 현재 칸 청소

if (room[y][x] == 0) {
    room[y][x] = -1; // 청소 완료 표시
    count++;
}

• 로봇이 현재 위치를 청소합니다.
• 청소한 칸은 -1로 표시하고, count를 증가시켜 청소한 칸의 개수를 기록합니다.

2단계: 주변 4칸 탐색 및 이동

for (int i = 0; i < 4; i++) {
    int nd = (d + i) % 4; // 반시계 방향으로 90도 회전
    int nx = x + direction_x[nd];
    int ny = y + direction_y[nd];
    if (0 <= nx && nx < M && 0 <= ny && ny < N && room[ny][nx] == 0) {
        backtracking_cleaning(nx, ny, nd);
        return;
    }
}

• 로봇이 현재 방향에서 반시계 방향으로 90도씩 회전하며 주변 4칸을 확인합니다.
• 청소되지 않은 빈 칸(값이 0)이 있다면, 해당 방향으로 이동하고 재귀 호출합니다.

3단계: 후진

int nd = (d + 2) % 4; // 뒤쪽 방향
int nx = x + direction_x[nd];
int ny = y + direction_y[nd];
if (0 <= nx && nx < M && 0 <= ny && ny < N && room[ny][nx] != 1) {
    backtracking_cleaning(nx, ny, d); // 방향 유지 후 후진
} else {
    return; // 종료
}

• 주변에 더 이상 청소할 칸이 없으면, 후진합니다.
• 후진도 불가능하면 함수는 종료됩니다.

---

4. 메인 함수

backtracking_cleaning(c, r, d); // 로봇 청소기 시작
printf("%d\n", count);          // 청소한 칸 개수 출력

• 초기 위치에서 청소를 시작합니다.
• 탐색이 종료된 후, 청소한 칸의 총 개수를 출력합니다.

---

5. 주요 로직 요약

1. 로봇은 현재 칸을 청소합니다.
2. 현재 위치에서 반시계 방향으로 90도씩 회전하며 청소되지 않은 칸을 탐색합니다.
3. 탐색한 칸이 있다면 이동하고, 없다면 후진합니다.
4. 후진이 불가능하면 종료됩니다.

---

코드 실행 예시

입력:

3 3
1 1 0
1 1 1
1 0 1
1 1 1

출력:

1

• 로봇은 (1, 1)에서 시작하여 청소할 수 있는 칸이 없습니다. 초기 위치만 청소합니다.

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.