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

lv. 3 단계의 코딩 테스트 연습 문제 중 '아이템 줍기'에 대한 풀이를 설명하고 있습니다.

 

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

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

추천글

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 너무 너무 귀찮게 구는 문제였다.
• 처음에는 사각형의 테두리와 그 내부를 모두 1로 칠하고, 외곽 라인을 BFS로 탐색하면서 도착 지점까지 가려고 했는데, ㄷ 자 모양에서 자꾸 건너뛰는 문제가 생겼다.
• 또, 사각형의 높이 또는 너비가 1일 때, 사각형을 관통해버리는 문제도 있었다.
  • (이제 생각해보면 이것은 조건을 통해서 해결 가능할 것 같다.)
  • 이 조건을 확인하는 방법이 궁금하면, 코드에서 line 33-45를 참고하면 된다.
• 그래서 생각한 것은 사각형의 외곽 라인을 그래프처럼 x 좌표에서 y 좌표로 이동하는 식으로 구현한 것이다.

 

• 사각형을 하나 입력받으면, 해당 사각형의 테두리에 포함된 모든 점들을 가지고 그래프를 만든다. 이 때, 각 점 사이는 양방향임을 잊지 말자.
• 아래의 코드는 lines라는 defaultdict에 특정 점에서 어떤 점으로 이동 가능한 지를 담는 코드이다.

for (x1, y1, x2, y2) in rectangle:
    for i in range(x1, x2):
        lines[(i, y1)].append((i+1, y1))
        lines[(i+1, y1)].append((i, y1))

        lines[(i, y2)].append((i+1, y2))
        lines[(i+1, y2)].append((i, y2))
    for i in range(y1, y2):
        lines[(x1, i)].append((x1, i+1))
        lines[(x1, i+1)].append((x1, i))

        lines[(x2, i)].append((x2, i+1))
        lines[(x2, i+1)].append((x2, i))

 

 

• 이런 식으로 모든 사각형들의 외곽 점들을 노드로 하는 그래프를 다 만들었으면, 이제 사각형들이 겹쳐짐으로 인해 더이상 외곽 지점이 아닌 점들을 골라내야 한다.

• 위의 그림과 같은 지점들이 될 수 있다.
• 이런 경우, 우리는 사각형 안에 있는 점으로 이동하는 간선을 제거한다.
• 이건 아래 코드처럼 단순하게 구현할 수 있다.
• 앞서 만든 그래프의 각 노드(딕셔너리에서는 키)를 가져와서 사각형들 안에 위치한 점인지 확인하면 된다.

# 내부 점들 모두 제거
for (x, y) in lines:
    for (x1, y1, x2, y2) in rectangle:
        if x > x1 and x < x2 and y > y1 and y < y2:
            pointsInRectangle.append((x, y))
for (x, y) in pointsInRectangle:
    lines.pop((x, y), None)

 

 

• 이제 끝났으니 BFS를 돌면 되나?
• 절대 아니다.
• 어떤 문제가 남았냐면 아래와 같다.

• 저렇게 너비가 1인 사각형이 있는 경우, 빨간색 포인트에서 다른 빨간색 포인트로 이동이 가능하다.
• 왜냐하면, 2번 과정에서의 코드를 거치더라도 저 점들은 사각형 외곽에 있는 것으로 판단되기 때문이다.
• 따라서 너비 혹은 높이가 1인 사각형이 있는 경우, 저렇게 사각형을 관통하는 간선들은 모두 제거해야 한다.

# 사각형을 가로지르는 선분들 제거, 가로나 세로의 길이가 1인 사각형들에서만 발생함
for (x1, y1, x2, y2) in rectangle:
    if x2 - x1 == 1:
        for i in range(y1+1, y2):
            if (x2, i) in lines[(x1, i)]:
                lines[(x1, i)].remove((x2, i))
            if (x1, i) in lines[(x2, i)]:
                lines[(x2, i)].remove((x1, i))
    if y2 - y1 == 1:
        for i in range(x1+1, x2):
            if (i, y2) in lines[(i, y1)]:
                lines[(i, y1)].remove((i, y2))
            if (i, y1) in lines[(i, y2)]:
                lines[(i, y2)].remove((i, y1))

• 이제 그러면 진짜 외곽 점들과 그 점들 사이의 관선으로 이루어진 깔끔한 그래프가 완성된다.
• 따라서 이 그래프를 BFS를 통해서 탐색하면 된다.

코드

from collections import deque, defaultdict

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    
    lines = defaultdict(list)
    
    for (x1, y1, x2, y2) in rectangle:
        for i in range(x1, x2):
            lines[(i, y1)].append((i+1, y1))
            lines[(i+1, y1)].append((i, y1))
            
            lines[(i, y2)].append((i+1, y2))
            lines[(i+1, y2)].append((i, y2))
        for i in range(y1, y2):
            lines[(x1, i)].append((x1, i+1))
            lines[(x1, i+1)].append((x1, i))
            
            lines[(x2, i)].append((x2, i+1))
            lines[(x2, i+1)].append((x2, i))
    
    pointsInRectangle = []
    
    # 내부 점들 모두 제거
    for (x, y) in lines:
        for (x1, y1, x2, y2) in rectangle:
            if x > x1 and x < x2 and y > y1 and y < y2:
                pointsInRectangle.append((x, y))
    for (x, y) in pointsInRectangle:
        lines.pop((x, y), None)
        
    # 사각형을 가로지르는 선분들 제거, 가로나 세로의 길이가 1인 사각형들에서만 발생함
    for (x1, y1, x2, y2) in rectangle:
        if x2 - x1 == 1:
            for i in range(y1+1, y2):
                if (x2, i) in lines[(x1, i)]:
                    lines[(x1, i)].remove((x2, i))
                if (x1, i) in lines[(x2, i)]:
                    lines[(x2, i)].remove((x1, i))
        if y2 - y1 == 1:
            for i in range(x1+1, x2):
                if (i, y2) in lines[(i, y1)]:
                    lines[(i, y1)].remove((i, y2))
                if (i, y1) in lines[(i, y2)]:
                    lines[(i, y2)].remove((i, y1))
            
        
    q = deque()
    q.append([characterX, characterY, 0])
    
    while q:
        data = q.popleft()
        cx = data[0]
        cy = data[1]
        cnt = data[2]
        
        if (cx, cy) not in lines:
            continue
        if cx == itemX and cy == itemY:
            answer = cnt
            break
        
        nexts = lines[(cx, cy)]
        lines.pop((cx, cy), None)
        for (nx, ny) in nexts:
            q.append([nx, ny, cnt + 1])
    return answer

 

롯데 이노베이트 코테가 오늘 마무리 되었다. 이런 탐색 문제는 안나와서 좀 아쉬웠다. 그래도 지금까지 열심히 달려와서 그런가 그렇게 어렵지 않게 풀 수 있었던 것 같다.

 

추천글

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

프로그래머스