[프로그래머스] 위클리챌린지_11주차_아이텝 줍기

📕 문제

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

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

 

💡 풀이법

: 혼자 풀어보려다 포기.. 먼저 사각형의 테두리에 해당하는 좌표들을 1로 해서 행렬을 만든다. 좌표를 2배로 할 생각을 한 사람들 정말 대단하다. 2배로 늘리는 이유는 아래와 같다.

파란점에 있을 경우 파란 화살표 방향으로 이동해야하지만 위의 좌표에도 1이 표시되어 있기 때문에 컴퓨터는 파란점과 빨간점이 이어져있다고 생각을 해버리는것..! 그래서 좌표를 2배로 늘려서 아예 붙어있지 않게끔 만드는 것이다! 2배로 만들어서 행렬을 만든 이후에는 bfs를 써서 가장 가까운 거리를 구하면 된다!

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    board = [[0] * 101 for i in range(101)]
    cX, cY = 2 * characterX, 2 * characterY
    iX, iY = 2 * itemX, 2 * itemY
    
    for x1, y1, x2, y2 in rectangle:
        for i in range(2*x1, 2*x2+1):
            for j in range(2*y1, 2*y2+1):
                board[i][j] = 1
    
    for x1, y1, x2, y2 in rectangle:
        for i in range(2*x1+1, 2*x2):
            for j in range(2*y1+1, 2*y2):
                board[i][j] = 0
    
    dxy = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    visited = [[0] * 101 for i in range(101)]
    visited[cX][cY] = 1
    queue = deque([(cX, cY)])
    while queue:
        x, y = queue.popleft()
        
        if (x, y) == (iX, iY):
            return (visited[x][y] - 1) // 2
        
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            
            if 0 <= nx < 101 and 0 <= ny < 101 and board[nx][ny] and not visited[nx][ny]:
                visited[nx][ny] = visited[x][y] +1
                queue.append((nx, ny))
        
    return answer