링크
아이템 줍기
난이도
문제요약
- 여러개의 직사각형을 겹쳤을때 외곽의 경로를 통해 출발지에서 목적지로 가는 최소거리를 구하시오
접근
-
- 각 사각형의 외곽을 구하여 경로를 찾는다.
- 여기서 중요한건 행렬로 표현된 도형에서부터 외곽을 찾아서 경로로 만들어야한다.
- 단순하게 행렬로 표현하면 가로 또는 세로가 1크기의 사각형을 그리게되면 외곽을 찾기 어려워서 추가적인 계산이 필요하다.
[1,1,2,8]이런 사각형이 있을때 행열로 그려서 외곽을 찾아보자
- 해결법 행렬로 표현할때 두배의 크기로 표현하자!
간단 알고리즘
- 기본 board를 만든다.
- 크기는 각 사각형의 최대 크기의 두배로 만들어준다.
- [좌측하단x,y, 우측상단x,y]라고 표현되어있지만 이를 행렬로 표현할때 x와 y의 관계를 주의하자
- x는 가로정보를 y는 세로정보를 가진다, 행렬로 표현시 [세로정보][가로정보]순으로 가기때문에 해당 부분을 잘 인지해야한다.
board = [[0]*가로*2 for _ in range(세로*2)]로 보드를 만들어준다.- 만들어진 행렬은 가로축을 기준으로 뒤짚어진 모양으로 만들것이다.
- 각 사각형을 행렬로 그리기
- 사각형의 요소를 r1,r2,r3,r4라고 할때
- 가로인 y는 r1~r3까지, 세로인 x는 r2~r4까지로 2중 반복문을 통해 보드의 해당 좌표를 1로 채운다.
- 이를 모든 rectangle을 돌면서 적용
- 이때에도 각 r1~r4는 곱하기 2를 해줘야한다.
- 외곽 찾기 함수
- 외곽 = 경로 이며 이는 간단한 조건문으로 찾을수있다.
- 현재 좌표가 x,y일때
board[x][y]==1이고
- x,y기준 좌,우,상,하,좌상,우상,좌하,우하의 영역이 0이 하나라도 있으면 외곽이다.
- 이를 만들어진 board에 모든 좌표에 적용, route라는 새로운 보드를 추출
- bfs로 외곽에서 경로찾기
- 시작xy,도착xy가 주어지고 경로가 있으니 bfs를 적용
- 주의
- 여기서 xy는 행렬에서 표현할때 yx로 표현해야하도록 만들어져있으므로 bfs를 위해 y,x로 넣어줘야 한다.
- 나온 최소 경로의 길이를 나누기 2를 해준다.
후기
- 외곽을 찾기위해 어떻게 해야할지 고민이 오래 걸렸다.
- 처음 행렬로 표현하고 계산했을때 정답보다 낮은 경로가 나와서 당황했다.
- 이는 원래라면 못가는 경로를 행렬로 하면서 구분이 안되는 경로로 나와서 생긴 문제
- 이후 두배의 크기로 만들어 구분을 확실히 하는 것 으로 해결
- x와 y가 행렬에서 뒤바뀌는 것을 자주 헷갈려서 더 오래걸린거 같다.