[프로그래머스] lv3 아이템 줍기 / 파이썬 [해설과 다른 풀이], 고득점kit

문제 설명 ==> 아이템 줍기

까다로운 문제라고 생각한다. 깊이/너비 우선 탐색 문제이고 상하좌우로 이동하는 것은 다른 문제와 같지만 테두리만 움직여야 한다는 조건이 있다.

 

주의점!

• 테두리만 움직여야 한다.
• ㄷ자 구조의 한계 때문에 최소거리가 오작동 할 수 있다.

 

ㄷ자 구조란?

화살표는 (0, 0)을 의미

사진 속 점선 처럼 밀접해 있는 구조를 의미한다. 그래서 많은 해설에서 ㄷ자 구조의 한계를 극복하기 위해 좌표값을 2배로 해주라 한다.

좌표값에 2배 적용

ㄷ자 구조의 한계를 극복했기에 상하좌우대각선에서 하나라도 공백이 발생하게 된다. 그 공백이 하나라도 존재하면 그 위치는 테두리라 말할 수 있다.

사진 속 (1, 0)은 상하좌우 중 공백이 (2, 2)는 대각선에서 공백이 발생한다. 그래서 테두리라 말할 수 있다.

나는 위의 방법으로 구글 속 해설과 조금 다른 방법으로 풀었다.

문제해결 아이디어

• 그래프 전체를 -1로 칠하고 주어지는 모든 사각형의 내부와 테두리를 0으로 칠한다.
• 새로운 위치의 주변 8군데를 탐색해 공백이 나오면 테두리라 판단 아니면 사각형의 내부라 판단

 

from collections import deque
def bfs(characterX, characterY, itemX, itemY, graph):
    q = deque()
    q.append([characterX*2, characterY*2])
    dx = [ 0, 0, -1, 1, -1, 1, 1, -1 ] # 앞의 4개는 상하좌우 뒤 4개는 대각선
    dy = [ -1, 1, 0, 0, -1, -1, 1, 1 ]
    visited = [ [0] * 102 for _ in range(102) ]
    while q:
        x, y = q.popleft()
        if x == itemX * 2 and y == itemY * 2:
            return visited[x][y] // 2
        for i in range(4): # 상하좌우를 돌면서 새로운 위치를 찾는다
            nx = x + dx[i]
            ny = y + dy[i]
            tmp_cnt = 0 # 공백의 개수를 찾을 임시카운트
            for i in range(8): # 새로운 위치가 주변에 공백을 가지고 있는지 판단
                tnx = x + dx[i]
                tny = y + dy[i]
                if graph[tnx][tny] == -1:
                    tmp_cnt += 1
            if tmp_cnt != 0: # 임시카운트가 0이 아니면 즉, 하나라도 공백이 존재하면 테두리라 판단 
                if graph[nx][ny] == 0 and visited[nx][ny] == 0:
                    visited[nx][ny] = visited[x][y] + 1
                    q.append([nx, ny])
            else:
                continue # 상하좌우대각선 모두 0이면 사각형의 내부이므로 테두리가 아니여서 패스

def solution(rectangle, characterX, characterY, itemX, itemY):
    # 1~50 이하의 자연수가 주어진다 했으니 x2해서 102를 곱해준다. [0,0]은 사용x
    graph = [ [-1] * 102 for _ in range(102) ] # 그래프 전체 -1로 채워줌
    for r in rectangle:
        x1, y1, x2, y2 = map(lambda x : x*2, r)
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                if x1 <= i <= x2 and y1 <= j <= y2: # 사각형 내부와 테두리 모두 0
                    graph[i][j] = 0
    return bfs(characterX, characterY, itemX, itemY, graph)

 

성공 사진

 

내부는 0, 테두리는 1로 칠하는 다른 해설보다 이 방법이 조금 더 직관적이지 않은가? 3중 반복문이지만 반복의 횟수가 4번 8번으로 고정되어 있고 입력값도 크지 않아 충분히 돌릴 수 있다.