Lab3

문제 복기

틀린 이유(4번 제외하고 다시 코딩해보자!)

1. BFS탐색 반복 조건 : 큐에 계속적으로 객체 추가해주고 큐가 비지 않을 때까지 해주어야하는데 while(!q.isEmpty()) 빼먹음.

2. 바이러스 갯수가 M개인 부분집합에 대해서만 BFS 하기 때문에 각 비트수 갯수가 M개인지 판단해주어야하는데 빼먹음.

3. 모든 칸을 다 방문했는지(바이러스가 다 퍼졌는지) 확인 if(map[i][j] == 0 && timt[i][j] == 초기값) 이면 -1을 리턴 수정 후 : 빈칸(0)인데 가지 않은 것(visited[i][j]== false)을 체크해준다.

boolean flag = true;
if(map[i][j] == 0 && visited[i][j] == false){
    flag = false;
}
if(flag) {
    ret = Math.min(ret,dist);//dist는 각 부분집합의 걸리는 시간
}
//ret가 여전히 INF라면 바이러스가 전체 퍼지지 못했으므로 -1을 리턴.
if(ret == INF){return -1;}
return ret;

4. BFS 탐색을 진행할 때 다음 노드가 될 수 있는 조건(다음으로 이동할 좌표 필터링) 헷갈림. 유튜브 질문 댓글과 정답 코드 참고해서 다시 생각해보자. 5. i번째 바이러스가 있는지 검사 : 비트마스킹 i번째 칸이 1인지 검사 1<<3 = 1👉🏻2^3, 1<<N = 2^N이므로 A<<B = 2^B 라고 생각하면 된다. 1, 10, 100, 1000 순으로 i번째 칸과 &연산해서 1인지 아닌지 확인하는 것이다! =>i는 0,1,2,3,4,,, =>2^0,2^1,2^2,2^3,... 과 &연산해서 i번째 비트가 1인지 아닌지 확인한다!

바이러스 갯수 : VirustCnt 0,1,2,3,4 번째 바이러스가 있는지 없는지 확인 => 0,1,2,3,4번째 비트가 1인지 확인한다! i=0,1,2,3,4로 증가, 반복한다!

for(int i=0;i<VirusCnt;i++{
    if((subset & (1<<i)) {//i번째 바이러스가 있다는 뜻이므로
        q.add(Virus[i]);//해주면 된다!
        visited[Virus[i].x][Virus[i].y] = true;
        ...
    }
}