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

문제

 

 

 

 

 

문제를 접하고서 경로를 찾는 것 자체는 최단경로 찾을 때처럼 해결해주면 될 것같은데 주어진 직사각형의 테두리만 따라서 경로를 찾아주는 것이 구현하기 너무 까다롭다는 생각이 들었다.

 

 

 

그리고 결국 이 부분은 구글링을 통해 도움을 얻었다.

 

이 부분을 해결할 때 크게 3가지의 단계가 필요하다

 

1. 사각형 내부에 포함되는 부분은 0으로 처리

2. 경계선에 해당되는 부분은 1로 처리

3. 좌표를 2배로 키워준다 (왜냐하면 ㄷ 자와 같은 형태의 경로를 탐색할때 ㅁ으로 인식될 수 있으므로 이를 방지하고자 좌표의 크기를 2배로 키워줌)

 

 

이 3가지 단계를 적용한 코드는

 

 

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    #범위가 50까지인데 2배할 예정이므로 102
    field = [[-1] * 102 for _ in range(102)]
    
    for r in rectangle:
        x1,y1,x2,y2 = map(lambda x:x*2, r)
        for i in range(x1,x2+1):
            for j in range(y1, y2+1):
                #사각형 내부에 해당되는 부분
                if x1< i <x2 and y1< j < y2:
                    field[i][j] = 0
                #현재 사각형의 경계선이면서 다른 사각형의 내부가 아닌 부분 1로처리 
                elif field[i][j] != 0:
                    field[i][j] = 1
    q = deque()
    q.append((characterX*2, characterY*2))
    visited = [[1] * 102 for _ in range(102)]
    visited[characterX*2][characterY*2] = 0
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while(q):
        x,y = q.popleft()
        if x == itemX*2 and y == itemY*2:
            #정답은 2로 나누어 반환
            answer = visited[x][y]//2
            break
            
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if field[nx][ny] == 1 and visited[nx][ny] == 1:
                q.append((nx,ny))
                visited[nx][ny] = visited[x][y] + 1
    
    return answer

 

 

 

 

이렇게 된다.

 

사각형의 테두리에 해당되는 부분에서만 경로를 찾는 걸 구현하는 부분이 너무 어려웠던 문제이다.