날짜: 2022년 5월 3일 오후 5:57
오답: o
코드
Algorithm/81304.py at main · Junroot/Algorithm
풀이
- 처음에 문제를 이해하는데 시간이 걸렸다. 똑같은 함정 방에 돌아가면 모든 간선의 방향이 원래대로 돌아가는 문제로 이해했다.
- 현재 방문했던 함정방으로 비트마스크로 표현하는 것까지는 쉽게 접근했다. 하지만 n의 크기가 1000이여서 int 범위 밖의 비트마스크 표현에 문제가 있었다. 이부분은 함정방이 10개이하이므로 좌표 압축을 통해 해결했다.
- 현재 노드와 이동할 노드에 함정 활성화가 모두 켜저있거나 모두 꺼져있으면 정방향, 하나만 켜져있으면 역방향으로 이동하도록 구현했다. 최소 경로는 다익스트라를 통해 구할 수 있다.