-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
4- c질문
22.09.26 18:43 작성 조회수 355
0
http://boj.kr/f73a62d8306144558a6106909f0c9e2f
i = 1부터 돌려가며 예를 first, second를 초기화해준뒤
예를들어 n = 6
이면 first -> 110011 이면 second -> 001100
두 부분으로 나눈 뒤 각각의 부분에 포함된 정점이 연결되어 있는지를 bfs를 통해서 알아봐서 두 부분다 연결이 되어있으면 두 부분의 인구수 차를 구해 출력했습니다.
선생님 처럼 dfs가 아니라 이렇게 bfs로 연결되어있는지를 확인하는 로직인데 혹시 괜찮은 방법인지, 개선할 점이 있는지 궁금합니다.
답변을 작성해보세요.
1
큰돌
지식공유자2022.09.28
안녕하세요. ㅎㅎ
괜찮긴한데.. 비트마스킹 + bfs로 할 거면
i 부분있잖아요. ^ 연산자 통해서 101 일 때 010 만들어서 같이 진행을 할 것같구요.
bfs에서 return되는 값을 bool이 아니라 pair나 등 좀 더 bfs 함수 하나만으로 로직이 다 처리되게끔 하면 좋을 것 같아요.
그리고 start 지점을 for문을 통해서 찾는데 비트마스킹 시간에 제가 최하위 비트 알려드린 거 있죠? 그걸 기반으로 하시면 될 것같아요
그리고 지금 보면 비트마스킹을 기반으로 bfs가 돌려지는데
for(int i = 0; i < connected[temp].size(); i++) {
if((start & (1 << (connected[temp][i] - 1))) && !visited[connected[temp][i] - 1]) {
이렇게 되는건... 효율적이지 않아요. 먼저 비트마스킹 > 각 노드에 색칠 > 색칠한 것을 기반으로 탐색할 정점들을 탐색 이렇게 하는게 좋을 것같아요.
감사합니다.
0
답변 2