🐹 아이템 줍기

1. 문제 링크

아이템 줍기

2. 코드

from collections import deque
ground = [[0] * 102 for i in range(102)]
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def solution(rectangle, characterX, characterY, itemX, itemY):
    # 캐릭터, 아이템 좌표 2배로 늘리기
    cx, cy, ix, iy = characterX*2, characterY*2, itemX*2, itemY*2

    # 좌표 직사각형 표시
    for r in rectangle:
        # 좌표를 2배로 늘리기
        x1, y1, x2, y2 = map(lambda x: x*2, r)
        for i in range(x1, x2+1):
            for j in range(y1, y2+1):
                # 직사각형 내부 2로 채우기
                if x1 < i < x2 and y1 < j < y2:
                    ground[i][j] = 2
                # 테두리 1로 채우기
                elif ground[i][j] != 2:
                    ground[i][j] = 1 

    q = deque([(cx, cy)])
    distance = [[1] * 102 for i in range(102)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 범위 밖으로 나갈 시 재탐색
            if nx < 0 or nx > 101 or ny < 0 or ny > 101:
                continue
            # 테두리에 포함되면서 방문 안 했을 경우
            if ground[nx][ny] == 1 and distance[nx][ny] == 1:
                distance[nx][ny] = distance[x][y] + 1
                q.append((nx, ny)) 

    return distance[ix][iy] // 2

• 정확성

  테스트 1 〉	통과 (0.10ms, 10.5MB)
  테스트 2 〉	통과 (0.15ms, 10.5MB)
  테스트 3 〉	통과 (0.15ms, 10.4MB)
  테스트 4 〉	통과 (0.10ms, 10.4MB)
  테스트 5 〉	통과 (0.11ms, 10.4MB)
  테스트 6 〉	통과 (0.10ms, 10.4MB)
  테스트 7 〉	통과 (0.18ms, 10.4MB)
  테스트 8 〉	통과 (0.19ms, 10.6MB)
  테스트 9 〉	통과 (1.12ms, 10.4MB)
  테스트 10 〉	통과 (1.23ms, 10.4MB)
  테스트 11 〉	통과 (1.10ms, 10.4MB)
  테스트 12 〉	통과 (1.18ms, 10.4MB)
  테스트 13 〉	통과 (2.02ms, 10.4MB)
  테스트 14 〉	통과 (0.67ms, 10.6MB)
  테스트 15 〉	통과 (0.45ms, 10.5MB)
  테스트 16 〉	통과 (0.77ms, 10.4MB)
  테스트 17 〉	통과 (0.72ms, 10.5MB)
  테스트 18 〉	통과 (0.78ms, 10.4MB)
  테스트 19 〉	통과 (1.22ms, 10.4MB)
  테스트 20 〉	통과 (1.39ms, 10.4MB)
  테스트 21 〉	통과 (1.43ms, 10.6MB)
  테스트 22 〉	통과 (0.56ms, 10.4MB)
  테스트 23 〉	통과 (1.09ms, 10.5MB)
  테스트 24 〉	통과 (0.73ms, 10.4MB)
  테스트 25 〉	통과 (0.24ms, 10.4MB)
  테스트 26 〉	통과 (0.27ms, 10.4MB)
  테스트 27 〉	통과 (0.29ms, 10.5MB)
  테스트 28 〉	통과 (0.30ms, 10.5MB)
  테스트 29 〉	통과 (0.47ms, 10.5MB)
  테스트 30 〉	통과 (0.57ms, 10.5MB)

3. 해설

bfs를 사용하여 최단 거리를 구하는 문제이다.

좌표상에 테두리를 1, 직사각형 내부를 2로 초기화 해준다. 겹치는 내부도 2로 초기화해준다.

이때 가장 큰 문제는 테두리를 칸 내부에 표시하다 보니 실제 이어져 있지 않은 길이 이어진 것 처럼 보인다.

위와 같은 경우에 파란 칸은 실제 이어지지 않은 줄이지만 bfs로 탐색하다보면 연결된 것으로 간주하여 탐색한다. 따라서 실제 답보다 더 작은 값이 나온다.

이를 해결하기 위해 실제 크기의 2배로 계산을 해준다. 그렇게 되면 해당 경우처럼 길이 붙어있는 경우를 해결할 수 있다.

그 후 bfs를 돌며 테두리를 따라 탐색해준다. 아이템 위치의 distance 값을 리턴할 때 2배로 해주었기 때문에 2로 나누어 리턴한다.