zxzimin   3년 전

예를 들어 5개의 섬이 있다고 하면, 각각의 섬에서 시작해서 다른 섬까지 놓을 수 있는 최소 길이의 다리 길이를 구합니다.

그렇다면 총 5개의 다리 길이가 구해질 것이고, 그 중에서 최소 길이를 결과로 출력하도록 했습니다.

우선 각각의 섬을 감싸고(?) 있는 테두리 부분의 거리를 1로 설정한 뒤, bfs을 돌려서 다른 섬(자기 자신이 아닌)을 발견하면 해당 길이가

그 섬에서 구할 수 있는 최소 길이의 다리임이 보장된다고 생각했습니다. (큐에 들어가는 순서에 따라)

이 경우 테두리 부분을 구하는데 bfs 1번, 다른 섬을 찾아가는데 bfs 1번해서 총 2번의 bfs을 사용했습니다.

그런데 테스트케이스나, 반례 등은 통과하는 거 같은데 64퍼에서 틀렸습니다가 나오네요 ㅠㅠ 어디가 문제일까요?

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