[코드트리/파이썬] AI 로봇청소기 - 2

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/ai-robot/description

코딩테스트 기출 문제 설명: AI 로봇청소기 | 코드트리

 

from collections import deque

ROBOT_DIRECTION = [[-1, 0], [0, -1], [0, 1], [1, 0]]    # 상좌우하


def robots_move(robots : deque[list[int]], idx: int) :
    """
    robots : 로봇 청소기들 좌표
    idx : 현재 로봇 청소기 번호
    
    1. 청소기 이동
    이동 거리가 가장 가까운 오염된 격자로 이동. => 가장 가까운 이동거리를 구해야함. BFS
    물건이나 청소기가 있는 격자로는 이동불가.
    상하좌우로 인접한 격자를 한 칸씩 이동하여 도달하는 데 필요한 최소 이동 횟수를 의미
    우선순위 : 가장 가까운 먼지 > 행번호 > 열번호
    """
    robot_q = deque()
    visited = [[0] * N for _ in range(N)]

    # 각 로봇의 좌표를 담아서 이동. 만약 움직였는데 자기의 범위에 먼지가 없으면 -1, -1 로 보낼까? 
    movement = N*N+1
    res_robot = []

    for robot in robots :
        visited[robot[0]][robot[1]] = 1

    robot_q.append([0] + robots[idx]) # 이렇게 되면 [이동횟수, 행, 열] 이 되니까.

    while robot_q :
        move_cnt, rr, rc = robot_q.popleft()

        # 정답처리 : 먼지를 발견했다. 더 짧은 이동거리로.
        if maps[rr][rc] > 0 and movement >= move_cnt:
            movement = move_cnt
            res_robot.append([rr, rc])

        for dr, dc in ROBOT_DIRECTION :
            nr, nc = rr + dr, rc + dc
            
            # 네방향, 범위내, 미방문, 조건(박스가 있거나, 먼지 발견)
            if 0 <= nr < N and 0 <= nc < N and visited[nr][nc] != 1:
                # if maps[nr][nc] == -1 :
                #     continue
                
                if maps[nr][nc] >= 0 :
                    robot_q.append([move_cnt + 1, nr, nc])
                    visited[nr][nc] = 1
    if len(res_robot) == 0 :
        return robots[idx]
    else :
        res_robot.sort()
        return res_robot[0]


if __name__ == "__main__" :
    N, K, L = map(int, input().split()) # 격자 크기, 청소기 개수, 테스트 횟수
    maps = [list(map(int, input().split())) for _ in range(N)]
    
    robots = deque()
    
    for _ in range(K) :
        a, b = map(int, input().split())    # 격자 구조가 1, 1 ~ N, N 이라 -1 씩 해줌
        robots.append([a-1, b-1])
    
    # 테스트 결과만큼 돌리라 했으니까.
    for _ in range(L) :
        # 1. 로봇 청소기 이동
        for k in range(K) :
            moved_robots = robots_move(robots, k)
            robots[k] = moved_robots

		# 2. 청소
        for k in range(K) :
            clean_direction = [
                [[0, 0], [-1, 0], [0, 1], [1, 0]],  # 오른쪽
                [[0, 0], [0, 1], [1, 0], [0, -1]],  # 아래쪽
                [[0, 0], [1, 0], [0, -1], [-1, 0]], # 왼쪽
                [[0, 0], [0, -1], [-1, 0], [0, 1]]  # 위쪽
            ]

            dust_amount = []
            for idx_direction in range(len(clean_direction)) :
                dust_cnt = 0
                for cr, cc in clean_direction[idx_direction] :
                    nr, nc = robots[k][0] + cr, robots[k][1] + cc

                    if 0 <= nr < N and 0 <= nc < N and maps[nr][nc] != -1 :
                        dust_cnt += min(20, maps[nr][nc])

                dust_amount.append([dust_cnt, idx_direction])
            dust_amount.sort(key=lambda x: (-x[0], x[1]))
        
            # 격자마다 청소 할 수 있는 최대 먼지량은 20 이라는 말은 각 격자마다 이겠지?
            # dust_amount[robot_idx][0] 을 가져오면 [먼지량, idx_direction]
            # 그럼 또 nr, nc 부여해서 max(0, maps[nr][nc] - 20) 하면 되겠네.
            dust_direction = dust_amount[0][1]
            for cr, cc in clean_direction[dust_direction] :
                nr, nc = robots[k][0] + cr, robots[k][1] + cc
                if 0 <= nr < N and 0 <= nc < N and maps[nr][nc] != -1 :
                    maps[nr][nc] = max(0, maps[nr][nc] - 20)

        # 3. 먼지 축적
        for i in range(N) :
            for j in range(N) :
                if maps[i][j] > 0 :
                    maps[i][j] += 5

        temp = [[0] * N for _ in range(N)]
        # 4. 먼지 확산
        for i in range(N) :
            for j in range(N) :
                if maps[i][j] == 0 :
                    dust_0 = 0
                    for di, dj in ROBOT_DIRECTION :
                        ni, nj = i + di, j + dj
                        if 0 <= ni < N and 0 <= nj < N and maps[ni][nj] > 0 :
                            dust_0 += maps[ni][nj]

                    temp[i][j] = (dust_0 // 10)

        for i in range(N) :
            for j in range(N) :
                if temp[i][j] > 0 :
                    maps[i][j] += temp[i][j]

        # 5. 출력
        cnt = 0
        for i in range(N) :
            for j in range(N) :
                if maps[i][j] > 0 :
                    cnt += maps[i][j]

        print(cnt)
        if cnt == 0 :
            break

드디어 혼자 힘으로 풀었다... 오예

확실히 BFS, DFS 의 개념을 꽉 잡아 놓으니까 이런문제 만나면 자신감이 조금 더 붙는 거 같다. 

일요일 스터디에서 가볍게 문제의 키포인트들을 확인하는 시간을 가졌지만, 월요일부터 투자했던 시간이 화요일인 지금 그렇게 아깝지 않게 되었다. 

키 포인트들을 하나씩 잡고 가자. 

1. robots_move :
   1. 이동횟수, 행 번호, 열 번호를 체크하는 큐가 필요하다. 
   2. 우선순위대로 나열할 수 있어야 한다. 이 방법을 # 정답처리 부분에 해당한다. 
   3. 마지막 행, 열 우열순위는 sort()를 통하여 행이 작으면, 그 다음 열이 작으면이 자동으로 나열된다.
   4. return 부분도 만약 먼지를 발견하지 못하면 제자리, 아니면 sort 후 가장 앞에 있는 좌표 반환 
   5. res_robot안에 여러 개가 저장되었다는건 같은 반경 안에 여러 개의 먼지가 존재한다는 것이다.
2. 청소 
   1. 위치 순서를 잘 기억하자. 오른쪽, 아래쪽, 왼쪽, 위쪽이다. 이러면 idx=[0,1,2,3] 이 된다.
   2. 해당 로봇의 좌표는 로봇 번호 k로 받아와서 robots[k][n] 으로 처리하면 된다.
   3. 방향 정렬 순서는 청소 가능한 먼지량이 제일 많은거, idx 순이다. sort(-(청소량), idx)
   4. 가장 적합한 방향은 [0][1]에 저장되어 있으니까 이렇게 꺼내면 될 것이다.
   5. 그다음 각 격자마자 최소 0이 되도록 코드 작성
3. 먼지 축적
   1. 이건 그냥 이중 for문 돌리면 된다.
4. 먼지 확산
   1. 처음에는 deepcopy를 활용했었는데 새로운 2차원 배열을 하나 생성하고 확산될 수 있는 공간에 + dust//10 을 하자
   2. 그리고 maps에다가 추가하면 끝.
5. 출력
   1. 덧셈이야 이중 for문 돌리면 되고, 마지막 전체 먼지량이 0이 되었을 때 끝내는 방법을 생각하지 않았는데, 이 역시 참고해서 풀었다. 생각보다 많이 틀리는데? 허허...

코데풀, 우리 스터디장님 코드 참고

1. 2. 청소 단계에서 dust_cnt += min(20, maps[i][j]) 단계를 처음에는 maps[i][j]로 했었다. 
2. robots_move 함수 부분은 문제가 하도 안풀려서 참고 했는데, 이렇게도 되지 않을까? 생각해서 몇가지를 바꿨다. 
   1. movement > move_cnt => movement >= move_cnt 로 등호를 추가해주었다. 
   2. 마지막 return 부분은 저런식으로 표현해야하는구나 라는걸 느낄 수 있었다. 
   3. movement 코드를 왜 저렇게 짰냐고 물어보신다면, 사실 가장 짧게 이동한 좌표만 들어오고 나머지는 다 탈락될거라는 계산하에 작성을 하였다. 
3. 코데풀님 코드에서 조금 변경했으면 좋겠는점.
   1. direction 설정을 for문 안에서 할 것이 아니라 전역 변수로 선언하면 초기화, 갱신을 덜 하게 될테니 조금 더 효율적이지 않을까?
   2. 내 코드 중에서도 clean_direction 도 마찬가지지만 나중에 따로 만들어서 동작시켜보고 시간, 공간 소모를 한 번 같이 체크해볼 수 있는 시간을 가졌으면 좋겠다. 
4. 아 나 ROBOT_DIRECTION을 그냥 DIRECTION으로 바꿔야겠다. 먼지 확산에도 같이 썼구나...

 

https://github.com/jeongminllee/CodeTreeTest/blob/main/samsung-sw/AI%20%EB%A1%9C%EB%B4%87%EC%B2%AD%EC%86%8C%EA%B8%B0/ai-robot.py

CodeTreeTest/samsung-sw/AI 로봇청소기/ai-robot.py at main · jeongminllee/CodeTreeTest