[백준 14503] 로봇 청소기

백준 14503

🔍 알고리즘 분류

• 구현
• 시뮬레이션

💡 문제 풀이

• 먼저, 현재 위치 청소: graph[x][y] = 2
• 현재 위치 기준 4가지 방향을 확인하여 아래와 같이 두 가지 경우로 나누어 진행

1. 청소 가능한 경우
   1) 반시계 방향 90도 회전: (dir + 3) % 4
   2) 회전한 방향으로 전진 가능하면 전진하여 재귀적으로 반복
   3) 현재 함수는 꼭 return; 해주기❗️

   return이 없으면 모든 조건을 검사하고 네 방향 모두 탐색하려고 시도

2. 청소 불가능한 경우
   1) 반대 방향 회전: (dir + 2) % 4
   2) 벽이 아니라면 후진하여 재귀적으로 반복

📄 코드

• C++

#include <iostream>
using namespace std;

int N, M, r, c, d;
int graph[50][50];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int ans = 0;

void cleaning(int x, int y, int dir) {
    if (graph[x][y] == 0) {
        // 청소 완료
        graph[x][y] = 2;
        ans++;
    }
    
    // 청소 가능 여부
    bool canClean = false;

    for (int i = 0; i < 4; i++) {
        // 반시계 방향으로 90도 회전
        int nx = x + dx[(dir + 3 - i) % 4];
        int ny = y + dy[(dir + 3 - i) % 4];
        if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
            // 주변 청소 가능
            if (graph[nx][ny] == 0) {
                canClean = true;
                // 전진하여 청소
                cleaning(nx, ny, (dir + 3 - i) % 4);
                // 청소 끝나면 함수 탈출
                return;
            }
        }
    }
    // 주변 청소 불가능
    if (!canClean) {
        // 후진 방향
        int backDir = (dir + 2) % 4;
        int bx = x + dx[backDir];
        int by = y + dy[backDir];
        if (bx >= 0 && bx < N && by >= 0 && by < M && graph[bx][by] != 1){
            // 후진
            cleaning(x + dx[backDir], y + dy[backDir], dir);
        }
    }
}

int main() {
    cin >> N >> M;
    cin >> r >> c >> d;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> graph[i][j];
        }
    }

    cleaning(r, c, d);

    cout << ans;

    return 0;
}

• Python

n, m = map(int, input().split())
r, c, d = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
ans = 0
# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def canGo(x, y):
    if 0 <= x < n and 0 <= y < m and not arr[x][y] and not visited[x][y]:
        return True
    return False

def dfs(x, y, d):
    global ans
    if not visited[x][y]:
        visited[x][y] = True
        ans += 1

    for _ in range(4):
        d = (d + 3) % 4
        nx = x + dx[d]
        ny = y + dy[d]

        # 청소 가능
        if canGo(nx, ny):
            dfs(nx, ny, d)
            return

    # 청소 불가 = 후진
    nx = x - dx[d]
    ny = y - dy[d]
    if 0 <= nx < n and 0 <= ny < m and not arr[nx][ny]:
        dfs(nx, ny, d)

dfs(r, c, d)
print(ans)