반응형

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

 

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어

www.acmicpc.net

문제 설명

문제에서 주어진 것 처럼, 로봇 청소기가 빈공간을 돌아다니며 청소를 한다.

현재 방향을 기준으로 왼쪽 방향부터 탐색을 시작하며,

방향은 0 = 북 / 1 = 동 / 2 = 남 / 3 = 서쪽을 의미한다.

 

문제에서 주어진 조건과 상황들을 잘 고려하여 코드를 작성해보자.


풀이 과정

먼저 로봇 청소기의 초기 위치는 무조건 0이며 해당 칸을 청소하게 된다.

청소를 한 칸은 2로 변경하여 청소를 했음을 표시해주도록 하자.

그리고 이제 다음과 같이 시뮬레이션을 돌려주자.

 

왼쪽 방향칸을 청소 하지 않았다면(0 이라면)

현재 내 방향(d)를 왼쪽으로 전환하고 한 칸 전진한 후 그 칸을 청소한다.

이 때, 방향은 0 = 북 / 1 = 동 / 2 = 남 / 3 = 서 이므로

왼쪽로의 전환은 (d - 1)%4 를 통해 가능하다.

 

② 왼쪽 방향에 청소할 공간이 없다면(0 or 1 이라면)

현재 내 방향(d)를 왼쪽으로 전환하고 전진은 하지 않은 상태로 다시 ①단계로 돌아간다.

 

③ 네 방향 모두 청소가 되어있거나 벽인 경우(0 or 1이라면)

현재 내 방향(d)를 유지한 채로 한 칸 후진하여 ① 단계로 돌아간다.

 

④ 네 방향 모두 청소가 되어있거나 벽인 경우(0 or 1이라면)

뒤 쪽 방향이 벽(1)이라 후진조차 불가능하다면 작동을 멈춘다.

 

위 과정을 모두 거친 후, 로봇청소기가 청소한 칸의 갯수를 출력한다.

n, m = map(int, input().split())
r, c, d = map(int, input().split())
board = []
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
answer = 1

for i in range(n):
    board.append(list(map(int, input().split())))


def dfs(x, y, depth):
    global answer, d
    if depth == 4:
        nx = x + dx[(d - 2) % 4]
        ny = y + dy[(d - 2) % 4]
        if board[nx][ny] == 2:
            dfs(nx, ny, 0)
        else:
            print(answer)
            exit(0)

    nx = x + dx[(d - 1) % 4]
    ny = y + dy[(d - 1) % 4]

    if board[nx][ny] == 0:
        board[nx][ny] = 2
        answer += 1
        d = (d - 1) % 4
        dfs(nx, ny, 0)

    elif board[nx][ny] == 1 or board[nx][ny] == 2:
        d = (d - 1) % 4
        dfs(x, y, depth + 1)


board[r][c] = 2
dfs(r, c, 0)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

반응형

+ Recent posts