감시
Last updated
Was this helpful?
Last updated
Was this helpful?
문제에서 주어진 N,M의 제한이 크지 않고, CCTV의 최대 갯수도 크지않았다. 최대 8개의 CCTV 각각의 방향(4가지)을 선택하는 모든 경우의 수를 다 구해봐도 4^8 <1억 이기 때문에 순열과 재귀 방법의 Brute Force 풀이방법이 제일 먼저 생각 났다. 그런데 재귀함수를 구현하는 부분에서 현재 Index의 cctv의 방향을 설정하고, 감시영역으로 마킹하고, 다음 경우를 호출하는 부분에서 구현에 자신이 없었다. 기능 구현에 있어서 선택, 재귀, 원복 생각해냈었지만! 구현해내지 못해서 아쉽다.
💡알고리즘 큰 그림 : 0을 제외한 모든 칸의 갯수를 합산해서 모든 CCTV 방향 설정한 후 N*M에서 뺀값이 가장 작은 것이 정답이 된다!
0. 처음에 입력 받을 때 0을 제외한 모든 칸 수를 세서 재귀함수에 매개변수로 넘겨준다! (매개변수 sum에 index번째 cctv 방향설정함으로써 감시영역 마킹한 칸 갯수를 sum에 계속 더해가고, 매개변수로 전달한다!) 1. index번째 CCTV의 방향 설정하는 재귀함수 make_dir(int index,int sum) 2. 방향 설정한 1의 감시 영역 칸 갯수 카운팅 & 리턴하는 함수 cctv(int x,int y,int dir) 3. 원상 복구하는 함수 rollback(int x,int y,int dir)
index번째 CCTV의 방향 설정하는 재귀함수 make_dir(int index,int sum) ① 선택 : index번째 CCTV의 번호에 따라 모든 방향을 선택한다. ② 재귀 : index+1번째 CCTV 방향 설정 위해 재귀함수 호출. ③ 원복 : ①에서 선택한 위치, 방향의 마킹한 것을 그대로 원복시킨다. ① 선택 : 현재 index의 CCTV 번호에 따라 선택하는 방향 갯수가 달라진다.⭐️⭐️⭐️⭐️⭐️ CCTV#1 : 4가지 경우의 방향(상,하,좌,우) CCTV#2 : 2가지 경우의 방향(상하,좌우) CCTV#3 : ㄴ ↱ㄱ↲ 총 4가지 경우의 방향 CCTV#4 : 4가지 경우의 방향 CCTV#5 : 4가지의 방향 모두 선택 tSum = cctv(cur.x,cur.y,dir) 각 CCTV마다 각각의 방향을 선택할 때 cctv함수로 감시영역을 마킹하여 갯수를 바로 합산한다! index+1번째 CCTV 방향 설정하는 재귀함수 호출할 때 매개변수로 현재까지의 0을 제외한 모든 칸수를 함께 넘겨주는 것이다!!
② 재귀 : make_dir(index+1, sum+tSum) ③ 원복 : cctv(cur.x,cur.y,dir)로 감시 영역 마킹한 칸들을 다시 원상복구시킨다!
💡구현 Tip
같은 코드가 2번 반복된 코드 : sum++이 2번이나 중복된 것을 알 수 있다.
범위에 따라 공통되는 로직은 한번만 수행하도록 하고, 1차 필터링 후 한번 더 조건을 추가함으로써 해결할 수 있다! 1. if(Map[i][j] >0 ) : sum 1씩 증가시킨다! 2.if(Map[i][j] >0) 조건문 아래에 if(Map[i][j] < 6) 조건을 추가해서 이 경우 0<Map[i][j] < 6 이므로 CCTV에 해당하는 것이므로 이 때 CCTV 배열 또는 컬렉션에 객체 생성하여 추가해주면 된다!!!
💡내 접근법(틀린 부분) CCTV cur = cctvList[index]라고 하고 cur.id(CCTV 번호)에 따라 선택하는 CCTV의 방향을 다르게 해주었다. index번째 CCTV의 방향을 선택하는 재귀함수지만, index에 따라 선택하는 방향에 따른 구현이 장황해져서 함수 자체도 목적은 간결한데 함수의 목적이 뚜렷하게 보이지 않았다. => 함수를 분리해야 한다! 적어도 2개의 함수 구현이 필요하다! =>index번째 CCTV 선택하자마자 감시 영역 마킹하여 갯수 리턴, 재귀함수 호출할 때 매개변수로 전달
다수의 CCTV 방향이 서로 겹쳐서 감시 영역이 겹치는 경우, cctv함수에서 그냥 한번만 Map[i][j] = 8로 마킹해주면 된다고 생각했는데 정답 코드에서는 이미 8로 마킹되있다면 Map[i][j] >=8에 대해 Map[i][j]를 1씩 증가시킨다! 원복할 때도 마찬가지로, Map[i][j] > 8인 칸에 대해서 바로 0으로 만들어주는 것이 아니라 1씩 감소시킨다! A방향, B방향의 감시영역이 중복되고, 방향 설정할 때 중복되는 횟수를 카운팅하지 않고 8로만 마킹하고, 원복할 때도 8인 칸을 0으로 한다고 가정해보자. A방향 감시영역 8로 마킹, B 방향 감시영역 아무 변화 없다. A방향 원복시, 8인 것을 0으로 바로 마킹시켜버리면 B방향에대한 감시영역이 처리되지 않기 때문에 답이 틀리게 나온다! 즉, 원복할 때, 다른 방향의 감시영역까지 0으로 초기화되버리기 때문에 이를 방지하기 위해, 방향을 설정할 때 이미 8로 마킹되어있다면 1씩 증가시키고, 마찬가지로 원복할 때에도, 8보다 크면 1씩 감소시키고, 8이면 0으로 셋팅한다!(감시영역이 하나의 방향에 대해서만 설정되었다는 것을 의미하기 때문이다!!)
3번째 풀었을 때
생각한 부분
필요한 기능 별로 로직을 처리하는 메서드를 분리했다. - go, monitor, rewind go(index) : index번째 cctv의 감시 방향을 선택 monitor(x,y,dir) : 현재 cctv의 위치(x,y)에서 선택한 방향 dir대로 감시 영역을 마킹 rewind() : 현재 선택한 것을 원복 =>원복하는 부분도 monitor와 똑같은 과정으로 반복하되, 증가->감소, (0->8) =>(8->0)으로 해주면된다. 다만 주의해야할 점은, monitor에서는 8이상인 조건을 걸어주어 8부터 포함하여 값 증가했지만, 원복할 때는 8을 포함하지 않고, 8보다 큰 값에 대해서만 감소처리하고, 8일 때 0으로 만들어줘야한다. 그렇지 않고 if(Office[x][y]>=8) ... else if(Office[x][y]==8) 이렇게 해버리면 8일 때는 2가지 조건에 모두 해당하여 별개의 로직을 모두 수행해버린다.
틀린 이유 인터페이스화, 기능 단위로 메서드를 생각한 것은 잘 했는데 각 케이스별로 메서드 내부를 구현하는 것을 못했다.
원복하는 부분에서 선택할 때 카운팅했던 감시 영역 갯수 cnt를 다시 빼줘야한다고 생각하고, 초기에 감시한 경우(Office[x][y] == 8)에서 0으로 바꿀 때, 갯수를 카운팅해서 tSum에 다시 빼주었는데 그럴 필요없다. tSum은 이후에 다시 사용하지 않을 값이고, 각 cctv별로 if-else문으로 롲직이 분되어있을 뿐더러 로직 내에서도 tSum에 값을 넣는(덮어쓰는) 식으로 되있기 때문이다. 즉, cctv 번호에 따라 tSum은 1번만 쓰이기 때문에 원복할 때 다시 감산하지 않아도 된다!!!
감시영역은 cctv, 벽 0보다 큰 값들(cnt)을 포함하기 때문에, 재귀함수에서 합산해가는 감시영역 갯수 sum은 0이 아니라 cnt부터 시작한다!
각 cctv마다 monitor라는 동일한 메서드를 사용하여 현재 선택한 방향으로 감시영역을 마킹한다. 내가 생각했던 monitor 메서드 호출 모습은 1번은 단일 방향에 대해서만 하기 때문에 monitor메서드에도 한가지 방향마다 한가지 경우이기 때문에 monitor 메서드를 호출했지만, 나머지 2번~4번 방향에서는 2번 : 상하, 좌우 2가지 3번 : 직각 방향 4가, 4번 : 상하좌우에서 1가지 뺀 4가지 경우를 구체화하지 못했다.
1번 cctv 부터 코드를 다시 살펴보면 다음과 같이 고칠 수 있다.
그리고 2번~4번 cctv 부터는 처음으로 선택하는 감시방향에 따라 난머지 감시방향을 정할 수 있다! 2번 : dir 선택시, 나머지 방향은 반대 방향 3번 : dir 선택시, 나머지 방향은 dir+1 4번 : dir 선택시, 나머지 방향은 dir+1, dir+2
monitor메서드의 기능을 명확하게 정해놓으면 monitor를 호출, 실행하는 것도 어렵지 않다. 처음에 내가 생각했던 대로 현재 cctv 위치와 선택한 방향dir만 알면 monitor는 감시 영역을 마킹할 수 있다. dir 방향대로 범위체크, 벽체크해주고 감시영역 마킹하면 되기 때문이다. monitor는 단일 방향 dir에 대해 감시영역을 마킹한다. 그렇기 때문에 cctv 별로 단일 방향갯수, 방향만큼 monitor로 감시 영역 마킹하면 된다.
2번의 경우 : 감시 방향을 더 구체화하면 한가지 방향 선택하고 그 방향으로 monitor 호출&실행하고, 나머지 한가지 방향은 반대 방향이기 때문에 반대 방향으로 monitor 호출&실행하면 된다.
3번의 경우 : 위에서 정의한 대로, 처음 선택한 방향 dir, dir+1마다 해당 방향으로 monitor 호출해주면 마찬가지로 해당 방향으로 일직선으로 쭉 감시 영역 마킹한다.
4번의 경우 : 위에서 정의 한대로, 처음 선택한 방향 dir, dir+1, dir+2 3가지 방향으로 각각 monitor 호출해주면 해당 방향으로 감시 영역 마킹한다.
내가 부족했던 점 : 공통 로직을 수행하는 monitor 메서드를 쓸 수 있게 호출하는 부분에서 적절하게 구현해야한다. 즉, cctv별로 방향을 더 쪼개서 1번 cctv처럼 monitor는 단일 방향 dir에 대해 감시영역을 마킹하기 때문에 cctv 별로 단일 방향갯수, 방향만큼 monitor로 감시 영역 마킹하면 되는 것이다.
최종적으로 구하고자 하는 것 : 최소 사각지대 갯수 => 최대 감시영역을 만들어야함. => monitor로 감시 영역 마킹하면서 각 경우마다 감시영역을 증가시켜 카운팅할 수 있다. => 재귀함수 거듭할 수록 현재까지 마킹한 감시영역 갯수를 넘겨주어 모든 cctv 방향 선택 다 한후, sum의 최댓값을 선택하거나, 전체 사무실 크기에서 sum을 뺀 값 중 최솟값을 선택하면 된다. 내가 참고하는 풀이법에서는 입력받을 때부터 0을 제외한 칸(cctv, 벽) 갯수를 감시영역에 먼저 카운팅한다. 그래서 따로 0갯수를 카운팅하지 않고, 입력받을 때 카운팅했던 기본 감시영역 갯수 sum에서 재귀함수로 합산한 최종 sum을 전체 사무실 크기에서 빼서 최솟값을 갱신하도록 한다.
문제 정리, 문제 해결 과정: 정답을 구하기 위해 최솟값을 구할지, 최댓값을 구할지 결단력⭐️
구하고자하는 사각지대 갯수는 0보다 큰 값의 갯수부터 시작한다.⭐️ 사각지대 갯수를 입력받을 때부터 구할 수 있다. => 재귀함수를 거듭하며 cctv 방향 선택하면서 감시 영역 갯수 더해간다! 모든 cctv 선택 다한 경우, 2차원 배열 전체 크기에서 sum을 뺀값 최솟값을 정답 변수에 넣어주면 된다!
모든 cctv의 방향을 선택해주면 된다. : go(index, sum) : index는 현재 cctv 몇 번째인지 인덱스, sum은 1에서 구한 값으로 시작하여 현재 index번 cctv의 방향을 선택함으로써 만든 감시 영역 갯수를 합산한 값으로 재귀호출 실행하면 된다!
각 cctv 별로 방향 선택할 때, 선택한 방향에 대해 감시 영역 마킹 처리 : monitor(x,y,dir)⭐️ 주의할점 : 이미 다른 cctv가 감시처리한 경우 : 갯수만 늘려주고, 현재 cctv가 처음 감시하는 경우는 8같은 구분가능한 숫자로 마킹한다. 이때, 처음 감시하는 경우에만 감시영역을 1증가시킨다! 중복해서 카운팅하지 않기 위함이다! index-1번째 cctv에서 이미 해당 행/열 칸을 마킹하면서 감시영역갯수를 카운팅하여, 현재 깊이의 index번 cctv에 대한 재귀함수를 호출했기 때문에, 이미 감시처리한 경우(>=8)는 갯수만 증가시켜주고 감시 영역 갯수는 이미 카운팅되었으므로 증가시키지 않는다!
재귀함수 호출 : 다음 경우 처리 => go(index+1, sum+tSum) : 이전까지의 합sum에 현재 index번에서 만든 감시영역 갯수tSum을 합산한 값으로 재귀호출, 실행한다.
원복 : cctv마다 선택하는 방향에 대해 monitor 로직 처리한 것을 그대로 원복.⭐️⭐️⭐️⭐️ 선택한 방향에 대해 모두 원복시켜야하는데, 한번만 해버려서 틀렸다.