연구소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를 최솟값으로 갱신, 저장한다!!

for(int i=0;i<N;i++) {
    for(int j=0;j<N;j++) {
					if(Arr[i][j] == 0 && visited[i][j] == false) {
            ret = -1;
          } else{
            ret = Math.min(ret, dist);
          }
		}
}

부분집합 A = -1, 부분집합 B = 양수값

7. 부분집합 subset이 바이러스가 M개인 부분집합인지 검사하는 메서드 OneCnt => 무한루프에 빠짐!! 메서드 동작 순서 ① subset의 가장 오른쪽 비트와 1 AND연산한다. ② 연산한 값이 1이면 cnt를 1씩 증가시킨다. ③ subset을 1비트 오른쪽 시프트연산한다. 틀린 부분 : ③ subset 오른쪽 시프트연산하는 부분은 cnt를 증가시킨 후에 해야한다!

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문 조건을 항상 만족해서 무한 루프에 빠지게 되었다!!!

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;
	}