프로그래머스 Lv3 | dfs/bfs | 아이템 줍기

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

프로그래머스

 

 

직사각형이 1개일 때는 어렵지 않게 구사했는데

일단 좌표축을 2배로 늘릴 생각을 못했고....

한 칸짜리 애매한 접촉이 두 칸 이상의 구조로 펴지면서
경계/내부/바깥이 분명하게 나뉨
-> 너무 조밀해서 구분이 안 되던 걸 조금 확대해서 기하 구조 보존

길을 표시한 새로운 배열을 만들 생각은 했는데 좌표축 때문에 구현이 안됐음..

대충 머리속에는 있었지만 너무 어려웠음 흑..

bfs 구현은 어렵지 않았는데 rectangle_map 구하는게 hell

 

from collections import deque
def bfs(rectangle, rectangle_map, characterX, characterY, itemX, itemY):
    queue = deque([(characterX, characterY, 0)])
    rectangle_map[characterX][characterY] = 2
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while queue:
        x, y, cnt = queue.popleft()
        if x == itemX and y == itemY:
            return cnt
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < 102 and 0 <= ny < 102:
                if rectangle_map[nx][ny] == 1:
                    queue.append((nx, ny, cnt+1))
                    rectangle_map[nx][ny] = 2

        
def solution(rectangle, characterX, characterY, itemX, itemY):
    # 테두리가 명확하지 않아서 2배로 좌표 확장한 다음 나중에 1/2 곱해서 줄이기
    # rectangle_map을 통해서 테두리 정의하기
    
    rectangle_map = [[0]*51*2 for _ in range(51*2)]
    
    characterX = 2*characterX
    characterY = 2*characterY
    itemX = 2*itemX
    itemY = 2*itemY
    
    # 직사각형 색칠하기
    for rec in rectangle:
        x1, y1, x2, y2 = rec
        x1, y1, x2, y2 = 2*x1, 2*y1, 2*x2, 2*y2
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                rectangle_map[i][j] = 1
    
    # 내부 지우기
    for rec in rectangle:
        x1, y1, x2, y2 = rec
        x1, y1, x2, y2 = 2*x1, 2*y1, 2*x2, 2*y2
        for i in range(x1+1, x2):
            for j in range(y1+1, y2):
                rectangle_map[i][j] = 0 
    
    answer = bfs(rectangle, rectangle_map, characterX, characterY, itemX, itemY)
    
    return answer//2