[프로그래머스] 388353. 지게차와 크레인 | Python3, Level2, BFS

 

프로그래머스

---

문제 요약

1.창고에서 컨테이너를 출고시켜야 한다. 컨테이너A를 출고하면 창고 내의 접근가능한 모든 컨테이너A를 출고시킨다. 

2. 지게차로 출고하는 경우 지게차가 한면이라도 외부와 접촉되는 컨테이너만 출고할 수 있다. 크레인으로 출고할때는 모든 컨테이너를 출고할 수 있다. 

하늘에서 바라본 모습이라고 생각하면 이해하기 편하다.

 

3. 아래와 같이 storage, requests가 주어질 때,

⭐모든 요청이 완료되었을 때 남아있는 컨테이너의 개수를 반환해라

storage = 컨테이너의 위치 정보를 담은 1차원 배열
ex) ["AZWQY", "CAABX", "BBDDA", "ACACA"]

requests = 출고할 컨테이너의 종류와 출고 방법을 담은 1차원 배열
ex) ["A", "BB", "A"]
requests[i]의 길이가 1이면 지게차으로 출고, 2이면 크레인으로 출고

---

해결 프로세스

1. 컨테이너 위치 정보를 2차원 배열로 변환한 후 요청들을 순차적으로 처리하며 출고 처리

2. 크레인 출고인 경우 그냥 출고처리 시킴. 지게차 출고인 경우 BFS로 외부와 연결되어있는지 확인 후 출고처리

3. 모든 요청을 처리한 후 아직 출고되지 않은 컨테이너를 카운트하여 반환

---

정답 소스코드

import copy

def solution(storage, requests):
    그래프 = [list(s) for s in storage]

    # 출고 요청 순차적으로 처리
    for request in requests:
        그래프복사본 = copy.deepcopy(그래프)     # 요청당시를 기준으로 작업해야하므로 복사본 생성
        출고컨테이너 = request[0]
        장비 = '크레인' if len(request) > 1 else '지게차'

        # 출고해야하는 컨테이너 찾아서 출고가능하면 출고시키기
        for i, containers in enumerate(그래프):
            for j, 현재컨테이너 in enumerate(containers):
                if 현재컨테이너 == 출고컨테이너:
                    if 장비 == '크레인' or 지게차접근가능(그래프복사본, i, j):   # 크레인으로 출고하거나 지게차가 접근가능하면 출고 가능
                        그래프[i][j] = ''

    #
    answer = sum(sum(container != '' for container in containers) for containers in 그래프)

    return answer

# BFS로 외부와 연결되어있는지 조회
def 지게차접근가능(graph, i, j):
    rows, cols = len(graph), len(graph[0])
    방문가능여부 =  [[container == '' for container in containers] for containers in graph]   # 비어있는 공간은 방문가능함
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    큐 = [(i, j)]
    while len(큐) > 0:
        x, y = 큐.pop(0)

        # 상하좌우 방문
        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            # 외부를 방문하는 경우 지게차로 접근 가능! True 반환~
            if not (0 <= nx < rows) or not (0 <= ny < cols):
                return True

            # 아직 방문하지 않은 곳이면 방문처리
            if 방문가능여부[nx][ny]:
                방문가능여부[nx][ny] = False
                큐.append((nx, ny))

    return False