2146번 - 다리 만들기
dfs로 섬 라벨링 한 후 bfs로 다리 건설하도록 짰습니다.
반례 찾아주시면 감사하겠습니다.
5
1 0 0 0 1
0 0 0 0 0
1 1 0 0 1
이 케이스에서 2가 나와야 하는데, 3이 출력됩니다.
힌트를 드리자면, 지금 코드에서는 윗줄의 두 섬이 아랫줄의 두 섬보다 먼저 큐에 들어갔기 때문에, 윗줄의 두 섬이 서로를 향해 다가가다가 상대편을 발견하는 시간이 아랫줄의 두 섬이 서로를 발견하는 시간보다 조금 더 빠릅니다.
답변 감사합니다!
@djm03178 님 반례 덕분에 저도 해결 했습니다
@djm03178
와 감사합니다... 감사합니다.. 감사합니다.. 덕분에 하루종일 머리 싸맸는데 드디어 왜 80%에서 틀리나 알 수 있었습니다... 이런 케이스가 있었네요.. 덕분에 풀었슴다 !!
@djm03178 감사합니다
댓글을 작성하려면 로그인해야 합니다.
nj0034 6년 전
dfs로 섬 라벨링 한 후 bfs로 다리 건설하도록 짰습니다.
반례 찾아주시면 감사하겠습니다.