백준 14503번. 로봇 청소기 (Java, Python)

Problem

• 문제 링크

특정 조건에 따라 움직이는 로봇이 청소한 칸의 총 갯수를 구하는 문제입니다.

Solution

로봇이 청소한 구역을 구하는 문제입니다.

특별한 알고리즘 없이 문제에서 주어진 조건대로 구현하는 시뮬레이션 문제입니다.

북, 동, 남, 서 방향에 대한 계산만 헷갈리지 않고 해주면 쉽게 구현할 수 있습니다.

현재 로봇의 위치와 방향에 대한 정보를 잘 관리해야 합니다.

로봇에 대한 클래스를 만들어도 되지만 그냥 전역 변수로 처리하였습니다.

한가지 특이한 점은 맵의 테두리는 항상 벽으로 되어 있어 map 배열이 범위를 벗어나는 경우는 처리하지 않아도 됩니다.

Java Code

import java.util.*;
import java.io.*;

class Main {
    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int n, m;
    static int[][] map;
    static int r, c, d;
    static int[] dx = {-1, 0, 1, 0};    // 북동남서
    static int[] dy = {0, 1, 0, -1};
    static int turnCount = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        map = new int[n][m];

        st = new StringTokenizer(br.readLine());
        r = stoi(st.nextToken());
        c = stoi(st.nextToken());
        d = stoi(st.nextToken());

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = stoi(st.nextToken());
            }
        }

        solution();
    }

    static void solution() {
        /**
         * 0 : 청소하지않은 공간
         * 1 : 벽
         * 2 : 청소한 공간
         */

        while (true) {
            if (turnCount == 4) {
                // 네 방향 모두 청소가 되어있거나 이미 벽이면 후진 후 2번으로
                int backX = r - dx[d];
                int backY = c - dy[d];

                if (map[backX][backY] == 1) {
                    // 벽이면 종료
                    System.out.println(getCleanArea());
                    return;
                } else {
                    // 벽 아니면 후진
                    setRobot(backX, backY, d, 0);
                }
            }

            // 1. 현재 위치 청소
            if (map[r][c] == 0)
                map[r][c] = 2;

            // 2. 현재 방향을 기준으로 왼쪽방향 확인
            int ld = (d + 3) % 4;
            int nx = r + dx[ld];
            int ny = c + dy[ld];

            // 3. 청소공간 있음 -> 한칸 전진 하고 1번으로
            // 4. 청소공간 없음 -> 그 방향으로 회전하고 2번으로
            if (map[nx][ny] == 0) {
                setRobot(nx, ny, ld, 0);
            } else {
                setRobot(r, c, ld, turnCount + 1);
            }
        }
    }

    // r, c, d, count 설정
    static void setRobot(int nextX, int nextY, int nextD, int nextCount) {
        r = nextX;
        c = nextY;
        d = nextD;
        turnCount = nextCount;
    }

    static int getCleanArea() {
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 2)
                    result++;
            }
        }
        return result;
    }
}

Python code

# -*- coding: utf-8 -*-
 
import sys
 
N = M = 0
arr = []
## 북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
 
def countClean():
    count = 0
    for i in range(N):
        for j in range(M):
            if arr[i][j] > 1:
                count += 1
    return count
 
def leftTurn(d):
    if d == 0:
        return 3
    else:
        return d-1
 
def clean(x, y, d, turnCount):
    while True:
        ## 4방향 모두 탐색했으면 
        if turnCount == 4:
            backX = x - dx[d]
            backY = y - dy[d]
 
            if arr[backX][backY] == 1:
                print(countClean())
                return
            else:
                x, y, d, turnCount = backX, backY, d, 0
 
        ## 1. 현재 위치를 청소한다.
        if arr[x][y] == 0:
            arr[x][y] = 2
 
        ## 2. 왼쪽 방향부터 탐색
        ld = leftTurn(d)
        nx = x + dx[ld]
        ny = y + dy[ld]
 
        ## 왼쪽 방향에 청소 안함 (1) 1번부터 다시 시작
        if arr[nx][ny] == 0:
            x, y, d, turnCount = nx, ny, ld, 0
        else:
            ## 왼쪽 방향에 청소함 (2) 2번부터 시작
            ## 벽이면 왼쪽 탐색
            x, y, d, turnCount = x, y, ld, turnCount + 1
 
if __name__ == '__main__':
    N, M = map(int, sys.stdin.readline().split())
    r, c, d = map(int, sys.stdin.readline().split())
    visited = [[False]*M for i in range(N)]
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    clean(r, c, d, 0)