프로그래머스 87694 아이템 줍기 파이썬 풀이

난이도 : Lv. 3

풀이일 : 2412183

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

프로그래머스

---

문제

---

문제 상황

• 처음 풀이 도중 문제가 발생했다. 위 그림과 같은 상황에서 x, y (3, 5)에서 (4, 5)로 이동해야 하는데, (3, 6)으로 움직이게 되어 맵을 가로 세로 모두 두 배씩 확장했다.

---

풀이 코드

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    
    land = [[False] * 102 for _ in range(102)]
    visited = [[False] * 102 for _ in range(102)]
    di, dj = [-1, 1, 0, 0, -1, 1, -1, 1], [0, 0, -1, 1, -1, -1, 1, 1]
    
    for y1, x1, y2, x2 in rectangle:
        for x in range(x1 * 2, x2 * 2 + 1):
            for y in range(y1 * 2, y2 * 2 + 1):
                land[x][y] = True
    
    queue = deque()
    queue.append((characterY * 2, characterX * 2, 1)) # i, j 좌표, 이동거리
    visited[characterY * 2][characterX * 2] = True
    
    while queue:
        i, j, v = queue.popleft()
        for k in range(4):
            ni, nj = i + di[k], j + dj[k]
            if 0 <= ni < 102 and 0 <= nj < 102 and land[ni][nj]:
                for l in range(8): # 외곽선 여부 검사
                    ti, tj = ni + di[l], nj + dj[l]
                    if 0 <= ti < 102 and 0 <= tj < 102 and not land[ti][tj]:
                        if not visited[ni][nj]:
                            queue.append((ni, nj, v + 1))
                            visited[ni][nj] = True
                            if ni == itemY * 2 and nj == itemX * 2: # 아이템
                                return v // 2

    return answer

---

실행 결과

---

느낀점

• 풀기는 풀었는데 마음에 들지 않아서 어디 수정할 데 없나 노려보는 중

---

개선 코드

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    answer = 0
    
    land = [[-1] * 102 for _ in range(102)]
    visited = [[False] * 102 for _ in range(102)]
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for y1, x1, y2, x2 in rectangle: # 외곽선 기록
        for x in range(x1 * 2, x2 * 2 + 1):
            for y in range(y1 * 2, y2 * 2 + 1):
                if x1 * 2 < x < x2 * 2 and y1 * 2 < y < y2 * 2:
                    land[x][y] = 0
                elif land[x][y]:
                    land[x][y] = 1
    
    queue = deque()
    queue.append((characterY * 2, characterX * 2, 1)) # i, j 좌표, 이동거리
    land[characterY * 2][characterX * 2] = 0
    
    while queue:
        i, j, v = queue.popleft()
        
        for di, dj in directions:
            ni, nj = i + di, j + dj
            if 0 <= ni < 102 and 0 <= nj < 102 and land[ni][nj] > 0:
                queue.append((ni, nj, v + 1))
                land[ni][nj] = 0
                if ni == itemY * 2 and nj == itemX * 2: # 아이템 발견
                    return v // 2          

    return answer

---

실행 결과