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

아이템 줍기

문제 설명

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.

즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.

다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.

한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

제한사항

• rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
• rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
• 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
• 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
• 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
• charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
• 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• itemX, itemY는 1 이상 50 이하인 자연수입니다.
• 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.
• 전체 배점의 50%는 직사각형이 1개인 경우입니다.
• 전체 배점의 25%는 직사각형이 2개인 경우입니다.
• 전체 배점의 25%는 직사각형이 3개 또는 4개인 경우입니다.

입출력 예

rectangle	characterX	characterY	itemX	itemY	result
[[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]]	1	3	7	8	17
[[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]]	9	7	6	1	11
[[1,1,5,7]]	1	1	4	7	9
[[2,1,7,5],[6,4,10,10]]	3	1	7	10	15
[[2,2,5,5],[1,3,6,4],[3,1,4,6]]	1	4	6	3	10

입출력 예 설명

입출력 예 #1

캐릭터 위치는 (1, 3)이며, 아이템 위치는 (7, 8)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

입출력 예 #2

캐릭터 위치는 (9, 7)이며, 아이템 위치는 (6, 1)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

입출력 예 #3

캐릭터 위치는 (1, 1)이며, 아이템 위치는 (4, 7)입니다. 위 그림과 같이 굵은 선을 따라 이동하는 경로가 가장 짧습니다.

입출력 예 #4, #5

설명 생략

문제 풀이

from collections import deque


# def solution(rectangle, characterX, characterY, itemX, itemY):
#     answer = 0
#     mapp = [[0 for _ in range(13)] for _ in range(13)]
#     renew_mapp = [[0 for _ in range(13)] for _ in range(13)]
#     visitied = [[0 for _ in range(13)] for _ in range(13)]
#     for i in range(len(rectangle)):
#         # print(rectangle[i])
#         for j in range(rectangle[i][0], rectangle[i][2] + 1):
#             for k in range(rectangle[i][1], rectangle[i][3] + 1):
#                 if mapp[j][k] == 0:
#                     mapp[j][k] = 1
#
#     def bfs(y, x):
#         que = deque()
#         que.append((y, x))
#         xy_list = []
#         dx = [-1, 1, 0, 0, 1, -1, -1, 1]
#         dy = [0, 0, -1, 1, 1, -1, 1, -1]
#
#         while que:
#             y1, x1 = que.popleft()
#             visitied[y1][x1] = 1
#             for i in range(8):
#                 x2 = x1 + dx[i]
#                 y2 = y1 + dy[i]
#                 if 0 <= x2 < len(mapp[0]) and 0 <= y2 < len(mapp):
#                     if mapp[y2][x2] == 1 and visitied[y2][x2] == 0:
#                         que.append((y2, x2))
#                     if mapp[y2][x2] == 0 and mapp[y1][x1] == 1:
#                         renew_mapp[y1][x1] = 1
#
#     for i in range(len(mapp)):
#         for j in range(len(mapp[0])):
#             if mapp[i][j] == 1:
#                 bfs(i, j)
#
#     def find_item(y, x, cnt):
#         answer_list = []
#         q = deque()
#         q.append((y, x, cnt))
#         dx = [-1, 1, 0, 0]
#         dy = [0, 0, -1, 1]
#         while q:
#             y1, x1, cntt = q.popleft()
#             new_visited[y1][x1] = 1
#
#             for i in range(4):
#                 y2 = y1 + dy[i]
#                 x2 = x1 + dx[i]
#                 if renew_mapp[y2][x2] == 2:
#                     answer_list.append(cntt)
#                 if 0 <= x2 < len(renew_mapp[0]) and 0 <= y2 < len(renew_mapp):
#                     if renew_mapp[y2][x2] == 1 and new_visited[y2][x2] == 0:
#                         q.append((y2, x2, cntt + 1))
#         return answer_list
#
#     renew_mapp[itemX][itemY] = 2
#     renew_mapp[characterX][characterY] = 3
#     print(renew_mapp)
#
#     new_visited = [[0 for _ in range(13)] for _ in range(13)]
#     a = find_item(characterX, characterY, 0)
#     print(new_visited)
#     print(a)
#     return answer
#
from collections import deque

def solution(rectangle, cx, cy, ix, iy):
    answer = 0
    maxX = 0
    maxY = 0

    for x,y,x2,y2 in rectangle:
        maxX = max(x2 * 2,maxX)
        maxY = max(y2 * 2,maxY)

    graph = [[0] * (maxX + 2) for _ in range(maxY + 2)]

    #1로 안쪽 다 칠하고
    for x,y,x2,y2 in rectangle:
        for i in range((x * 2),(x2 * 2) + 1):
            for j in range((y * 2),(y2 * 2) + 1):
                graph[j][i] = 1

    #전체 돌면서 주위 8개중에 하나가 0이면서 자기 자신이 1이면 2로 바꿈 테두리 경로
    for y in range(1,maxY + 1):
        for x in range(1,maxX + 1):
            for i in range(3):
                for j in range(3):
                    if graph[y + i - 1][x + j - 1] == 0 and graph[y][x] == 1:
                        graph[y][x] = 2
                        break

    dx = [1,0, 0, -1]
    dy = [0,1, -1, 0]
    queue = deque([(cx * 2,cy * 2,0)])
    ix *= 2
    iy *= 2
    while queue:
        x, y,length = queue.popleft()
        graph[y][x] = 1
        if x == ix and y == iy:
            answer = (length // 2)
            break

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if graph[ny][nx] == 2:
                queue.append((nx,ny,length + 1))


    return answer

문제 해석

꽤 애를 먹었던 문제입니다. 실제로 알고리즘 접근법을 바탕으로 문제를 풀다가 중간에 좌표값을 넣는 부분에서 꼬였는지 답을 도출하지 못하였습니다.

문제 접근은 다음과 같습니다.

기본적으로 미로탐색이나 BFS로 탐색을 진행할시 구분된 숫자를 바탕으로 좌표탐색을 진행합니다. 이때 그러면 character좌표와 item 좌표가 주어졌지며 탐색을 진행 할때 위에 보이는 이미지 처럼 곂치는 부분을 탐색하며 돌아갈 수 있습니다.

이를 해결하고자 주어진 사각형 좌표값에서 안에 있는 모든 부분을 1로 표기하며 색을 칠합니다.

이후 bfs로 True(색칠된 부분)부분 탐색을 진행합니다.

기존 4방탐색이 아닌 8방 탐색으로 0이 탐색되면 이를 표기하고 0이 탐색되지 않으면 False구간으로 바꿔줍니다.

위 이미지와 같이 안에 있는 값들을 전부 0으로 바꾸게 되면 이때 캐릭터 좌표를 찾아 탐색을 진행합니다.

이때 하나의 문제점이 생깁니다.

파란색 좌표에서 빨간색 좌표를 탐색할 때 초록선처럼 탐색을 진행해야 하지만, 해당 좌표를 구할때 직선으로 탐색을 하는 문제점이 생깁니다.

이를 해결하기 위해 모든 좌표값을 2배 증가시킵니다.

이 처럼 좌표 값을 2배 증가시키면 탐색을 하는 길이도 2배 증가하게 됩니다.

이후 해당 탐색 길이를 2로 나누면 답이 도출됩니다.

기존 문제를 풀었을 때 2배를 곱할 생각을 하지 못하여 문제 푸는데 실패를 하였습니다. 다른 사람의 코드를 참고하여 문제를 풀었으며, 해당 문제를 풀면서 BFS의 개념과 사고를 확장시킬 수 있었습니다.