[Python] BOJ(백준) 14502번 - 연구소

링크

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

난이도(solved.ac 참고)

골드5

풀이

1. input값으로 받은 a 리스트를 돌면서 값이 0이라면 전부 candidate라는 리스트에 인덱스 형태로 넣어주고(ex. (0, 1)), 2라면 큐에 담는다.

2. candidate 리스트에서 3개를 뽑아내는 순열 반복을 하면서 큐와 a를 각각 카피해서 새로운 변수에 지정해주고 그 순열에 해당하는 부분에 대해 a_copy 내의 해당 인덱스의 값을 1로 바꿔준다. (3개를 뽑아 벽을 세우는 것)

3. 그다음 result라는 변수에 bfs 함수의 리턴값을 부여한다.

3-1. bfs 함수에서는 a_copy 내의 값이 0일 경우 전부 2로 바꿔준 뒤 큐가 비게 되면 while문이 끝나면서 a_copy에서의 0의 개수 temp를 리턴한다.

4. max_result라는 변수를 부여한 뒤 매번 bfs 함수를 돌 때마다 더 큰 값으로 업데이트 되게끔 하고 그 값을 출력해서 마무리한다.

 

PyPy로는 통과했으나 Python 3으로는 시간초과가 떴다. 다시 한 번 봐야되겠지만 일단 논리는 맞았으므로 포스팅한다.