BOJ(백준) 14503[로봇 청소기]

안녕하세요, 이번 글에서는 백준 14503번 문제인 “로봇 청소기” 문제를 함께 해결해 보겠습니다. 이 문제는 주어진 영역을 로봇 청소기가 주어진 규칙에 따라 청소하는 문제입니다. 함께 문제를 분석하고, 접근 방법을 정리한 후, 최종적인 정답 코드를 확인해 보겠습니다.

 

문제 URL: https://www.acmicpc.net/problem/14503

1. 문제 설명

1) 문제 개요

• 로봇 청소기가 주어진 영역을 청소하는 문제입니다.

• 로봇은 현재 위치에서 북, 서, 남, 동 방향으로 이동하며, 주어진 규칙에 따라 청소를 수행합니다.

 

2) 입력

• 첫 번째 줄에 그리드의 크기 N과 M이 주어집니다. (1 ≤ N, M ≤ 50)

• 두 번째 줄에 로봇 청소기의 초기 위치 (si, sj)와 초기 방향 (sd)이 주어집니다. (0 ≤ si, sj < N, M) (0 ≤ sd < 4)

• 다음 N개의 줄에 그리드 정보가 주어집니다. (0: 빈칸, 1: 벽)

 

3) 출력

• 청소한 구역의 수를 출력합니다.

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 그리드의 크기 N과 M을 입력받습니다.

• 두 번째 줄에서 로봇 청소기의 초기 위치와 방향을 입력받습니다.

• 다음 N개의 줄에서 그리드 정보를 입력받습니다.

 

2) 방향 벡터 정의

• 북, 서, 남, 동의 순서로 이동을 정의합니다.

• 방향 매핑: 0 -> 북, 1 -> 동, 2 -> 남, 3 -> 서

 

3) 로봇 청소기 동작 구현

• 초기 방향이 동/서인 경우 북/남으로 조정합니다.

• 현재 위치를 청소하고, 왼쪽 방향으로 회전하며 청소하지 않은 공간을 찾습니다.

• 네 방향 모두 청소가 되어 있거나 벽인 경우 후진합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

# 방향 벡터: 북, 서, 남, 동
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

"""
방향 매핑:
0 -> 0 (북)
1 -> 3 (서)
2 -> 2 (남)
3 -> 1 (동)
"""

# 그리드 크기 입력
N, M = map(int, input().split())

# 시작 위치와 방향 입력
si, sj, sd = map(int, input().split())

# 그리드 맵 입력
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

ans = 0  # 청소한 구역의 수

# 초기 방향 조정
if sd % 2 != 0:
    if sd == 1:
        sd = 3  # 동 -> 서
    else:
        sd = 1  # 서 -> 동

chk = True
while chk:
    # 현재 위치가 청소되지 않은 경우 청소
    if arr[si][sj] == 0:
        arr[si][sj] = 2
        ans += 1

    for i in range(1, 5):
        # 왼쪽 방향으로 회전
        nd = (sd + i) % 4
        ni, nj = si + di[nd], sj + dj[nd]
        # 청소하지 않은 공간이 있는 경우 이동
        if arr[ni][nj] == 0:
            si, sj, sd = ni, nj, nd
            break
    else:
        # 네 방향 모두 청소가 되어 있거나 벽인 경우 후진
        ni, nj = si - di[sd], sj - dj[sd]
        if arr[ni][nj] == 1:
            chk = False  # 후진할 수 없으면 종료
        else:
            si, sj = ni, nj  # 후진

# 청소한 구역의 수 출력
print(ans)

 

4. 코드 설명

1) 입력 받기

• 첫 번째 줄에서 그리드의 크기 N과 M을 입력받습니다.

• 두 번째 줄에서 로봇 청소기의 초기 위치 (si, sj)와 초기 방향 (sd)을 입력받습니다.

• 다음 N개의 줄에서 그리드 정보를 입력받아 arr 배열에 저장합니다.

 

2) 초기 방향 조정

• 입력된 방향이 동(1) 또는 서(3)인 경우 북/남으로 조정합니다.

• 동(1)인 경우 서(3)로 변경

• 서(3)인 경우 동(1)로 변경

 

3) 로봇 청소기 동작 구현

• chk 변수를 True로 설정하고, 루프를 시작합니다.

• 현재 위치가 청소되지 않은 경우 청소하고, 청소한 구역의 수를 증가시킵니다.

• 왼쪽 방향으로 회전하면서 청소되지 않은 공간을 찾습니다. 청소되지 않은 공간이 있으면 그 방향으로 이동합니다.

• 네 방향 모두 청소가 되어 있거나 벽인 경우 후진합니다. 후진할 수 없으면 루프를 종료합니다.

 

4) 결과 출력

• 청소한 구역의 수를 출력합니다.

 

5) 예시

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

 

이 예시에서는 N = 3, M = 3, si = 1, sj = 1, sd = 0이며, arr는 다음과 같이 저장됩니다:

arr = [

    [1, 1, 1],

    [1, 0, 1],

    [1, 1, 1]

]

 

• 초기 위치 (1, 1)이 청소되지 않았으므로 청소하고, ans를 1로 증가시킵니다.

• 왼쪽으로 회전하여 서쪽(3) 방향을 검사합니다. (0 -> 3)

• 서쪽에 벽이 있으므로 북쪽(0) 방향을 검사합니다. (3 -> 0)

• 북쪽에 벽이 있으므로 동쪽(1) 방향을 검사합니다. (0 -> 1)

• 동쪽에 벽이 있으므로 남쪽(2) 방향을 검사합니다. (1 -> 2)

• 남쪽에 벽이 있으므로 후진합니다. 후진할 수 없어 루프를 종료합니다.

 

5. Github으로 확인

coTest/BOJ/BOJ01_08_01_14503.py at main · pcy4196/coTest

 

 

**

시간 복잡도

 

이 문제의 시간 복잡도는 그리드의 크기와 로봇 청소기의 이동에 따라 결정됩니다. 최대 N * M의 그리드에서 모든 칸을 탐색하는 경우가 최악의 시나리오입니다.

 

1. 입력 처리

• 입력을 처리하는 데 O(N * M)의 시간이 소요됩니다.

2. 로봇 청소기 동작

• 각 칸을 최대 한 번만 청소하므로, 모든 칸을 방문할 경우 O(N * M)의 시간이 소요됩니다.

 

따라서, 전체 시간 복잡도는 O(N * M)입니다. 이는 주어진 그리드의 크기에 비례하여 선형적으로 증가합니다.

**