[프로그래머스] 아이템 줍기 파이썬

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/87694

코딩테스트 연습 - 11주차

 

내풀이의 핵심은 사각형을 확대 해보는 것이다.

 

우선 두가지 배열을 사용했다.

사각형의 올라가있는 공간을 표시한 2차원 배열 board

사각형이 올라간 공간이 테두리인지 사각형의 안쪽인지 표시한 3차원 배열 in_out_board

      사각형은 최대 4개 이므로 해당 점이 어떤 사각형에서 테두리인지 안쪽인지 표시

      in_out_board[x][y][사각형번호] = 테두리 여부

 

우선 board에 사각형을 그리자.

나는 x,y 좌표를 반대로 했다.

그리고 그림을 위아래 뒤집어서 표현한 것이다.

 

나는 사각형을 확대한다 했다.

그래서 a점에서 b점을 가는데 한칸을 더 사용한다.

또한 시작위치, 아이템의 위치도 조정이 되니 주의하자.

 

뒤에서 설명하겠지만 나는 DFS로 출발점에서 아이템의 위치까지 탐색을 한다.

나는 탐색할 때 다음점이 1이상의 값이라면 사각형의 점이라고 보고 이동을 수행한다. 근데 위 그림의 초록색 점에서 다음점을 찾을 때 애매해진다.

 

만약 확대를 하지않고 그대로 초록색 원 근처를 board에 표현한다면 모양은 대략 아래일것이다.

  0 0 0 0 0

  0 1 1 1 0

  0 0 5 1 0

  0 0 1 0 0

숫자 5가 있는 곳이 초록색 점의 위치다. 그림대로라면 오른쪽으로 이동해야하지만 board만 본다면 위로도 가능한 것으로 나타난다. 그래서 확실하게 표시를 하기 위해서 확대해서 표시한 것이다.

확대해서 표시하면 아래와 같다.

  0 0 0 0 0 0 0

  0 1 1 1 1 1 0

  0 0 0 0 0 1 0

  0 0 0 5 1 1 0

  0 0 0 1 0 0 0

 

확대해서 표시한다면 더 명확하게 테두리가 보여 길이 보인다.

 

board에 사각형을 그리면서 테두리도 확인하자.

일단 입력받은 순서대로 사각형의 번호를 부여했다.

그래서 현재 좌표가 테두리의 안쪽이라면 -1, 테두리라면 1을 넣어줬다.

in_out_board[x][y][사각형번호] = 테두리 여부

 

다음 이제 DFS로 탐색한다.

4방향을 확인해본다.

이때 탐색 조건은 다음 점이 1이상의 값, 즉 사각형의 좌표여야하고,

해당 점이 사각형의 테두리어야한다. 즉 in_out_board의 해당 좌표 값에 -1이 없어야한다.

그리고 방문표시도 해주자.

 

탐색하다 최종점에 도착하면 답을 갱신해주자.

이때 사각형을 확대해서 그렸으므로 두칸 이동한게 한칸이 되므로 주의하자.

 

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


def solution(rectangle, characterX, characterY, itemX, itemY):
    global board, in_out_board, visited, answer
    answer = 9876543210
    in_out_board = [[[0] * 4 for _ in range(105)] for _ in range(105)]
    board = [[0] * 105 for _ in range(105)]
    visited = [[False]*105 for _ in range(105)]

    set_board(rectangle)

    visited[characterY*2][characterX*2] = True
    for d in range(4):
        nx = characterY*2 + dx[d]
        ny = characterX*2 + dy[d]
        if board[nx][ny] > 0 and -1 not in in_out_board[nx][ny]:
            dfs(nx, ny, 1, itemY*2, itemX*2)
    return answer


def dfs(x, y, cnt, tx, ty):
    global answer,visited
    if (x, y) == (tx, ty):
        answer = min(cnt//2, answer)
        visited[tx][ty] = False
        return

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if board[nx][ny] > 0 and -1 not in in_out_board[nx][ny] and not visited[nx][ny]:
            visited[nx][ny] = True
            dfs(nx, ny, cnt + 1, tx, ty)

def set_board(rectangle):
    global board, in_out_board
    num = 0
    for sy, sx, ey, ex in rectangle:
        for x in range(sx*2, ex*2+1):
            for y in range(sy*2, ey*2+1):
                board[x][y] += 1
                if x in (sx*2, ex*2) or y in (sy*2, ey*2):
                    in_out_board[x][y][num] = 1
                else:
                    in_out_board[x][y][num] = -1
        num += 1