swift DFS 완전탐색, 백준 15683 감시 문제풀이

 

 

 

---

백준 15683번, 감시 문제설명

 

 

 

오늘은 백준 15683, 감시 문제를 풀어보겠습니다. 감시 문제는 solved.ac기준, 골드5로 코딩테스트 기준 중후반에 나올 수 있는 수준의 문제입니다.

 

 

 

 

 

 

시간 제한은 1초, 메모리 제한은 512MB입니다. 제출횟수가 많은 검증된 문제(?)라고 할 수 있습니다. 

 

해당 문제의 설명은 다소 복잡한 관계로, 본 포스팅에 적은 설명과 별개로 직접 해당 문제의 설명을 보고 이해하시길 권장드립니다. 문제설명은 가볍게 하고 넘어가겠습니다.

 

 

 

 

 

 

1x1크기의 정사각형들로 이루어진 N x M 크기의 직사각형 사무실이 있습니다.

 

이곳은 빈공간 0 / 벽 6 / cctv 1~5가 설치되어있습니다. cctv는 1, 2, 3, 4, 5의 다섯가지 종류의 cctv가 있고, 각 cctv가 감시할 수 있는 방식은 위의 설명과 같습니다.

 

각 cctv는 위와 같은 방식으로 상/하/좌/우의 방향으로 배치하여 감시가 가능하고, 만약 중간에 벽이 있다면 벽을 뚫고 감시할 수는 없습니다.

 

 

 

 

 

 

각 CCTV는 회전이 가능하고 위와 같이 감시를 할 수 있습니다. 감시를 하는 방향에 따라 감시가능한 빈공간의 크기가 달라지겠죠? 이번 문제의 요지는 사무실에 배치된 벽, cctv가 주어질때 최대한 많은 빈 공간을 감시하는 경우, 바꿔말하면 감시못하는 사각지대의 최소크기를 구하는 문제입니다. 

 

 

 

 

 

 

 

입력은 첫 줄에 사무실 세로, 가로크기를 의미하는 N, M이 주어지고, 이후에 사무실의 그래프가 직사각형 형태로 주어집니다. CCTV의 최대개수는 8개를 넘지 않고, N, M의 범위가 매우 작기 때문에 완전탐색, 브루트포스 방식으로 문제를 풀어도 무방합니다. 

 

본 문제를 swift언어와 DFS(깊이 우선 탐색)을 통해서 해당 문제를 풀어보도록 하겠습니다. 

 

 

 

---

백준 15683 감시 swift 문제풀이
DFS(Depth - First Search) 이용, 완전탐색 문제풀이

 

 

 

먼저 라인입력을 받아 [Int]배열로 변환해주는 클로져를 정의했습니다. split, component등을 활용해서 입력값을 변환해도 되지만, 위와 같이 String 문자열을 받아서 커스텀으로 배열을 반환해서 사용하면 성능상 이점이 있습니다.

 

백준에서는 스위프트의 시간제한 조절이 제대로 안되어있는 경우가 많아, 저는 위와 같은 입력 최적화가 가능한 경우를 항상 고려하고 풀이합니다. 

 

위 클로져의 로직은 단순합니다. 문자열을 입력받고, 빈칸을 넘어가고, 그 외의 값은 숫자로 추출해서 배열에 누적시킵니다.

본 문제는 한자리 수의 숫자만 나오므로 가능한 로직입니다. 만약 두자리수 이상일 경우에는 좀더 로직이 추가되어야 하는데 본 문제는 이정도면 충분합니다. 

 

 

 

 

 

 

13행) Tuple은 커스텀 타입 하나를 정의했는데 꼭 이렇게 할 필요는 없습니다.

14 ~ 15행) cctv의 방향을 정의한 배열입니다. 순서대로 상 / 우 / 하 / 좌 입니다. 

16 ~ 17행) 첫 줄로 입력받는 정수 N, M 값을 저장합니다.

 

18행) G : 사무실 그래프를 입력받을 이차원 배열입니다.

19행) cctvList : CCTV의 (유형, x위치, y위치)를 담을 배열입니다. DFS에서 cctvList를 0번째부터 끝까지 순서대로 탐색하게 됩니다.

20행) zeroCnt : 초기 사무실에서 감시가능한 빈 공간의 갯수를 기록해둘 예정입니다.

 

 

 

 

 

 

22 ~ 24행) 두번째 줄 부터 사무실의 그래프을 입력 받습니다. 0 ~ 6의 숫자가 있는 2차월 배열을 G에 기록합니다.

 

 

 

 

 

 

위 코드에서는 입력받은 사무실의 정보를 재 탐색하면서 문제풀이 전 참고할 데이터를, cctvList, zeroCnt를 기록합니다. 

28 ~ 29행) cctv가 있는 곳은 (cctv의 유형, cctv x좌표, cctv y좌표)를 cctvList에 저장합니다.

30 ~ 32행) 빈 공간의 갯수를 zeroCnt에 기록합니다.

 

 

 

 

 

 

위 코드는 ,cctv로 감시가능했던 빈 공간에 감시했음을 표시함과 동시에 감시가능했던 공간의 크기를 반환하는 함수, coverZeroOneline입니다.

 

본 메서드는 아래 runCCTV에서 자주 사용되는 메서드입니다. 이런 메서드가 없으면 아래 runCCTV와 같은 메서드를 구현할 때 코드가 굉장히 난잡해져서 메서드 분리를 해두면 좋습니다.

 

 

 

 

 

 

특정 cctv의 유형과 cctv의 배치방향에 따른 감시가능 공간을 기록함과 동시에, 감시가능한 공간 크기를 반환하는 메서드입니다.

 

cctvNum의 유형에 따라 1, 2, 3, 4, 5번째 cctv의 감시기능을 작동시키고, 사무실의 감시상태를 기록(coverZeroOneline)하고, 감시가능했던 공간의 크기(coverTotCnt)를 반환합니다.

inout은 인자를 참조방식으로 넘겨받을 수 있도록 해주는데, 메서드 호출부 인자값 앞에 &을 붙여 넘겨줍니다.(&tmpG) 인자값이 메서드 내부에서 변경되면 원본 변수또한 변경됩니다. 실제 인자로 받은 변수를 변형시킬필요가 있을때 사용할 수 있습니다. 

 

 

 

 

 

 

DFS는 cctvList를 탐색하면서 모든 경우의 사각지대 크기를 확인하고, 최소 사각지대 크기를 구하는 메서드입니다.

 

78 ~ 82행) cctvList의 모든 cctv의 방향을 설정한 상태일때 사각지대 크기를 확인하고 메서드를 종료, 재귀 깊이를 1 줄입니다. 즉, 본 DFS 탐색의 기저조건입니다.

현재 탐색한 경우 기준으로 사각지대 크기(blindSpotCnt)를 계산하는데, 그 값은 전체 빈 공간의 크기(zeroCnt) - 감시가능했던 크기(coverCnt)입니다. 이 부분에서 최소 사각지대 크기를 Ans에 기록합니다. 

 

84행) nowG에 현재까지의 그래프 상태 tmpG를 저장합니다. 변수로 재 할당하는 이유는 runCCTV 메서드의 inout 인자값으로서 사용되고, 병형될 필요가 있기 때문입니다. 

 

85행) 현재의 cctv정보를 담습니다.

86 ~ 92행) 현재 cctv의 상/우/하/좌 방향 배치 시의 사무실 상태를 runCCTV로 기록하고, 그 다음 cctv의 배치를 위한 재귀함수를 호출합니다. 재귀함수가 끝난 이후에는 nowG를 다시 nowCCTV 배치 전의 상태(tmpG)로 복귀시킵니다. (다음 for문 케이스에 대해 체크해야하므로 상태를 돌려두어야함)

 

 

 

 

 

 

DFS메서드를 실행하고, CCTV 배치 경우의 수를 완전탐색 한 후 계산된 최소 사각지대 크기, Ans를 출력해줍니다. 이렇게 swift언어를 사용해서 swift DFS 완전탐색, 백준 15683 감시문제를 해결할 수 있었습니다. 이번 문제는 DFS 완전탐색을 활용해서 풀어봤습니다. 

 

이렇게 코드를 작성 후 제출한 결과는 아래와 같습니다. 의견, 질문 등 환영합니다.

 

 

 

---

 

백준 15683 감시 swift 완전탐색 구현 후 제출결과