[프로그래머스] 아이템 줍기 (level3, python)

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

프로그래머스

아이디어

최단거리여서 BFS 로 풀었다. 

1. maps 만들기
2. 최단거리 구하기

풀이는 어렵지 않았지만, 풀기 위해서는 위 두 가지를 구현하면서 반례를 잘 찾아야 했다.

 

maps 만들기

처음에는 rectangle의 정보를 1:1 비율로 맵에 넣어주었는데, 이 때문에 최단거리를 찾을 때 문제가 있었다.

 

표시된 부분이

11

11

이런식으로 붙어서 표현됐기 때문에 ㄷ모양으로 움직이지 않고, | 이렇게 직선으로 경유해버렸기 때문이다.

빨간선 참고

 

그래서 비율을 2배로 변경해서 옮겨주었다. 

 

우선 좌표 값을 2배로 변경해주었다.

    rectangle = [[x1 * 2, y1 * 2, x2 * 2, y2 * 2] for x1, y1, x2, y2 in rectangle]

 

그 후 각 좌표를 돌면서 해당하는 가장자리를 1로 표시해주었다.

    for x1, y1, x2, y2 in rectangle:
        for x in range(x1, x2 + 1):
            maps[x][y1] = 1
            maps[x][y2] = 1
        for y in range(y1, y2 + 1):
            maps[x1][y] = 1
            maps[x2][y] = 1

 

마지막으로 maps를 돌면서 가장자리를 제외한 rectangle 범위 내에 1이 있으면 0으로 변경해준다.

    for x1, y1, x2, y2 in rectangle:
        for i in range(MAX):
            for j in range(MAX):
                if maps[i][j] == 1 and x1 < i < x2 and y1 < j < y2:
                    maps[i][j] = 0

 

이러면 maps이 완성된다.

해당 로직으로 maps를 만들면 위와 같은 예제에서 가운데에 있는 사각형 부분은 1로 남게 된다. 하지만 좌표를 *2 했으므로 가운데 ㅁ 부분과 가장자리 선 사이에 공간이 생기므로, bfs를 사용해도 가운데 부분으로 이동할 수 있는 방법이 없기 때문에 그냥 예외처리를 해주지 않았다.

빨간색 부분이 1, 파란 부분이 0이다.

최단거리 구하기

최단거리를 구할 때도 마찬가지로 아이템과 캐릭터 좌표는 *2 해준다.

이동 거리를 return 할 때는 2배의 맵을 이동했으므로 2로 나눈 값을 리턴하면 된다.

이 점을 제외하면 다른 bfs 로직과 특별히 다른 점은 없다!

    queue = deque([(characterX*2, characterY*2, 0)])
    
    while queue:
        x, y, c = queue.popleft()
        
        if x == itemX*2 and y == itemY*2: return c//2
        
        for dx, dy in dv:
            nx = x + dx
            ny = y + dy
            
            if nx < 0 or nx >= MAX or ny < 0 or ny >= MAX or maps[nx][ny] == 0 or visited[nx][ny] == 1:
                continue
            visited[nx][ny] = 1
            queue.append((nx, ny, c + 1))
    
    return -1

 

전체 코드

from collections import deque

def solution(rectangle, characterX, characterY, itemX, itemY):
    dv = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    MAX = 101
    maps = [[0 for _ in range(MAX)] for _ in range(MAX)]
    visited = [[0 for _ in range(MAX)] for _ in range(MAX)]
    
    rectangle = [[x1 * 2, y1 * 2, x2 * 2, y2 * 2] for x1, y1, x2, y2 in rectangle]
    
    for x1, y1, x2, y2 in rectangle:
        for x in range(x1, x2 + 1):
            maps[x][y1] = 1
            maps[x][y2] = 1
        for y in range(y1, y2 + 1):
            maps[x1][y] = 1
            maps[x2][y] = 1

    for x1, y1, x2, y2 in rectangle:
        for i in range(MAX):
            for j in range(MAX):
                if maps[i][j] == 1 and x1 < i < x2 and y1 < j < y2:
                    maps[i][j] = 0

    queue = deque([(characterX*2, characterY*2, 0)])
    
    while queue:
        x, y, c = queue.popleft()
        
        if x == itemX*2 and y == itemY*2: return c//2
        
        for dx, dy in dv:
            nx = x + dx
            ny = y + dy
            
            if nx < 0 or nx >= MAX or ny < 0 or ny >= MAX or maps[nx][ny] == 0 or visited[nx][ny] == 1:
                continue
            visited[nx][ny] = 1
            queue.append((nx, ny, c + 1))
    
    return -1

 

MAX가 101인 이유는 모든 좌표의 범위가 1부터 50이기 때문이다.

 

후기

탐색 문제를 풀기 전에 선인지 블럭인지 확인을 하고 풀어야한다는 것을 알게되었다.. 처음에 비율 그대로 정직하게 구현했다가 30분동안 헤맸다.. 

다음부터는 반례를 제대로 찾고 풀어야겠다,..🥹