BOJ 5529 - 저택
특이한 형태의 최단경로 문제인데, 결론적으로 모든 스위치와 시작점 끝점만 하나의 위치로 보면 된다.
왜냐면 $wlog.$ 가로로 문이 열려있을 때 가로로 이동하는 곳이 스위치가 아니면 세로로 이동할 수 없기 때문이다.
그리고 현재 문이 가로로 열려있는지 세로로 열려있는지만 판단하면 된다.
따라서 $2K$ 개 정도의 정점이 나온다.
이제 간선을 생각해보면 항상 가로나 세로로 인접한 스위치에 대해서만 이어주면 된다.
그러니까 하나의 정점에서 간선은 최대 $4$개가 나온다.
인접한 스위치들을 찾는 것은 자료구조를 쓰거나 이분탐색을 이용해서 $O(\log k)$에 찾아줄 수 있다.
Comments