# 연구소3 비트마스킹 연산은 잘 구현함✅ 틀린 부분 1. 로직이 중구난방으로 얽혀있음. 구현을 하면서도 코드가 실행되는 순서와 로직이 나와야할 순서가 가늠이 잘 되지 않았다. =>로직의 흐름을 선명하게! 소스 코드 흐름(구조) 1. 모든 부분집합 subset 구한다. 2. 바이러스 갯수 M개인 부분집합 구한다.\ 바이러스 갯수가 M인 각각의 부분집합에 대해 BFS하기 때문에 2 스코프가 시작하면\ ① BFS에 필요한 자료구조 생성\ ② 몇 번째 바이러스가 존재하는지 비트연산으로 검사! 3. 바이러스확산 BFS 탐색한다. 4. 전체 완전탐색 검사한다. (전체 완탐 못한 경우 정답은 -1) 틀린 부분 2\. 바이러스 M개인 부분집합 BFS에 필요한 자료구조 셋트\ 큐, 방문체크 배열, **걸린 시간(dist)//스코프 중구난방 위치에 있어서 틀림.** **3. BFS 목적 : 전체 확산하는데 걸리는 시간을 구한다.**\ **2차원 배열 Map 값이 2이면 그 칸을 방문할 때 시간 카운팅하지 않는다!**\ **2차원 배열 Map 값이 2가 아닐 때만 시간 계산한다!!!**\ ~~**고로, BFS는 Map값이 2가 아닌 칸에 대해서만 탐색한다!**~~**⭐️(코드 잘못 읽어서 틀림)**\ **=>BFS는 Map값이 2가 아닌 칸에 대해서만 시간을 구하고, 최댓값으로 갱신해서 저장한다!** **4. 바이러스 M개인 부분집합 BFS에서 걸린 시간은 dist의 최댓값이다!**\ **=> 큐에서 꺼내자마자 (Map값 조건 검사 후) Math.max()로 최댓값을 갱신해서 저장한다!** **5. BFS 다음 방문 노드 탐색 조건**\ **nx, ny 범위 체크✅ 이미 방문한 노드 체크✅**\ **Map값에 따른 조건 검사 : Map값이 1인 경우만 continue처리. 0 또는 2?인 경우 다음 노드로 방문 가능하다!** 6\. 전체 완전 탐색 검사**⭐️⭐️⭐️⭐️⭐️**\ 조건 : **Map\[i]\[j] == 0 && visited\[i]\[j] == false**\ 🧐케이스 생각 : 부분집합 A에서 -1이 나왔을 때 다른 부분 집합에서 -1이 아닌 다른 양수값이 나올 수 있나? **YES⭐️**\ **그렇기 때문에 아래 코드처럼하면 어떤 부분집합에서 -1이 나오면 Math.min으로 최솟값을 저장하기 때문에 한번 -1이 나오면 계속 -1을 저장하기 때문에 아래 코드는 틀렸다!**\ **=> 어떻게 고칠 수 있나? (정답 컨닝)**\ **1. boolean 변수 flag를 만든다. //flag = true;**\ **2. 전체 완전 탐색 조건 검사 : 전체 완탐 못한 경우 : flag = false;**\ **3. flag가 true일 때만(전체 완탐한 경우에만) 정답 최솟값으로 갱신해준다!**\ **완탐못한 경우라면 dist는 -1이 되는데, 이 -1인 dist로 최솟값 저장해버리면 무조건 -1로 계속 저장되기 때문에!**\ **완탐한 경우에만 이 때의 dist를 최솟값으로 갱신, 저장한다!!** ```java for(int i=0;i 무한루프에 빠짐!!\ 메서드 동작 순서\ ① subset의 가장 오른쪽 비트와 1 AND연산한다.\ ② 연산한 값이 1이면 cnt를 1씩 증가시킨다.\ ③ subset을 1비트 오른쪽 시프트연산한다.\ 틀린 부분 : ③ subset 오른쪽 시프트연산하는 부분은 cnt를 증가시킨 후에 해야한다! ```java static int OneCnt(int subset) {//10101. subset을 오른쪽으로 한칸씩 시프트하고 1과 앤드연산해서 결과가 1이면 cnt++ int cnt = 0; while(subset>0){ subset = subset>>1; if((subset & 1) != 0) { cnt++; } } return cnt; } ``` OneCnt 메서드 두 번째 틀림 : \ while문의 반복 조건인 subset>0이 항상 참이 되어 무한루프에 빠져버렸다!!\ 아래 코드의 경우, subset의 비트가 1일 때만 subset을 오른쪽 시프트연산하기 때문에 subset은 항상 양수가 되고, while문 조건을 항상 만족해서 무한 루프에 빠지게 되었다!!! ```java static int OneCnt(int subset) {//10101. subset을 오른쪽으로 한칸씩 시프트하고 1과 앤드연산해서 결과가 1이면 cnt++ int cnt = 0; while(subset>0){ if((subset & 1) != 0) { cnt++; subset = subset>>1; } } return cnt; } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-1/3-1.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.