[프로그래머스][level3] 아이템 줍기 - python

문제 링크

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

코딩테스트 연습 - 아이템 줍기

풀이 

- bfs 문제 

여기서 중요한 것은 그래프의 크기를 두배로 늘리는 것이다.

예를 들어, 아래 그래프의 (3,5) 위치에서 (3,6)으로 위로 한칸 이동할 수 없는데, bfs에 따르면 이동이 가능하다고 판단하기 때문에 두배로 늘려주는 것이다. 

 

따라서 

1. 네모 테두리만 표시

2. bfs로 최단거리 구하기 

from collections import deque 

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def bfs(board, cx,cy,ix,iy):
    q = deque()
    # 현재 위치, 이동 횟수 
    q.append((cx,cy,0))
    
    visited = [ [0] * 101 for _ in range(101)]
    visited[cx][cy] = True 
    
    while q :
        x ,y, cnt = q.popleft() 
        
        # 아이템 위치이면
        if x == ix and y == iy :
        	# 두배로 늘렸으므로, 2로 나눈 값 
            return cnt // 2 
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
        
        	# 범위에 속하고, 이동 가능한 위치이고, 방문하지 않았으면 
            if 0 <= nx < 101 and 0 <= ny < 101 and board[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx,ny,cnt+1))
                visited[nx][ny] = True 
                
def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    
    board = [ [0] * 101 for _ in range(101)]

	# 네모 테두리, 내부 모두 1 로 표시 
    for x1, y1, x2, y2 in rectangle :
        for i in range(x1*2 , x2*2+1):
            for j in range(y1*2, y2*2+1):
                board[i][j] = 1 
                
    # 네모 내부는 0으로 표시하여, 테두리만 1로 표시되도록 
    for x1, y1, x2, y2 in rectangle :
        for i in range(x1*2+1 , x2*2):
            for j in range(y1*2+1, y2*2):
                board[i][j] = 0 
    
    # 현재 위치, 아이템 위치 두배 늘리기 
    cx, cy = characterX*2, characterY * 2 
    ix, iy = itemX *2 , itemY *2 
    
    return bfs(board, cx,cy,ix,iy)