na982   6년 전

100 개의 섬에 최대 연결 다리는 최대 1000개가 있고, 모든 섬에 보석의 합은 최대 14입니다.

섬을 연결하는 다리는 보석의 수를 고려하여 지나가야 합니다.


제가 생각한 솔루션은 아래와 같습니다.

1.  플로이드를 통해서 각 100 * 100 배열에 각 섬끼리 지나갈수 있는 다리의 최대 무게를 갱신시킨다.

2. bfs를 이용해서 보석을 가지고 있는 섬만 탐색하면서 탐색한 섬을 비트마스킹하고, 보석을 줍거나, 안줍거나 두가지 케이스를 고려하여 queue에 넣는다.


아래 코드는 메모리 초과가 나오네요; visited를 다른방식으로 해야 하는건가요?;;;

아니면 코드가 잘못 짜진건가요?


고수님들 도움 부탁 드립니다.

댓글을 작성하려면 로그인해야 합니다.