2025 프로그래머스 코드챌린지 1차 예선 > 지게차와 크레인 - Python, BFS

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/388353

프로그래머스

 

 

코드 & 풀이

 

from collections import deque

def solution(storage, requests):
    N, M = len(storage), len(storage[0])
    new_storage = [list(row) for row in storage]
    answer = N * M  # 전체 칸 개수
    
    def can_go_outside(tmp_storage, i, j):
        direct = [(1, 0), (-1, 0), (0, -1), (0, 1)]
        visited = [[False] * M for _ in range(N)]
        que = deque([(i, j)])
        visited[i][j] = True
        
        while que:
            nx, ny = que.popleft()
            for dx, dy in direct:
                tx, ty = nx + dx, ny + dy
                
                # 창고 밖으로 나갈 수 있는 경우
                if tx < 0 or tx >= N or ty < 0 or ty >= M:
                    return True
                
                if 0 <= tx < N and 0 <= ty < M and not visited[tx][ty] and tmp_storage[tx][ty] == '-':
                    visited[tx][ty] = True
                    que.append((tx, ty))
        
        return False

    for request in requests:
        delete_boxes = []
        target = request[0]

        # target 위치 탐색
        for i in range(N):
            if target not in new_storage[i]: # 불필요한 탐색 pass
                continue
            for j, box in enumerate(new_storage[i]):
                if box == target:
                    if len(request) == 1:  # 외부로 연결된 경우만 삭제
                        if can_go_outside(new_storage, i, j):
                            delete_boxes.append((i, j))
                    else:  # 무조건 삭제
                        delete_boxes.append((i, j))

        # 삭제 처리
        for tx, ty in delete_boxes:
            new_storage[tx][ty] = '-'
            answer -= 1

    return answer

 

크레인 방식은 탐색해서 있으면 삭제

지게차의 경우 BFS를 통해 밖으로 나갈 수 있는지 탐색 후 삭제할 수 있으면 삭제

 

 

 

 

 

다음에 또 봐요