프로그래머스 ) Lv2. 지게차와 크레인 [ python, bfs ]

 

---

분류 : bfs, 약간 구현

 

---

keypoint : storage 테두리를 0으로 채우기

기본 배열에 0으로 상하좌우를 둘러줘서 접근 가능한 영역을 구분할 수 있다.

---

code

def fork(storage, box): # 지게차
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    index = []
    
    for i in range(1, len(storage)-1):
        for j in range(1, len(storage[0])-1):
            if storage[i][j] == box:
                for k in range(4):
                    nx, ny = i + dx[k], j + dy[k]
                    if storage[nx][ny] == "0":  # 지게차로 꺼낼 수 있으면 (외부쪽 박스)
                        index.append((i, j))    # 위치 저장(바로 꺼내면 옆에있는 박스도 꺼낼 수 있게 됨)
                        break
    
    for i, j in index:  # 저장된 박스 꺼내기
        storage[i][j] = "0"
        isOutside(storage, i, j) # 주변에 빈 공간있으면 외부랑 연결

def crane(storage, box): # 크레인
    for i in range(1, len(storage)-1):
        for j in range(1, len(storage[0])-1):
            if storage[i][j] == box:
                storage[i][j] = "1"
                isOutside(storage, i, j) # 주변에 빈 공간있으면 외부랑 연결

def isOutside(storage, x, y):   # 박스 꺼냈을 때 외부랑 연결된 공간 찾아서 연결
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    outside = False

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if storage[nx][ny] == "0":  # 외부랑 연결되어 있으면
            storage[x][y] = "0"
            outside = True         
            break
    
    if outside:
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if storage[nx][ny] == "1":  # 빈 공간을 외부랑 연결 "1" -> "0"
                storage[nx][ny] = "0"
                isOutside(storage, nx, ny)  # 붙어있는 빈 공간을 더 찾기

def solution(storage, requests):
    answer = 0
    # 0 = 외부랑 연결된 곳, 1 = 사방이 막힌 빈 공간
    storage = [list("0" + i + "0") for i in storage]    # 테두리를 "0"으로 채우기
    storage.insert(0, list("0" * len(storage[0])))
    storage.append(list("0" * len(storage[0])))

    for q in requests:
        if len(q) == 1:
            fork(storage, q)
        else:
            crane(storage, q[0])
    
    for i in range(1, len(storage)-1):
        for j in range(1, len(storage[0])-1):
            if storage[i][j] not in ["0", "1"]:
                answer += 1
    
    return answer

---

중요한 내용 lambda 

 

# N×N 2차원 배열

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

# 방문한 노드일 경우 True / 방문하지 않은 노드일 경우 False
visited = [[False for _ in range(N)] for _ in range(N)]


def BFS(r, c):
    q = deque()  # 탐색해야 하는 노드들을 담는 큐
    
    # 탐색을 시작하는 노드 (r, c)
    q.append((r, c))
    visited[r][c] = True
    
    route = []  # 탐색 경로 저장
    route.append((r, c))

    # 큐에 들어가 있는 노드가 없을 때까지(탐색이 완료될 때까지) 반복
    while q:
        # 현재 탐색 중인 노드 (y, x)
        y, x = q.popleft()
        
        for i in range(4):
            # 인접 노드 (ny, nx)
            ny = y + dy[i]
            nx = x + dx[i]
            
            # 조건문을 통해 탐색 가능한 노드인지 확인
            if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append((ny, nx))  # 인접한 노드를 전부 탐색하기 위해 큐에 다시 append
                route.append((ny, nx))
                
    return route