[프로그래머스] 아이템 줍기 (Python)

📌 아이템 줍기

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

풀이과정

어려운 문제이다. 지나는 점을 표시해두고 문제를 풀려하면 문제가 발생한다. 연결이 되어있는 점인지, 아니면 따로 떨어져 있는 점인지 구분 할 수 없다.
예를 들어, 테두리를 1로 둔다고 하자. 이때 그대로 점을 찍었을 때, 이러한 모양의 그래프가 있다고 하자.
0 0 0 0 0
0 0 1 1 1
0 0 1 1 0
0 0 0 1 1
이 경우 노란색 부분이 최소 거리가 될 것이다. 하지만 사실 이 그래프는 4번째 행에서 1이 위아래로 서로 연결되어 있지 않는 구조이다. 따라서 정답은 다음과 같이 나와야한다.
0 0 0 0 0
0 0 1 1 1
0 0 1 1 0
0 0 0 1 1
즉, 1끼리 어디가 연결이 된 것인지 알 수 없으므로, 크기를 두배로 늘려주어야 한다. 크기를 늘려준다면
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 1 1 0
이렇게 깔끔하게 구분되어 질 것이다.

따라서 모든 것을 다 두배를 해주어야 한다. characterX, characterY, itemX, itemY 모두 두배를 빼먹지 않고 잘 해주야 하고, 그래프의 크기도 넉넉히 102로 만들어 주어야 한다.

• 테두리를 1로 먼저 표시한 후, 내부의 점은 5로 표시한다. 이유는 다른 직사각형에서 테두리였던 부분이 다른 직사각형에서 내부라면 무조건 내부가 되기 때문이다.
• bfs를 사용하여 방문하지 않았고, 값이 1인 좌표를 지속적으로 방문하여 타겟의 값(두배 한 타겟)과 같은지 확인한다.

💯 정답

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = int(1e9)
    graph = [[0]*102 for _ in range(102)]
    for data in rectangle:
        lx,ly,ux,uy = data
        for i in range(lx*2, (ux*2+1)):
            graph[i][ly*2] = 1 # 테두리
            graph[i][uy*2] = 1 # 테두리
        for i in range(ly*2, (uy*2+1)):
            graph[lx*2][i] = 1 # 테두리
            graph[ux*2][i] = 1 # 테두리
    for lx, ly, ux, uy in rectangle:
        for i in range(lx * 2 + 1, ux * 2):
            for j in range(ly * 2 + 1, uy * 2):
                graph[i][j] = 5 # 내부
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    visited = [[False]*102 for _ in range(102)]
    
    q = deque([[characterX*2, characterY*2, 0]])
    visited[characterX*2][characterY*2] = True
    
    while q:
        nx, ny, dist = q.popleft()
        for i in range(4):
            tx = nx + dx[i]
            ty = ny + dy[i]
            if graph[tx][ty] == 1 and visited[tx][ty] == False and tx>=0 and tx<=100 and ty>=0 and ty<=100:
                if tx == itemX*2 and ty == itemY*2:
                    answer = min(answer, dist+1)//2
                q.append([tx, ty, dist+1])
                visited[tx][ty] = True
        
    return answer

• 사실 visited는 필요하지 않음. 지나간 점은 graph[tx][ty] = 0 으로 만들어주면 된다.
• answer도 처음 발견한 타겟에서 무조건 최소거리가 나올 것이기에 min이 필요 없다. 타겟값과 같으면 바로 break시키면 된다. break 시키기 좋게, 타겟값과 비교확인 하는 부분을 popleft한 후로 옮기면 된다.

(수정 2023.03.03)

• 내부 안의 값을 설정할때 테두리를 다 한다음에 따로 for문을 돌려야 한다.
  다시 풀었을 때 이것 때문에 시간을 엄청 할애했다.