[백준_BOJ] 14502. 연구소 문제풀이 JAVA

문제

 

 

 

 

 

 

 

풀이

 

 

정말 오랫동안 헤맸던 문제입니다. ㅠㅠ 여러번 시도 끝에 풀이하여 기쁜 마음으로 포스팅합니다!

1. 먼저 Input() -- > 문제에서 주어지는 입력을 받는 부분입니다.

맵의 사이즈, list( 벽을 만들기 위해 사용 ). vlist ( 바이러스 위치 저장을 위해 사용 ), bfs를 위한 

큐 생성 등..  입력을 받을 때 0 ( 벽을 세울 수 있는 위치 )은 list에 넣어주었고 
                                          2 ( 바이러스가 있는 위치 )는 vlist에 추가해주었습니다.

 

2. 다음으로 buildWall 함수입니다.

 ( cnt == 3 ) 을 종료 조건으로 하며  벽 3개를 세워주는 함수입니다. 가장 최적의 장소일 때를 찾기 위해 모든 지점에

벽을 한 번씩 세워보면서 check( ) 함수를 통해 최적의 장소에서 정답을 기록합니다.

 

함수 내에서 list에서 해당 idx 번째 위치에

벽을 세울 경우 --> buildWall( cnt + 1 , idx + 1 ) ;

벽을 세우지 않을 경우 --> buildWall ( cnt, idx + 1 );

모두 검사하여 항상 답을 찾을 수 있도록 해주었습니다.

 

3. bfs 함수입니다.

벽이 모두 세워진 상태에서 바이러스를 퍼트립니다.

바이러스를 퍼트린 뒤 안전구역을 cnt 하여 가장 큰 값을 정답으로 저장합니다.

 

마지막으로 check ( ) 함수입니다.

바이러스를 모두 퍼뜨린 뒤에 가장 많은 안전구역을 갖는 경우를 위해 바이러스를 퍼뜨릴 때마다 cnt를 기록합니다.

max 값을 갱신하여 최고 값을 기록합니다.

 

 

 

 

코드

 

 

 

 

 

출처

 

 

https://www.acmicpc.net/problem/14502

14502번: 연구소