visited = [[0]*n for _ in range(n)] 두고 풀 경우

1) 한 개의 섬만 색칠하고 for문을 이용해 어떤 섬에서 나머지 섬들중 거리가 가장 빠른 섬을 구하는 bfs를 만들어서 최솟값 구하기

2) 모든 섬을 각각 다른 번호로 색칠하고, 한 번 bfs를 돌릴 때마다 간척사업처럼 1씩 늘리다가 서로 만날 경우 출력하고 종료하기

둘이 메모리 사용량은 비슷하지만 1이 2보다 약 두 배 정도 빠릅니다.

@ hello70825

차이가 나는 이유가 visited 배열 때문인건가요??

네 visited를 줄이고 bfs를 1),2)에 맞게 수정하시면 됩니다.

그리고 파이썬은 재귀가 느린 것으로 알고 있는데 100 x 100이 그렇게 큰 영향을 줄 것 같지는 않을 것 같아요.

@ hello70825

말씀하신 1번의 bfs는 이해했습니다.

말씀하신 100 x 100은 무슨 의미로 말씀하시는 건가요?

아 dfs라고 되어있어서 재귀 함수로 하신 줄 알았는데 그냥 deque로 하셨네요. 저 말은 무시해도 됩니다.

네 처음에 dfs로 풀려고 하다가 bfs로 했거든요

말씀하신 1,2번 중에 2번 방법으로 시행했고, 그래서 3중 visited 배열이 필요했던 것이고요.

답변 정말 감사드립니다.

만약 맵이

1 0 0

0 0 0

0 0 2

이렇게 있다면 다음 턴엔

1 1 0

1 0 2

0 2 2

이렇게 될 것이고

다음턴엔

1 1 1

1 1 2

1 2 2

가 되어 최솟값 3이 나옵니다.

2차원 배열로 충분히 구현할 수 있습니다.

제가  https://www.acmicpc.net/source/12767022 여기에 주석 달아 놨으니 혹시 필요하시면 보는 것도 나쁘지 않을 것 같습니다.

좋은 주말 보내세요

아... 그런식으로 하면 되겠네요

이해했어요 감사합니다!!

@ hello70825

덕분에 방금 해결했습니다^^ 혹시 이와 비슷하게 풀 수 있는 문제가 있다면 추천 부탁드려도 괜찮을까요??

대부분 저런 요구사항은 다익스트라, 플로이드로 만들어져서 비슷한 문제를 본 적이 없네요.

그나마 비슷하다고 말할만한 것이 알고스팟 같아요.

고맙습니다 hello님