4-H(#2234, 성곽)문제 DFS대신 BFS 사... - Inflearn

10-Week C++ Coding Test | Algorithm Coding Test

4-H

4-H(#2234, 성곽)문제 DFS대신 BFS 사용

Written on

안녕하세요 선생님.

#2234 문제에 대해서 Connected Component개념으로 DFS를 소개해주셔서 문제풀이를 이해하는데 수월했습니다.

다만, 처음 문제를 저 혼자 풀 때,

각 방 칸의 크기가 1이고, 방 칸의 개수에 따라 방 넓이가 결정되므로

가중치가 동일하니 BFS로도 풀 수 있지 않을까라고 생각되어 아래와 같이 풀어봤습니다.

각 방을 탐색할때마다 queue를 생성하고 queue pop을 할 때마다 방 칸의 개수를 cnt++라는 변수에 담고,

탐색을 더이상 진행할 수 없을 때 방 칸의 개수값 cnt를 return하도록 하여 탐색했는데요.

문제에서 주어진 예제 입력1은 통과했지만 채점에서도 어떠한 반례에 걸려 fail이 발생한 것 같습니다.

BFS 탐색 코드에 어떠한 문제점이 있는지 피드백 주시면 감사드리겠습니다...

감사합니다.

c++코딩-테스트

Answer 1

Instructor

안녕하세요 기태님 ㅎㅎ

해당 코드를 여러번 시도해고 제가 생각한 반례들을 모두 다 통과하네요

제가 봤을 때 틀린점이 없는 것 같은데.. 이상하네요

도움을 못드려 죄송합니다.

Questioner

선생님, 오랜시간 제 궁금증을 해결해주시고자 노력해주셔서 너무 감사드립니다.

일단 이 문제는 Connected Component -> DFS로 대응이란 인사이트를 명확하게 인지하되,

추후에 제가 시간이 남으면 BFS로 인한 반례가 생기는지 천천히 되짚어보도록 하겠습니다.

본의아니게, 수고를 들이게 하여 죄송하고 감사합니다.