알고리즘48 :: BOJ_17142_연구소3

연구소 3 문제는 맵에 활성 바이러스와 비활성 바이러스가 주어지게 되는데 

 

이 두가지를 잘 이용해서 문제를 해결할 수 있습니다. 

 

맵을 순회하면서 바이러스를 ArrayList에 저장하고 이중에서 Input으로 입력받은 개수 만큼 조합을 이용해서 선택합니다. 

백트래킹을 사용하여 활성 바이러스는 -2 비활성바이러스는 -3으로 표시하여 선택된 활설바이러스 로부터 BFS()를 돌렸습니다.

for(int i=index; i<al.size(); i++) {
                select[nn] = i;
                laboratory[al.get(select[nn]).x][al.get(select[nn]).y] = -3; //활성 
                go(nn+1, i+1);
                laboratory[al.get(select[nn]).x][al.get(select[nn]).y] = -2; //비활성
                
            }

 

 

 

 BFS() 돌릴때 Time 배열을 만들어서 -1로 초기화 했으며 이는 바이러스가 확산될때 일종의 visit 배열의 역할을 담당시켰습니다. 

 

최종적으로, 맵을 전체 순회하고 시간을 체크할때 맵의 값이 0 인곳(=지나갈 수 있는 칸, Time 배열에서는 시간이 적혀있는 index) 을 확인하여 최소 시간을 체크합니다. 

 

단, time은 초기에 -1로 채웠으므로 최종 단계에서 time에 -1값이 존재하면 return 하도록 했습니다. 

 

 

이 문제를 해결할때 한가지 착각 한것이 있는데, 

내용은 아래와 같습니다. 

질문내용중에

선택된 바이러스가 확산되면 Time 이라는 배열을 두어 표시를 해두었으나 만약 `비활성 바이러스` 를 만나는 경우에는 Time 이 확산되는 바이러스 시간을 유지하며 맵에 표시를 해두어야 하는지 아니면 다시 1 부터 시간을 표시해야하는지 의문이 들었습니다.

이 경우 저는 Time에 확산되는 바이러스 시간을 유지하여 맵에 표시해두었으나 명확하지 못한 것 같아 질문글을 작성합니다.

 

답글을 읽고 생각해보니, 새롭게 활성화된 바이러스는 시간을 초기화 해줄 필요가 없었습니다. 

 

Code : 꽥! 클릭 클릭 해주세요.

궁금한게 생기시면 클릭해주세요!!! 서로 배워 가요 😀