4- c질문
460
작성한 질문수 3
http://boj.kr/f73a62d8306144558a6106909f0c9e2f
i = 1부터 돌려가며 예를 first, second를 초기화해준뒤
예를들어 n = 6
이면 first -> 110011 이면 second -> 001100
두 부분으로 나눈 뒤 각각의 부분에 포함된 정점이 연결되어 있는지를 bfs를 통해서 알아봐서 두 부분다 연결이 되어있으면 두 부분의 인구수 차를 구해 출력했습니다.
선생님 처럼 dfs가 아니라 이렇게 bfs로 연결되어있는지를 확인하는 로직인데 혹시 괜찮은 방법인지, 개선할 점이 있는지 궁금합니다.
답변 2
1
안녕하세요. ㅎㅎ
괜찮긴한데.. 비트마스킹 + 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]) {
이렇게 되는건... 효율적이지 않아요. 먼저 비트마스킹 > 각 노드에 색칠 > 색칠한 것을 기반으로 탐색할 정점들을 탐색 이렇게 하는게 좋을 것같아요.
감사합니다.
1-E질문입니다!
0
513
2
3-L 틀린 부분 피드백 부탁드립니다.
0
815
2
1-A문제 순열재귀함수 질문입니다.
0
380
1
1-A 일곱난쟁이문제입니다
0
454
1
문제 풀 때 방향성에 대해
0
796
1
맥에서 vs code로 실행 관련 질문입니다
0
520
1
17071번 메모리 초과
0
384
1
1-C질문입니다!
0
415
2
2-B BFS 시간초과질문
0
626
2
1-O 13번 라인
0
437
1
6-J 놀이공원 문제 질문
0
379
1
구현관련 질문
0
481
1
강의 교안
0
316
1
실력을 더 올리고나서 강의를 보는 것이 맞을까요?
0
544
1
안녕하세요! 재귀함수에 관해서 질문드립니다
0
534
1
1-K
0
471
2
3-G번 질문있습니다.
1
467
3
3-C 실행 시간 질문드립니다.
0
491
1
4-A 문제 풀이 질문있습니다.
0
589
2
비트마스킹 연산자 "1의 보수" 영문 표기법
0
433
1
격자탐색 문제에서 BFS 시간복잡도 질문드립니다.
0
332
1
3-O go 함수 질문 드립니다.
1
440
2
4-A 출력 질문
0
301
1
1주차 1-O 질문드립니다
0
253
1