로봇청소기

문제

해결방법

BFS를 사용하여 청소할 수 있는 공간을 큐에 넣고 하나씩 탐색하면서 청소하는 칸의 개수를 세고, 종료조건 (청소가 모두 되어있거나, 뒤쪽방향이 벽이라서 후진도 할 수 없는 경우) 탐색한 청소하는 칸의 개수를 반환한다.

current_r, current_c, current_d = 7, 4, 0
current_room_map = [
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

# 2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.

# 뷱동남서
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def turn_left(d):
    return (d + 3) % 4

def turn_back(d):
    return (d + 2) % 4

# a. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
def get_count_of_departments_cleaned_by_robot_vacuum(r, c, d, room_map):
    n = len(room_map)
    m = len(room_map[0])
    # 청소한 공간 수
    get_count_of_departments_clean = 1
    # 청소한 후 2로 업데이트
    room_map[r][c] = 2
    queue = list([[r,c,d]])
    while queue:
        r,c,d = queue.pop(0)
        temp_d = d

        # 네 방향 돌면서 청소
        for i in range(4):
            temp_d = turn_left(temp_d)
            # 현재 있는 위치에서 이동하는 방향으로 값을 더해줘서 이동
            new_r, new_c = r + dr[temp_d], c + dc[temp_d]

            # 왼쪽 방향에 아직 청소하지 않은 공간이 있다면, 왼쪽으로 회전하고, 한 칸 전진
            if 0 <= new_r < n and 0 <= new_c < m and room_map[new_r][new_c] == 0:
                get_count_of_departments_clean += 1
                room_map[new_r][new_c] = 2
                # 큐에 붙여주기
                queue.append([new_r,new_c,temp_d])
                break
            # 이미 청소가 되어있거나 벽인경우 후진하고, 위 단계로 돌아감
            elif i == 3:
                new_r, new_c = r + dr[turn_back(d)], c + dc[turn_back(d)]
                queue.append([new_r,new_c,d])
            # 뒤가 벽인 경우
                if room_map[new_r][new_c] == 1:
                    return get_count_of_departments_clean

# 57 가 출력되어야 합니다!
print(get_count_of_departments_cleaned_by_robot_vacuum(current_r, current_c, current_d, current_room_map))