BOJ 1385 - 벌집
개인적으로 까다로웠던 구현 + 최단거리 문제
굳이 최단거리 알고리즘을 안쓰고 좌표변환을 잘해서 그리디하게 구해도 되는듯하다.
인덱스를 어떻게 잡는지 살펴보자.
번호 $n$에 대해
$n \leftrightarrow (y, x)$ 같은 인덱스를 $O(1)$에 구할 수 있게 해두자.
벌집 둘레의 크기는 $1,6,12,18,24,\dots$ 처럼 $1$이후에 $6$씩 늘어나는 모습을 보인다.
이걸 열심히 활용해서 저 배열을 만들어주는데, 인덱스를 어떻게 관리하는지 보자.
벌집의 그림을 보자.
$1=(0, 0)$이라고 두고
$2=(-1,0),3=(0, 1),4=(1,1),5=(1,0),6=(0, -1),~~7=(-1, -1)$
처럼 좌표를 생각해보자.
이걸 카르테시안 좌표로 변환해보자.
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 7 2 0 0 0 0 0
0 0 0 0 0 6 1 3 0 0 0 0
0 0 0 0 0 0 5 4 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
적당한 중앙에 $1$을 찍었다. 이런식으로 모두 카르테시안 좌표로 표현해주고,
$dy,dx$에 대해 $6$가지 방향에 대해서만 잘 BFS를 돌려주면 된다.
Comments