BOJ 1385 - 벌집
개인적으로 까다로웠던 구현 + 최단거리 문제
굳이 최단거리 알고리즘을 안쓰고 좌표변환을 잘해서 그리디하게 구해도 되는듯하다.
인덱스를 어떻게 잡는지 살펴보자.
번호 에 대해
같은 인덱스를 에 구할 수 있게 해두자.
벌집 둘레의 크기는 처럼 이후에 씩 늘어나는 모습을 보인다.
이걸 열심히 활용해서 저 배열을 만들어주는데, 인덱스를 어떻게 관리하는지 보자.
벌집의 그림을 보자.
이라고 두고
$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
적당한 중앙에 을 찍었다. 이런식으로 모두 카르테시안 좌표로 표현해주고,
에 대해 가지 방향에 대해서만 잘 BFS를 돌려주면 된다.
Comments