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

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

프로그래머스

 

문제 요약 

물류창고에는 알파벳으로 구분된 컨테이너들이 격자 형태로 놓여 있다.
컨테이너 제거 요청이 순서대로 들어오며, 요청 방식에 따라 제거 규칙이 다르다.

• 요청이 A 처럼 알파벳 하나로 들어오면 지게차를 사용한다.
  이 경우, 요청이 들어온 시점에 해당 알파벳 컨테이너가 창고 외부와 맞닿아 있는 경우에만 제거할 수 있다.
  즉, 컨테이너의 상·하·좌·우 중 하나라도 외부 공간과 연결되어 있어야 제거 대상이 된다.
• 요청이 AA 처럼 같은 알파벳이 두 번 반복되어 들어오면 크레인을 사용한다.
  이 경우에는 위치와 상관없이, 해당 알파벳 컨테이너를 모두 제거할 수 있다.

모든 요청을 순서대로 처리한 뒤, 창고에 남아 있는 컨테이너의 개수를 구하는 문제이다.

 

풀이

이 문제의 핵심은 지게차로 제거할 수 있는 컨테이너가 어떤 상태인지 정확히 판단하는 것이다.

크레인을 사용하는 경우는 단순하다.
요청된 알파벳과 일치하는 컨테이너를 창고 전체에서 찾아 모두 제거하면 된다.

반면 지게차를 사용하는 경우에는,
요청이 들어온 그 순간에 해당 컨테이너가 창고 외부와 연결되어 있는지를 판단해야 한다.

이를 위해 다음과 같은 방법을 사용한다.

1. 창고 바깥에서 시작해, 빈 공간으로만 이동하는 BFS를 수행한다.
2. 이미 제거된 위치는 빈 공간으로 간주하여 탐색을 계속한다.
3. 이렇게 하면 창고 외부와 연결된 모든 빈 공간을 구할 수 있다.
4. 제거 대상 알파벳 컨테이너 중에서,
   상·하·좌·우 중 하나라도 이 외부와 연결된 빈 공간과 맞닿아 있는 컨테이너만 지게차로 제거한다.

 

from collections import deque

def solution(storage, requests):
    answer = 0
    n = len(storage)
    m = len(storage[0])
    N = n+2
    M = m+2

    remove = [ [1] * m for _ in range(n) ]
    
    def calc_outside():
        q = deque()
        visited = [[0] * M for _ in range(N)]
        
        q.append((0,0))
        visited[0][0] = 1
        
        while q:
            x, y = q.popleft()
            for dx, dy in ((1, 0), (0,1), (-1,0),(0,-1)):
                nx, ny = x+dx, y+dy
                if nx <0 or nx >=N or ny <0 or ny>=M or visited[nx][ny] == 1:
                    continue
                if (nx == 0 or nx == N-1 or ny ==0 or ny == M-1) or (remove[nx-1][ny-1]) == 0 : # 테두리는 자유롭게 이동가능, 테두리가 아닌데 이미 제거되어 있는 경우 진입 가능
                    q.append((nx, ny))
                    visited[nx][ny] = 1
        return visited
                
    for r in requests:
        target = r[0]
        if len(r) == 1: #지게차
            #외부에서 도달할 수 있는 칸을 모두 구함
            out = calc_outside()
            for i in range(n):
                for j in range(m):
                    px, py = i+1, j+1
                    if storage[i][j] == target and (out[px+1][py] == 1 or out[px][py+1] == 1 or out[px-1][py] == 1 or out[px][py-1] == 1):
                        remove[i][j] = 0 
        else : #크레인
            for i in range(n):
                for j in range(m):
                    if storage[i][j] == target:
                        remove[i][j] = 0
    
    for i in range(n):
        for j in range(m):
            if remove[i][j] == 1:
                answer+=1
    return answer

 

파이썬 팁

함수 내부에서 다시 함수를 정의하고, 이를 반복적으로 호출하는 방식은
파이썬에서는 생각보다 비용이 큰 편인것 같다. 

실제로 while 문 안에 있는 if 조건을 별도의 함수로 분리했을 때,
논리적으로는 동일하고 문제도 통과했지만,
함수 호출 오버헤드로 인해 실행 시간이 약 1~10ms 정도 증가하는 것을 확인할 수 있었다.

 

def calc_outside():
        q = deque()
        visited = [[0] * M for _ in range(N)]
        
        q.append((0,0))
        visited[0][0] = 1
        
        def is_empty(nx, ny):
            if visited[nx][ny] == 0:
                if (nx == 0 or nx == N-1 or ny ==0 or ny == M-1) or (remove[nx-1][ny-1]) == 0 : 
                    # 테두리는 자유롭게 이동가능, 테두리가 아닌데 이미 제거되어 있는 경우 진입 가능
                    return True
            return False
        
        while q:
            x, y = q.popleft()
            for dx, dy in ((1, 0), (0,1), (-1,0),(0,-1)):
                nx, ny = x+dx, y+dy
                if nx <0 or nx >=N or ny <0 or ny>=M:
                    continue
                if is_empty(nx ,ny):
                    q.append((nx, ny))
                    visited[nx][ny] = 1
        return visited