파이썬 백준 알고리즘 해설: 청소 로봇 14503

안녕하세요! 개발자 여러분들을 위해 알고리즘 풀이 포스트를 작성하려고 합니다. 오늘은 백준 온라인 저지의 "청소 로봇" 문제를 다뤄보려고 합니다. 해당 문제는 주어진 맵에서 로봇이 청소하는 과정을 시뮬레이션하는 문제입니다.

 

바로 아래 정보에서 공부해봅시다!

백준 알고리즘 로고

문제 내용

로봇은 2차원 맵에서 청소 작업을 수행하며, 각 칸은 빈 공간(0) 또는 벽(1)으로 구성됩니다. 로봇은 동, 서, 남, 북 네 가지 방향 중 한 가지 방향을 바라볼 수 있으며, 현재 위치의 상태는 청소 완료(2)인지, 청소하지 않은 상태인지(0) 나타냅니다. 로봇은 다음과 같은 규칙에 따라 작동합니다.

1. 현재 위치를 청소합니다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색합니다.
3. 청소하지 않은 공간이 존재하면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행합니다.
4. 네 방향 모두 청소가 이미 되어있거나 벽인 경우, 바라보는 방향을 유지한 채로 한 칸 후진하고 2번으로 돌아갑니다.
5. 만약 후진할 수 없는 경우 작동을 멈춥니다.

로봇이 청소하는 칸의 개수를 출력하는 문제입니다. 이제부터 문제를 해결하는 방법을 알아보겠습니다.

 

문제 이해하기

주어진 코드를 통해 문제의 요구사항을 파악해보겠습니다. 주어진 코드를 살펴보면, 맵의 크기와 로봇의 초기 위치, 방향, 맵의 상태를 입력받습니다. 그리고 로봇이 청소하는 칸의 개수를 구하는 로직이 구현되어 있습니다.

 

풀이 코드

pythonCopy code
import sys

input = sys.stdin.readline

EMPTY, WALL, CLEAN = 0, 1, 2

# 북(상) 동(좌) 남(하) 서(우) - 반시계 방향
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

n, m = map(int, input().split())
x, y, d = map(int, input().split())

matrix = [list(map(int, input().split()))for _ in range(n)]

answer = 1
matrix[x][y] = CLEAN

while True:
    check = False

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

        if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == EMPTY:
            matrix[nx][ny] = CLEAN
            answer += 1
            check = True
            x, y = nx, ny
            break

    if not check:
        nx = x - dx[d]
        ny = y - dy[d]

        if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == WALL:
            break
        x, y = nx, ny

print(answer)

풀이 방법

주어진 코드를 통해 문제를 해결하는 방법을 살펴보겠습니다. 이 코드는 주어진 맵에서 로봇이 청소하는 과정을 시뮬레이션하는 로직으로 구성되어 있습니다.

먼저, 맵의 크기와 로봇의 초기 위치, 방향을 입력받습니다. 그리고 맵의 상태를 2차원 리스트 **matrix**에 저장합니다. 초기 위치를 청소한 상태로 표시하고, 청소한 칸의 개수를 answer 변수에 1로 초기화합니다.

주어진 로봇의 작동 규칙에 따라 while 루프를 돌며 작동을 수행합니다. 우선 청소할 칸이 존재하는지 확인하기 위해 4방향을 탐색합니다. 현재 방향을 기준으로 왼쪽 방향부터 차례대로 탐색하며, 청소하지 않은 공간을 찾으면 그 방향으로 로봇을 이동시키고 청소한 칸의 개수를 증가시킵니다. 이후 청소한 칸의 위치를 기록하고, 루프를 계속 진행합니다.

만약 네 방향 모두 청소가 이미 되어있거나 벽인 경우, 후진할 위치를 계산합니다. 후진할 위치가 맵 범위 내에 있고 벽이 아닌 경우, 로봇을 후진시키고 이전 방향을 유지한 채로 루프를 계속 진행합니다. 후진할 위치가 맵 범위를 벗어나거나 벽인 경우, 로봇의 작동을 멈추고 작업이 종료됩니다.

풀이 코드의 로직을 통해 로봇이 청소하는 칸의 개수를 구할 수 있습니다.

 

시간 복잡도

해당 알고리즘의 시간 복잡도는 주어진 맵의 크기에 비례합니다. 맵의 크기가 N×M일 때, 모든 칸을 한 번씩 방문해야 하므로 최악의 경우 O(N×M)의 시간 복잡도를 가지게 됩니다.

이상으로 "청소 로봇" 문제의 풀이를 마치겠습니다. 다음 포스트에서 또 다른 알고리즘 문제를 다룰 예정입니다. 감사합니다!

백준이 너무 어렵다면 아주 기본 코딩테스트 알고리즘을 먼저 도전해보세요~

 

👉 기본 코딩테스트 문제보기

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음