[코드트리] 삼성 2025 하반기 오후 기출 1번 AI 로봇청소기

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

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

사실 그렇게 깔끔한 코드는 아니지만,, 기록해둘겸 작성해봅니다..

 

패턴이 주어지고, 이를 방향에 따라 다르게 적용하는 코드는 백준의 마법사 상어와 토네이도 문제에서 영감을 받았습니다.

https://www.acmicpc.net/problem/20057

 

이 문제는 'bfs', 'tie break', 'origin' 이 3가지가 키워드였다고 생각합니다.

 

비교할 때 tie break를 적절히 잘 활용하면 코드 몇 줄 줄일 수 있더라구요,, 근데 뭔가 썩 좋은 코드는 아닌 듯한 느낌입니다.

 

또한 청소할 수 있는 용량이 정해져 있고, 먼지 확산이라는 개념이 있습니다. 이것만 조심하시면 될 듯 합니다.

1. 청소 후에도 원점에 청소할 것이 남아있는 경우

2. 청소기가 있는 칸에도 (먼지가 없다면) 그곳으로 확산합니다 ㄷㄷ

from collections import deque
N,K,L = map(int, input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
loc_robots = [[False] *N for _ in range(N)]
robots=deque()
for _ in range(K):
    x,y = map(int, input().split())
    robots.append([x-1,y-1])
    loc_robots[x-1][y-1] = True


# 로봇의 진행 방향 : 하우좌상
dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]

# 반시계 방향 회전
def rotate_dir(dx,dy,d):
    for _ in range(d):
        dx,dy = -dy, dx
    return dx,dy

# 위쪽 방향 기준, 청소 패턴
patterns = [
    (-1,0),
    (0,-1),
    (0,0),
    (0,1),
]

def bfs(now):
    x,y = now
    dq = deque()
    dq.append([x,y,0])
    visited = [[False]*N for _ in range(N)]
    visited[x][y] =True
    candidate = []
    #print(now)
    while dq:
        x,y,d = dq.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N and not visited[nx][ny] and not loc_robots[nx][ny] and arr[nx][ny] >=0:
                if arr[nx][ny] == 0:
                    dq.append([nx,ny,d+1])
                elif arr[nx][ny] > 0 :
                    candidate.append([nx,ny,d+1])
                visited[nx][ny]=True
    if len(candidate) ==0:
        return [-1,-1]
    candidate.sort(key = lambda x : (x[2],x[0],x[1]))
    #print('1', candidate)
    return [candidate[0][0], candidate[0][1]]

while L:
    tmp = deque()
    answer  = 0
    while robots:
        robot = robots.popleft()

        # 제자리에 청소할 게 남았다면
        if loc_robots[robot[0]][robot[1]] and arr[robot[0]][robot[1]] > 0:
            tmp.append(robot)
        else:
            # 청소기 이동
            new_robot = bfs(robot)

            loc_robots[robot[0]][robot[1]] = False
            if new_robot == [-1, -1]:     # 못 움직이면
                new_robot = robot         # 원래 자리 그대로 유지

            tmp.append(new_robot)
            loc_robots[new_robot[0]][new_robot[1]] = True

    # 전부 이동 완료 후 청소 시작
    robots = deque(tmp)
    #print(robots)
    #print(arr)
    while tmp:
        cur_robot = tmp.popleft()
        sum_ = -1
        # 청소할 방향 정하기 (상,좌,하,우)
        for d in range(4): 
            inter_sum = 0
            for p in patterns:
                px, py = rotate_dir(p[0],p[1],d)
                nx = cur_robot[0] + px
                ny = cur_robot[1] + py
                #nx, ny = rotate_dir(nx,ny,d)

                if 0<=nx<N and 0<=ny<N and arr[nx][ny] > 0:
                    inter_sum += min(20, arr[nx][ny])
            if sum_ <= inter_sum: # 우선순위의 역순으로 방향을 탐색하니까 <= 로 처리
                sum_ = inter_sum
                dir = d
        # 방향대로 청소하기 
        #print(loc_robots)
        for p in patterns:
            px, py = rotate_dir(p[0],p[1],dir)
            nx = cur_robot[0] + px
            ny = cur_robot[1] + py
            #가운데
            if 0<=nx<N and 0<=ny<N and arr[nx][ny] > 0:
                arr[nx][ny] = max(0, arr[nx][ny]-20)

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

    #확산
    spread = [a[:] for a in arr]
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 0:
                dust = 0
                for d in range(4):
                    nx = i + dx[d]
                    ny = j + dy[d]
                    if 0<=nx<N and 0<=ny<N and arr[nx][ny] > 0 :
                        dust += arr[nx][ny]
                spread[i][j] = (dust)//10
            
    #print((arr))
    arr = [s[:] for s in spread]
    for a in arr:
        for num in a:
            if num > 0:
                answer += num
    print(answer)

    # 종료조건
    L-=1
    if L == 0:
        break