[Level 2 | Python] 지게차와 크레인 (2025 프로그래머스 코드챌린지)

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

프로그래머스

 

문제

https://jinsang-2.tistory.com/129

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

백준 치즈 문제와 비슷하다. 

 

물류창고에 알파벳 컨테이너가 있는데, 지게차 같은 경우에는 "A"와 같은 형태이며 외곽에 있는 것들만 꺼낼 수 있다. 외곽부터 껍질 깎기 느낌으로 생각하면 된다. 크레인 같은경우에는 요청된 모든 종류의 컨테이너를 꺼낸다. 

첫번째 세번째는 지게차로 'A' 꺼내기, 두번째 예시는 크레인으로 'B' 컨테이너 다 꺼내기

 

풀이 과정

위에 백준 치즈 문제와 같은 해결법으로 생각했다. n*m의 직사각형 형태의 외곽으로 한 칸씩 늘려서 밖이 한 집합으로 연결되게 만들어서 지게차 일 때는 외곽쪽을 녹이고 크레인 일 때는 그냥 다 뽑아버릴 것이다. 

visited 배열을 하나 만들어서 외곽은 -1로 표시하고 크레인 일 때는 그냥 다 찾고 -1로 바꿔버리면 되고, 지게차 일때가 중요한데, 지게차 일 때에는 n*m에서 상하좌우로 한 칸씩 더 늘린 visited 0,0부터 bfs 탐색해서 해당 알파벳을 찾고 -1로 변환해주면 된다. 

핵심은 지게차로 외곽 갉아 먹기이다. 

from collections import deque
def solution(storage, requests):
    answer = 0
    n=len(storage)
    m=len(storage[0])
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    # vistied 배열 만들기
    visited = [[-1]+[1] * (m)+[-1] for _ in range(n)]
    visited = [[-1]*(m+2)] + visited + [[-1]*(m+2)]
    
    def forklift(alpa):
        queue = deque([(0,0)])
        alpa_li = []
        v=[[0]*(m+2) for _ in range(n+2)]
        v[0][0]=1
        while queue:
            x,y=queue.popleft()
            for i in range(4):
                nx=dx[i]+x
                ny=dy[i]+y
                if 0<=nx<n+2 and 0<=ny<m+2 and v[nx][ny]==0 and visited[nx][ny]==-1:
                    v[nx][ny]=1
                    queue.append((nx,ny))
                if 0<=nx<n+2 and 0<=ny<m+2 and visited[nx][ny]==1 and storage[nx-1][ny-1]==alpa:
                    alpa_li.append((nx,ny))
        
        for x,y in alpa_li:
            visited[x][y]=-1
    
    def crane(alpa):
        for i in range(n):
            for j in range(m):
                if storage[i][j]==alpa:
                    visited[i+1][j+1]=-1
                    
    tmp=set()                                           
    for request in requests:
        if len(request)==1:
            forklift(request)
        else:
            if request[0] not in tmp:
                crane(request[0])

                tmp.add(request[0])

    for i in visited:
        answer+=i.count(1)