nj0034   2년 전

dfs로 섬 라벨링 한 후 bfs로 다리 건설하도록 짰습니다.

반례 찾아주시면 감사하겠습니다.


djm03178   2년 전

5

1 0 0 0 1

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

1 1 0 0 1

이 케이스에서 2가 나와야 하는데, 3이 출력됩니다.

힌트를 드리자면, 지금 코드에서는 윗줄의 두 섬이 아랫줄의 두 섬보다 먼저 큐에 들어갔기 때문에, 윗줄의 두 섬이 서로를 향해 다가가다가 상대편을 발견하는 시간이 아랫줄의 두 섬이 서로를 발견하는 시간보다 조금 더 빠릅니다.

nj0034   2년 전

답변 감사합니다!

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