[Lv.2 / 프로그래머스 / 파이썬] 지게차와 크레인 (2025 프로그래머스 코드챌린지 1차 예선)

 

 

 

 

프로그래머스

 

풀이

 

requests를 순회하며 처리하는 시뮬레이션에서 BFS를 수행하는 문제이다. 

 

BFS를 가장자리부터 진행하도록 하기 위해 빈 값으로 storage를 래핑해주었다.

그리고 주어진 요청을 순회하며 BFS 혹은 전체 삭제를 진행한다.

순회가 종료되면, 남은 블럭의 개수를 리턴한다.

 

BFS를 진행할 때, 현재 요청 타입에 맞는 블럭과 만났을 때 즉시 삭제하지 않도록 따로 삭제 예정 리스트를 구성한 다음 처리해야 한다. 그렇지 않으면 같은 타입의 블럭 뭉치를 만났을 때, 연결된 모든 부분을 삭제하게 된다.

 

def solution(storage, requests):
    # 빈 값으로 storage 래핑
    empty_row = ["-" * len(storage[0])]
    storage = empty_row + storage + empty_row
    storage = [list("-" + row + "-") for row in storage]
    
    N, M = len(storage), len(storage[0])
    move = [(1,0), (0,1), (-1,0), (0,-1)]
    
    # 요청 순회
    for req in requests:
        t = req[0]
        
        # 알파벳 2개 요청인 경우 전체 삭제
        if len(req) == 2:
            for i in range(N):
                for j in range(M):
                    if storage[i][j] == t:
                        storage[i][j] = "-"
        else: # 알파벳 1개 요청인 경우, 바깥에서 접근 가능한 부분만 삭제
            visited = [[False] * M for _ in range(N)]
            q = [(0, 0)]
            # BFS
            del_list = []
            while q:
                # 방문 체크
                x, y = q.pop()
                if visited[x][y]:
                    continue
                visited[x][y] = True
                
                # 탐색
                for a, b in move:
                    dx, dy = x+a, y+b
                    # index out of range 방지
                    if dx >= N or dx < 0 or dy >= M or dy < 0:
                        continue
                
                    # 타입 비교 후 제거 목록에 추가
                    if storage[dx][dy] == t:
                        del_list.append((dx, dy))
                    
                    # 다음 탐색 후보지 추가
                    if visited[dx][dy] or storage[dx][dy] != "-":
                        continue
                    
                    q.append((dx, dy))
            
            # 컨테이너 제거
            for x, y in del_list:
                storage[x][y] = "-"
                
    # 결과 반환
    result = 0
    for i in range(N):
        for j in range(M):
            if storage[i][j] != "-":
                result += 1
    return result