14503. 로봇청소기 - 시뮬레이션, 구현

사용한 알고리즘, 자료구조

1. 2차원 배열의 델타 검색

 

접근 방식

문제의 조건을 잘 읽고 정확히 구현한다.

 

1. 입력
   1. 지도의 가로, 세로 길이를 입력받는다.
   2. 로봇의 시작 좌표와 초기 방향을 입력받는다.
2. 선언
   1. 방문 여부 배열을 선언한다
   • 지도 배열에 방문 여부를 기록할 수도 있다.
   1. 델타 탐색을 위한 배열 선언
   2. 로봇의 다음 좌표를 담을 리스트를 선언한다.

어려웠던 점

삼성 스타일 완전탐색 중에서는 비교적 간단한 편이었다.

 

느낀 점

시간을 아낄 수 있는 방법이 많았다. 일반적인 완전탐색(BFS) 처럼 생겼다는 이유로 습관적으로 deque를 import 했으며, visited배열을 선언하기도 했다. 문제를 다시 읽어보니 시공간 복잡도를 줄일 수 있는 방법들이 많았다. 파이썬은 느린 편히니 특히나 시간을 많이 아껴야한다.

 

풀었을 때 당시의 백준 티어

2021.09.26 골드 3

 

import sys
input = sys.stdin.readline

# 1. 입력
N, M = map(int, input().split()) # 지도의 세로 길이, 가로 길이
robot_y, robot_x, robot_drc = map(int, input().split()) # 시작 y, 시작 x, 초기 방향값
room = [list(map(int, input().split())) for _ in range(N)] # 지도 == 벽이 있는지 여부

# 2. 선언
# 2-1. 델타 배열
dx = (0, 1, 0, -1) # 북, 동, 남, 서
dy = (-1, 0, 1, 0) # 북, 동, 남, 서

# 2-2. 결과값 받을 변수 선언
cleaned_spots = 0

# 2-3. 로봇 작동 여부 받을 변수 선언
# while 문의 맨 끝에 'break'쓰는것보다, 이렇게 별도의 변수를 할당한 뒤
# True-False 스위치로 활용하는 것이 가독성이 더 좋다.
is_robot_active = True

#2-4 벽, 청소됨.
wall = 1
cleaned = -1

# 3. 연산
while is_robot_active: # 로봇이 작동하는 동안

    # 3-1. 현재 위치를 청소한다.
    # 문제에서 '1' 단계
    if not room[robot_y][robot_x]: # 청소가 안 되었으면
        room[robot_y][robot_x] = cleaned # 청소하고
        cleaned_spots += 1 # 청소된 구역 += 1

    # 3-2. 현재 위치에서 현재 방향을 기준으로
    # 왼쪽 방향부터 차례대로 인접한 칸을 탐색한다.
    for i in range(4): # 4방향을 차례대로 탐색한다.

        # 문제 2-a~b. 단계
        robot_drc = 3 if robot_drc == 0 else robot_drc - 1 # 왼쪽 보는 연산
        next_y = robot_y + dy[robot_drc] # '다음에 볼 장소'의 y좌표
        next_x = robot_x + dx[robot_drc] # '다음에 볼 장소'의 x좌표

        # 문제 1.로 복귀
        if not room[next_y][next_x]:# 청소도 안 되었고 벽도 벽도 아니면 == 0 이면
            robot_y = next_y # 로봇 y 좌표 갱신
            robot_x = next_x # 로봇 x 좌표 갱신
            break # 청소할 곳 탐색 작업 종료

    # 문제 2-c. 단계
    else: # for문이 break 되지 않고 4회 순회했을 시
        back = (robot_drc + 2) % 4 # '뒤'를 보는 연산
        robot_y = robot_y + dy[back]
        robot_x = robot_x + dx[back]

        # 문제 2-d. 단계
        if room[robot_y][robot_x] == wall: # 뒤가 벽이면
            is_robot_active = False # 로봇청소기 작동 종료

# 4. 출력
print(cleaned_spots)