프로그래머스 지게차와 크레인 python

프로그래머스 지게차와 크레인 python

문제

A 회사의 물류창고에는 알파벳 대문자로 구분되는 컨테이너들이 있습니다.
이 컨테이너들은 세로로 n줄, 가로로 m줄로 이루어진 n × m 격자 형태로 놓여 있습니다.

각 컨테이너의 종류는 알파벳으로 표시되며,
출고 요청(request)이 들어올 때마다 두 가지 방식 중 하나로 출고가 진행됩니다.

1. 지게차 요청 (예: "A")

   • 알파벳 한 글자 요청입니다.
   • 외부와 연결되어 있는 해당 종류의 컨테이너만 꺼낼 수 있습니다.
   • 외부와 연결되어 있다는 뜻은, 컨테이너가 놓인 자리에서 4방향(상하좌우) 중 적어도 하나가 창고 밖과 이어진 경우입니다.
   • 내부 깊숙한 곳의 컨테이너는 꺼낼 수 없습니다.

2. 크레인 요청 (예: "BB")

   • 같은 알파벳 두 글자 요청입니다.
   • 해당 종류의 모든 컨테이너를 한 번에 꺼냅니다.
   • 접근 가능 여부는 고려하지 않습니다.

예를 들어 창고가 다음과 같을 때,

초기 상태	요청 순서	결과
["AZWQY", "CAABX", "BBDDA", "ACACA"]	["A", "BB", "A"]	11

첫 번째 요청 "A"에서는 지게차로 접근 가능한 A만 제거합니다.
두 번째 요청 "BB"에서는 모든 B 컨테이너를 제거합니다.
세 번째 요청 "A"에서는 다시 접근 가능한 A만 제거합니다.

모든 요청이 끝난 뒤 남은 컨테이너의 개수를 반환합니다.

---

아이디어

이 문제의 핵심은 “접근 가능한 컨테이너”를 판별하는 방식입니다.
이를 위해 BFS(너비 우선 탐색)를 사용합니다.

접근 가능한지 판단하기 위한 로직은 다음과 같습니다.

1. 특정 좌표 (i, j)가 출고 대상 문자(ch)와 일치할 경우,
   그 좌표가 외부와 연결되어 있는지 확인합니다.
2. 이때 주변 4방향으로 이동하며,
   인접한 곳이 0(빈 공간)이거나 창고 외부로 나가면 “접근 가능”으로 판정합니다.
3. 접근 가능하면 해당 위치의 컨테이너를 제거합니다.

한편, 요청 문자열의 길이가 2라면 크레인 요청이므로
해당 알파벳의 모든 컨테이너를 바로 제거합니다.

---

전체코드

from collections import deque

def Print(arr,c,r):
    for i in range(c):
        for j in range(r):
            print(arr[i][j], end='')
        print()

storage=["AZWQY", "CAABX", "BBDDA", "ACACA"]
requests=["A", "BB", "A"]

arr=[]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
for i in storage:
    arr2=[]
    for j in i:
        arr2.append(j)
    arr.append(arr2)

c=len(arr)
r=len(arr[0])

cnt=0
for ch in requests:
    Print(arr,c,r)
    print()
    for i in range(c):
        for j in range(r):
            if len(ch)==2 and ch[0]==arr[i][j]:
                arr[i][j]=0
            elif ch==arr[i][j]:
                Check=False
                check=[[0 for _ in range(r)] for _ in range(c)]
                q=deque()
                check[i][j]=1
                q.append([i,j])
                while q:
                    a,b=q.popleft()
                    for x,y in zip(dx,dy):
                        nx=b+x
                        ny=a+y
                        if nx<0 or nx>=r or ny<0 or ny>=c:
                            arr[i][j]='x'
                            Check=True
                            break
                        elif check[ny][nx]==0 and (0<=nx<r and 0<=ny<c) and arr[ny][nx]==0:
                            q.append([ny,nx])
                            check[ny][nx]=1
                    if Check:
                        break
    for i in range(c):
        for j in range(r):
            if arr[i][j]=='x':
                arr[i][j]=0

for i in range(c):
    for j in range(r):
        if arr[i][j]!=0:
            cnt+=1
print('cnt:', cnt)
for i in range(c):
    print(arr[i])

---

결론

이 코드는 지게차와 크레인 출고 시스템을 시뮬레이션합니다.

1. 크레인 요청("BB" 형태)은 단순히 해당 알파벳 전체를 제거합니다.
2. 지게차 요청("A" 형태)은 BFS를 통해 외부 접근 가능 여부를 판단하여 제거합니다.
3. 모든 요청을 순서대로 처리한 후, 남은 컨테이너 수를 세어 반환합니다.

이 방식은 문제 설명에 제시된 예시 입력
storage=["AZWQY", "CAABX", "BBDDA", "ACACA"], requests=["A","BB","A"]
에 대해 올바르게 11을 반환합니다.

즉, 이 풀이는 탐색 알고리즘을 이용해 접근 가능한 영역만 판단한 뒤 컨테이너를 제거하는 시뮬레이션 문제의 전형적인 풀이 구조입니다.