[Programmers, Python] Lv3. 아이템 줍기

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기

프로그래머스 - Lv3. 아이템 줍기

문제 설명

 

 

제한 사항

풀이

나는 알고리즘 문제를 풀 때 문제를 세분화된 과제로 정리한다.
문제 요구사항을 읽으면서 정리한 과제는 아래와 같다.

• 겹쳐진 직사각형 사이에서 테두리 구분하기
  • 백트래킹시 테두리의 좌표를 어떻게 구별할 것인지

사실상 테두리의 좌표만 정리한다면 그 이후부터는 일반적인 그래프 탐색 문제와 다를 것이 없다.

처음에는 테두리 구분을 각각 직사각형을 모두 구분하며 하나하나 테두리를 찾으려고 했다.
그러나 이는 높은 시간 복잡도를 요구하기에 바로 마음을 접었다.

많은 고민을 했지만 결국 테두리를 구분할 방법을 찾지 못했다.
다른 분의 아이디어를 참고하여 문제를 다시 풀었다.

풀이 방법

1. 2차원 리스트를 만들어 테두리는 1, 사각형 내부는 0, 외부는 -1로 채운다.
2. BFS로 최단거리를 찾는다.

여기서 주의해야 할 점이 있다. 테두리를 1로 만들어서 문제를 풀면 테두리를 돌 때 안쪽으로 파여진 경로는 스킵하고 지나갈 수 있다.

때문에 그래프틑 2배율해서 문제를 풀어줘야한다. 그래프를 2배율 해서 문제를 풀었으니 답을 출력할 때는 단순히 2로 나누어서 반환하면 된다.

풀이 코드

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    graph = [[-1]*102 for _ in range(102)]
    visited = [[1]*102 for _ in range(102)]

    # graph 정리
    for rec in rectangle:
        x1,y1,x2,y2 = map(lambda x: 2*x, rec)

        for x in range(x1, x2+1):
            for y in range(y1,y2+1):
                # 테두리를 제외한 점은 사각형 내부이기 때문에 0
                if x1<x<x2 and y1<y<y2:
                    graph[x][y] = 0
                # 테두리의 점이 다른 사격형의 내부가 아니라면 1
                elif graph[x][y] != 0:
                    graph[x][y] = 1


    item = (itemX*2, itemY*2)
    start = (characterX*2, characterY*2)
    q = deque()
    q.append(start)

    while q:
        current_x, current_y = q.popleft()

        if (current_x, current_y) == item:
            return visited[current_x][current_y]//2

        for (rx, ry) in ((1,0), (0,1), (-1,0), (0,-1)):
            nx, ny = current_x+rx, current_y+ry
            if graph[nx][ny] == 1 and visited[nx][ny] == 1:
                visited[nx][ny] = visited[current_x][current_y]+1
                q.append((nx,ny))

살펴볼 점

item = (itemX*2, itemY*2)
start = (characterX*2, characterY*2)

위 코드를 보면 본래 좌표에 2를 곱해주고 있다. 위에서 언급했듯이 경로를 스킵하는 경우를 방지하기 위한 조치이다.

2차원 리스트를 만들어서 그래프 정리

# graph 정리
for rec in rectangle:
    x1,y1,x2,y2 = map(lambda x: 2*x, rec)

    for x in range(x1, x2+1):
        for y in range(y1,y2+1):
            # 테두리를 제외한 점은 사각형 내부이기 때문에 0
            if x1<x<x2 and y1<y<y2:
                graph[x][y] = 0
            # 테두리의 점이 다른 사격형의 내부가 아니라면 1
            elif graph[x][y] != 0:
                graph[x][y] = 1

직사각형 정보가 들어있는 리스트인 rectangle에서 직사각형을 하나씩 꺼내 우선 테두리를 제외한 점은 모두 직사각형의 내부 점이기 때문에 0으로 변경한다.

테두리의 점은 해당 점이 다른 직사각형의 내부의 점이 아니라면 전체 도형의 테두리에 해당하기 때문에 1로 변경한다.

---

여기까지 했다면 문제는 다 푼 것과 같다. 이후부터는 일반적인 bfs와 같다.

BFS

item = (itemX*2, itemY*2)
start = (characterX*2, characterY*2)
q = deque()
q.append(start)

while q:
    current_x, current_y = q.popleft()

    if (current_x, current_y) == item:
        return visited[current_x][current_y]//2

    for (rx, ry) in ((1,0), (0,1), (-1,0), (0,-1)):
        nx, ny = current_x+rx, current_y+ry
        if graph[nx][ny] == 1 and visited[nx][ny] == 1:
           visited[nx][ny] = visited[current_x][current_y]+1
           q.append((nx,ny))

결과

다른 풀이

https://school.programmers.co.kr/questions/72900

변화 규칙을 적용해서 푼 풀이도 있다.
생각하지도 못한 방법으로 푼 풀이라서 그런가 충격을 받은 풀이이다.