백준 14502: 연구소 (Swift)

bfs와 dfs를 종합적으로 사용해야하는 문제였다. 꽤나 어렵고 오래 걸리는 문제였다.

순한맛 삼성전자 코딩테스트 문제라고 할 수 있을 것 같다.

 

1. dfs(백트래킹) 형태로 2차원 배열을 순차 탐색하며 3개의 벽을  순열 형태로 세워, 3개의 벽이 세워질 때마다 해당 2차원 배열의 주소를 매개변수로 넘겨줍니다. ( 3개의 벽이 세워졌는지의 여부는 level이라는 매개변수로 check합니다)

 

2. 그렇게 dfs에서 3개의 벽이 세워질 때마다 bfs()함수가 호출되고, 그 때의 2차원 배열에서 VIRUS 전파를 실행하고, 안전영역의 수를 return해준다.

 

각 이미지 아랫쪽에 문제풀이의 핵심 아이디어를 작성해보았다.

Point 1. virus의 위치를 미리 담아놓는다.

    -> 우리는 아랫쪽에서 백트래킹을 통해 수많은 경우들에 대해 virus전파 후 안전영역의 갯수를 구해야한다. 그 모든 경우들에서 virus의 갯수와 위치는 변하지 않기 때문에 전역변수에 담아두었다.

Point 2. 바이러스가 퍼지기 전 안전여역의 갯수 (zeros)를 세놓는다 ( -3을 해준 이유는 벽을 3개 세워야하기 때문 )

    -> 바이러스의 전파 이전에 안전영역의 갯수는 백트래킹 중 항상 변하지 않기 때문에 미리 세놓았다.

Point 3. 바 q와 result에 virus 와 zeros값을 얕은 복사하여 사용. virus와 zeros는 계속 참고해야하는 값이므로 변하지 않게 하고 사용.

Point 4. 바이러스를 전파하며 arr의 0들을 2로 바꾸는 식으로 함수를 작성하였었다. 하지만 그렇게 하려면 n * m 크기만큼의 Int형 배열이 필요하기 때문에, visited라는 n * m크기의 Bool 배열을 사용하는 것이 메모리 면에서 효율적일 것이라고 생각했다.

여기서 0인 것만 신경쓰면 되기 때문에, visited여부로 간접적 체크하는 것이 까다롭지 않았다.

Point 5. 바이러스들이 배치된 2차원 맵에 백트래킹 (순열 ) 형식으로 3개의 벽을 세우며, 

3개의 벽이 세워진 경우 bfs()함수를 호출하여 해당 경우의 안전영역 크기를 구해오도록 하였다.