문제 설명
캐릭터는 다음 다각형 지형에서 아이템을 집기 위해 이동을 시도합니다.
지형은 측면이 x축과 y축에 평행한 겹치는 사각형으로 표현되며 캐릭터는 이 다각형의 둘레(두꺼운 선)를 따라 이동합니다.
겹치는 사각형 뒤 중간에 공백이 있으면 다각형의 가장 바깥쪽 경계가 캐릭터의 이동 경로가 됩니다.
그러나 두 개의 사각형은 동일한 x 또는 y 좌표를 갖지 않습니다.
즉, 위의 그림과 같이 서로 다른 두 개의 직사각형이 꼭지점에서 교차하거나 모서리가 겹치는 등의 현상이 없습니다.
어떤 경우에도 아래 이미지와 같이 지형을 두 개 이상의 조각으로 나누어서는 안 됩니다.
또한 하나의 사각형이 다른 사각형 안에 완전히 포함되는 경우도 없습니다.
지형, 초기 문자 위치 characterX, characterY, 항목 위치 itemX, itemY를 나타내는 사각형을 포함하는 2D 배열 사각형이 솔루션 함수에 대한 인수로 제공될 때 항목을 집기 위해 캐릭터가 이동해야 하는 최단 거리를 반환합니다.
해결 기능을 완료하십시오.
한계
- 사각형의 세로(행) 길이는 1보다 크거나 같고 4보다 작거나 같습니다.
- 사각형의 요소는 각 사각형의 (왼쪽 아래 x, 왼쪽 아래 y, 오른쪽 위 x, 오른쪽 위 y) 좌표입니다.
- 사각형을 나타내는 모든 좌표 값은 1에서 50 사이의 자연수입니다.
- 두 개의 직사각형이 동일한 x 또는 y 좌표를 갖지 않습니다.
- 질문에 주어진 조건을 만족하는 사각형만 입력으로 제공됩니다.
- 사각형을 나타내는 모든 좌표 값은 1에서 50 사이의 자연수입니다.
- charcterX 및 charcterY는 1보다 크거나 같고 50보다 작거나 같은 자연수입니다.
- 지형을 나타내는 폴리곤 경계의 한 점이 주어집니다.
- 지형을 나타내는 폴리곤 경계의 한 점이 주어집니다.
- itemX와 itemY는 1에서 50 사이의 자연수입니다.
- 지형을 나타내는 폴리곤 경계의 한 점이 주어집니다.
- 지형을 나타내는 폴리곤 경계의 한 점이 주어집니다.
- 캐릭터와 아이템은 동일한 초기 위치를 가지지 않습니다.
- 직사각형 1개가 총점의 50%를 차지합니다.
- 총 점수의 25%는 2개의 사각형에 할당됩니다.
- 총점의 25%는 3개 또는 4개의 직사각형에 대한 것입니다.
IO 예제 직사각형 characterXcharacterYitemXitemYresult
| ((1,1,7,4),(3,2,5,5),(4,3,6,9),(2,6,8,8)) | 하나 | 삼 | 7 | 8 | 17 |
| ((1,1,8,4),(2,2,4,9),(3,6,9,8),(6,3,7,7)) | 9 | 7 | 6 | 하나 | 11 |
| ((1,1,5,7)) | 하나 | 하나 | 4 | 7 | 9 |
| ((2,1,7,5),(6,4,10,10)) | 삼 | 하나 | 7 | 10 | 15 |
| ((2,2,5,5),(1,3,6,4),(3,1,4,6)) | 하나 | 4 | 6 | 삼 | 10 |
I/O 예시 설명
I/O 예제 #1
문자 위치는 (1, 3)이고 항목 위치는 (7, 8)입니다.
위의 이미지와 같이 두꺼운 선을 따라가는 경로가 가장 짧습니다.
I/O 예제 #2
문자 위치는 (9, 7)이고 항목 위치는 (6, 1)입니다.
위의 이미지와 같이 두꺼운 선을 따라가는 경로가 가장 짧습니다.
I/O 예제 #3
문자 위치는 (1, 1)이고 항목 위치는 (4, 7)입니다.
위의 이미지와 같이 두꺼운 선을 따라가는 경로가 가장 짧습니다.
I/O 예제 #4, #5
설명 생략
from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
answer = 0
#상하좌우로 탐색하면서 하기위해 표시
dx=(-1,1,0,0)
dy=(0,0,-1,1)
# 겹치면 안되므로 곱하기 2배 로 시작
board=((0)*101 for _ in range(101))
cX=characterX*2
cY=characterY*2
iX=itemX*2
iY=itemY*2
q=deque()
q.append((cX,cY,0))
# 테두리+안쪽까지 1로 채워줌
for x1,y1,x2,y2 in rectangle:
for i in range(x1*2,x2*2+1):
for j in range(y1*2,y2*2+1):
board(i)(j)=1
# 안쪽을 0으로 초기화
for x1,y1,x2,y2 in rectangle:
for i in range(x1*2+1,x2*2):
for j in range(y1*2+1,y2*2):
board(i)(j)=0
#잘 그려졋는지 확인
for i in range(50):
for j in range(50):
print(board(j)(i),end=" ")
print()
# 2,6 에서 14 ,15 로 가기위해 최소거리를 구해야함 최단거리는 bfs queue 를 사용
count=0
while(q):
x,y,count=q.popleft()
# 아이템을 찾았으면 브레이크 후 곱하기 2배해주었으니 나누기 2
if x==iX and y==iY:
answer=board(x)(y)//2
break
# 상하좌우로 탐색하면서 1을 찾아서 1을 중첩해나아감
for i in range(4):
nx=x+dx(i)
ny=y+dy(i)
if -1<nx<101 and -1<ny<101 and board(nx)(ny)==1:
board(nx)(ny)=board(x)(y)+1
q.append((nx,ny,count+1))
#잘 그려졋는지 확인
for i in range(50):
for j in range(50):
print(board(j)(i),end=" ")
print()
return answer
x1, y1, y1, y2만큼의 좌표로 그래프를 만들어서 1로 표현했는데, 경계선을 넘으니까
경계 내의 모든 숫자는 0으로 초기화됩니다.
이제 bfs를 통해 캐릭터 위치에서 아이템 위치까지의 최단 거리를 위, 아래, 왼쪽, 오른쪽으로 검색할 때,
1을 겹쳐서 검색합니다.