[BOJ] 백준 15683번: 감시_자바(JAVA)

1. 문제

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

15683번: 감시

---

2. 접근 및 해결

2-1) 접근

이 문제를 풀기 위해 한 cctv에서 고려해야 할 것은  종류, 위치, 방향으로 총 3가지 입니다.

그런데 종류, 위치는 이미 문제에서 주어지기 때문에 우리는 방향만 정하면 됩니다.

종류, 위치(x, y), 방향에 대한 정보  는 cctv 리스트로 관리할겁니다.

위치는 x좌표, y좌표가 있으므로 총 4가지의 정보를 담아야 합니다.

int[][] cctv = new int[8][4]; // 카메라의 최대 개수는 8개, 하나의 카메라에 대해 저장할 정보는 4가지

for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				list[i][j] = Integer.parseInt(st.nextToken());
				if(list[i][j] > 0 && list[i][j] < 6) {
					cctv[cnt][0] = list[i][j]; // 카메라의 정보(1번, 2번, 3번, 4번, 5번)
					cctv[cnt][1] = i; // 카메라의 x좌표
					cctv[cnt][2] = j; // 카메라의 y좌표
					cctv[cnt][3] = 1; // 카메라가 바라보고 있는 방향(1_왼쪽, 2_오른쪽, 3_위쪽, 4_아래쪽)
					cnt++; 
				}
			}
		}

 

 그렇다면 우리는 방향을 관리해야합니다. 이 방향을 정하는건 백트래킹을 이용하면 됩니다.

그렇다면 백트래킹으로 어떻게 할까요?

떠오르는데는 2가지의 방법이 있는데,

1. 종류별로 다르게 방향을 결정하는 방법

2. 그냥 종류 상관없이 일단 방향을 4가지로 두고 추후에 세세하게 결정하는 방법

이 있습니다. 

CCTV가 감시할 수 있는 방법

 

1. 종류별로 다르게 방향을 결정하는 방법

종류별로 다르게하면 총 15가지 경우의 수가 나옵니다.
1번 cctv : 4 가지 (왼, 오, 위, 아래)
2번 cctv : 2 가지 (왼+오, 위+아래)
3번 cctv : 4 가지 (왼+위, 왼+아래, 오+위, 오+아래)
4번 cctv : 4 가지 (왼+오+위, 왼+오+아래, 위+아래+왼, 위+아래+오)
5번 cctv : 1 가지 (왼+오+위+아래)

그런데 이렇게 하면, 1번 cctv인 경우에만 해도 아래와 같은 동작을 수행해야합니다.

if(list[i][j]==1) { // 1번 cctv인 경우
   left(i, j); // 왼쪽 바라본 경우, 왼쪽에 대응되는 것을 -1로 넣음
   func(k+1); // 다음 카메라 이동
   leftRestore(saveList, i, j); // 왼쪽에 대응되게 바꾼 리스트를 다시 복구

   right(i, j); // 오른쪽 바라본 경우
   func(k+1);
   rightRestore(saveList, i, j);

   up(i, j);
   func(k+1);
   upRestore(saveList, i, j);

   down(i, j);
   func(k+1);
   downRestore(saveList, i, j);

}
...

이렇게 하면, 코드도 더러워지고 매 번 계속 리스트 값을 변경해야하므로 시간복잡도가 매우매우 .. 커지게 됩니다..

(사실 처음에 코드를 이렇게 짰었습니다. 코드가 500줄이 넘어가더군요 ㅋㅋ..)

 

2. 그냥 종류 상관없이 일단 방향을 4가지로 두고 추후에 세세하게 결정하는 방법 -> 채택!

1번째 cctv - 왼, 오, 위, 아래

2번째 cctv - 왼, 오, 위, 아래 

3번째 cctv - 왼, 오, 위, 아래 

... 그런데 문제에서 최대 8개의 cctv까지 주어진다고 했으니 8번째 cctv까지 계속 왼, 오, 위, 아래의 정보만 넣는겁니다!

그리고 백트래킹이 완료된 이후에 카메라의 종류에 따라 바라보는 방향을 정해줍니다.

// solve 함수 내의 if문
if(cctv[a][0]==1) { // 카메라 종류 1
    if(cctv[a][3]==1) { // 방향 왼쪽
        left(x, y);
    } else if(cctv[a][3]==2) { // 방향 오른쪽
        right(x, y);
    } else if(cctv[a][3]==3) { // 방향 위쪽
        up(x, y);
    } else if(cctv[a][3]==4) { // 방향 아래쪽
        down(x, y);
    } 
}

 이렇게 해주면 백트래킹 중간에 다시 리스트의 값을 변경시키지 않아도 되기 때문에 복잡함이 덜해집니다.

이렇게 일단 cctv의 종류에 상관없이 전부 4가지로 치게되면 8개 cctv를 결정하는 경우의 수는 4^8 = 32가지 입니다.

 

2-2) 해결

사용된 메소드 수: 총 8개

1. main - 메인
2. func - 백트래킹
3. solve - func에서 호출, 백트래킹이 완료된 경우 실행

// 4-1 ~ 4-4는 solve 내에서 호출
4-1. left // 현재 카메라 기준으로 왼쪽에 -1을 넣음
4-2. right // 현재 카메라 기준으로 오른쪽에 -1을 넣음
4-3. up // 현재 카메라 기준으로 위쪽에 -1을 넣음
4-4. down // 현재 카메라 기준으로 아래쪽에 -1을 넣음

5. checkMin - solve에서 호출, 현재 리스트에 있는 0의 수를 세고 최소값 저장

 

---

3. 코드(JAVA) 

메소드를 여러개 만들었음에도 코드가 200줄이 넘어갑니다.. ㅠㅠ

자세한 설명은 주석으로 적어두었습니다.

import java.io.*;
import java.util.*;

public class Main {
	static int[][] cctv;
	static int[][] list;
	static boolean[][] isUsed;
	static int N, M, cnt, min;
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N= Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		list = new int[N][M];
		cctv = new int[8][4]; // 카메라의 최대 개수는 8개, 하나의 카메라에 대해 저장할 정보는 4가지
		cnt = 0; // 확인 할 카메라의 수
		min = Integer.MAX_VALUE; // 출력할 최소값
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				list[i][j] = Integer.parseInt(st.nextToken());
				if(list[i][j] > 0 && list[i][j] < 6) {
					cctv[cnt][0] = list[i][j]; // 카메라의 정보(1번, 2번, 3번, 4번, 5번)
					cctv[cnt][1] = i; // 카메라의 x좌표
					cctv[cnt][2] = j; // 카메라의 y좌표
					cctv[cnt][3] = 1; // 카메라가 바라보고 있는 방향(1_왼쪽, 2_오른쪽, 3_위쪽, 4_아래쪽)
					cnt++; 
				}
			}
		}

		func(0);
		bw.write(Integer.toString(min));
	
		br.close();
		bw.close();
	}
	
	/**
	 * 백트래킹
	 * @param k 현재 비춰야 할 카메라 번호(현재 방향을 결정한 cctv 개수)
	 */
	public static void func(int k) {
		if(k == cnt) { // 모든 카메라를 검사한 경우
			solve();
			return;
		}
		
		// cctv의 방향을 1~4로 설정(왼_1, 오_2, 위_3, 아래_4를 설정)
		// cctv의 구체적인 방향을 정하는 것이 아니라, 한 곳에서 cctv가 비출 수 있는 방향을 기준으로 1~4를 적음
		for(int dir = 1; dir < 5; dir++){
		  cctv[k][3] = dir;
		  func(k+1);
		}
	}
	
	/**
	 * 각 카메라별 위치를 설정한 경우
	 * 백트래킹의 각 종착점에 실행됨 
	 */
	public static void solve() {
		
		int[][] saveList = new int[N][M]; // 카메라가 비추는 곳에 -1을 넣을 것이므로 기존의 배열이 변형되기 때문에 미리 저장해둠

		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				saveList[i][j] = list[i][j];
			}
		}
		for(int a=0; a<cnt; a++) {
			int x = cctv[a][1];
			int y = cctv[a][2];
			if(cctv[a][0]==1) { // 카메라 종류 1~5개
				if(cctv[a][3]==1) { // 방향 왼쪽
					left(x, y);
				} else if(cctv[a][3]==2) { // 방향 오른쪽
					right(x, y);
				} else if(cctv[a][3]==3) { // 방향 위쪽
					up(x, y);
				} else if(cctv[a][3]==4) { // 방향 아래쪽
					down(x, y);
				} 
			} else if(cctv[a][0]==2) {
				if(cctv[a][3]==1) { // 방향 왼쪽, 오른쪽
					left(x, y);
					right(x, y);
				} else if(cctv[a][3]==2) { // 방향 위쪽, 아래쪽
					up(x, y);
					down(x, y);
				} 
			} else if(cctv[a][0]==3) {
				if(cctv[a][3]==1) {
					left(x, y);
					up(x, y);
				} else if(cctv[a][3]==2) {
					right(x, y);
					up(x, y);
				} else if(cctv[a][3]==3) { 
					left(x, y);
					down(x, y);
				} else if(cctv[a][3]==4) {
					right(x, y);
					down(x, y);
				}  
			} else if(cctv[a][0]==4) {
				if(cctv[a][3]==1) { // 방향 왼쪽
					up(x, y);	
					left(x, y);
					right(x, y);
				} else if(cctv[a][3]==2) { // 방향 오른쪽
					right(x, y);
					up(x, y);
					down(x, y);
				} else if(cctv[a][3]==3) { // 방향 위쪽
					down(x, y);
					left(x, y);
					right(x, y);
				} else if(cctv[a][3]==4) { // 방향 아래쪽
					left(x, y);
					up(x, y);
					down(x, y);
				} 
			} else if(cctv[a][0]==5) {
				left(x, y);
				right(x, y);
				up(x, y);
				down(x, y);
			}
		}
		
		checkMin(); // list에 0의 개수를 세고 가장 적은 0의 개수를 min값으로 설정  

		// 변형된 list의 값을 미리 저장해두었던 saveList로 원상복구함
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				list[i][j] = saveList[i][j];
			}
		}
	}
	
	/**
	 * 카메라가 왼쪽을 비추는 경우 
	 * @param x 카메라의 x좌표
	 * @param y 카메라의 y좌표
	 */
	public static void left(int x, int y) {
		for(int i=x; i>=0; i--) {
			if(list[i][y] == 6) break;
			if(list[i][y] == 0) {
				// 카메라가 보고 있는 경우: -1
				list[i][y] = -1;
			}
		}
	}

	/**
	 * 카메라가 오른쪽을 비추는 경우 
	 * @param x 카메라의 x좌표
	 * @param y 카메라의 y좌표
	 */
	public static void right(int x, int y) {
		for(int i=x; i<N; i++) {
			if(list[i][y] == 6) break;
			if(list[i][y] == 0){
				list[i][y] = -1;
			}
		}
	}

	/**
	 * 카메라가 위쪽을 비추는 경우 
	 * @param x 카메라의 x좌표
	 * @param y 카메라의 y좌표
	 */
	public static void up(int x, int y) {
		for(int j=y; j>=0; j--) {
			if(list[x][j] == 6) break;
			if(list[x][j] == 0) {
				list[x][j] = -1;
			}
		}
	}

	/**
	 * 카메라가 아래쪽을 비추는 경우 
	 * @param x 카메라의 x좌표
	 * @param y 카메라의 y좌표
	 */
	public static void down(int x, int y) {
		for(int j=y; j<M; j++) {
			if(list[x][j] == 6) break;
			if(list[x][j] == 0) {
				list[x][j] = -1;
			}
		}
	}
	
	/**
	 * 0의 개수 확인
	 * list에 0의 개수를 세고 가장 적은 0의 개수를 min값으로 설정
	 */
	public static void checkMin() {
		int sum = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(list[i][j]==0) {
					sum++;
				}
			}
		}
		min = Math.min(sum, min);
		return;
	}
}

백준 15683번 감시 맞았습니다

---

4. 백트래킹에서 잘 못 생각했던 부분

계속 시간 초과가 날 때, 백트래킹 내부에 isUsed 와 for문을 이용했었습니다.

// 수정 전 for문 - 쓸 데 없는 for문을 이용해서 시간초과가 발생합니다.
public static void func(int k) {
      if(k == cnt) {
         solve();
         return;
      }
      
      for(int a=0; a<cnt; a++) {
         int i = cctv[a][1];
         int j = cctv[a][2];
         if(!isUsed[i][j] && list[i][j] > 0 && list[i][j] < 6) {
            isUsed[i][j] = true;
            
            cctv[a][3] = 1;
            func(k+1);
            cctv[a][3] = 2;
            func(k+1);
            cctv[a][3] = 3;
            func(k+1);
            cctv[a][3] = 4;
            func(k+1);
            
            isUsed[i][j] = false;
         }
      }
   }

k값이 현재 카메라를 지정해주므로 for문을 돌릴 필요가 없고, 이로인해 isUsed도 이용 할 필요가 없어집니다.

 

이걸 떠올린건..

왜 계속 시간 초과가 나는 지 헤메고 있었는데, 코딩테스트 장인 친구가 열심히 피드백을 해주었습니다..

기록용으로 더보기에 피드백 내용 첨부합니다..

/**
 * 백트래킹 안에 반복문이 이상함
 * k 값이 현재 결정할 cctv의 인덱스 값임을 몰랐던거 같음
 * isUsed의 2차원 배열 형태도 사실 불필요
 * 뭔가 저번에도 그렇고 2차원 배열에서 하는 백트래킹 문제가 나올 때
 * 그 위치 값으로 isUsed를 매핑하는 것이 굳이 필요한지 확인할 필요가 있음
 * 이번엔 이렇게 해도 이미 위치에 대한 정보가 있으므로 시간복잡도 상 문제는 없긴함 ( 공간복잡도엔 문제가 있음 )
 * [ 문제점 ]
 * 1. 반복문이 8번 돌아감
 * 2. 이 문제의 백트래킹에선 방문 배열이 필요하지 않음
 * 3. N, M의 크기가 커지면 공간복잡도상 문제가 무조건 생김(이 문제에선 해당 사항 없음)
 * 
 * 
 * 반복문이 8번 돌아가는건 큰 시간적 낭비가 될 가능성이 큼
 * 그리고 이미 한번 봤었던 경우의 수를 다시 한 번 보게됩니다.
 * 
 * k란 현재 방향을 결정한 cctv 개수라는 의미입니다.
 * 각 cctv 정보에 대한 변수는 선형 자료형에 저장되어있고,
 * 이를 잘 생각해보면 0 ~ k-1번 째 cctv는 방향이 이미 결정되었다고 해석할 수 있습니다.
 * 즉 그렇다면 k번째 cctv는 아직 방향이 결정되어있지 않다는 것이 자명하죠, 
 * func(int k)에서 우리는 k번째 cctv의 방향만 결정해주면 됩니다.
 * 
 * 따라서 현재 백트래킹은 불필요한 연산이 너무 많고, 반복문이 결국엔 8번 돌아가니깐
 * 최대 8번 스택에 8번 반복하는데 4번 재귀 호출 -> 정확한건 아닌데 32^8 정도의 경우의 수 
 * O(32^8) = 1,099,511,627,776
 * @param k 현재 방향을 결정한 cctv 개수 
 */
public static void func(int k) {

 

---

5. 바킹독님의 풀이

https://youtu.be/jZwf4OPlhtk?si=DLswLg3et1G7w0Gk

초반에 감시 부분의 해설이 나옵니다.

카메라의 방향을 정할 때 4진수를 이용하고, 

위에서 만들었던 left, right, up, down 메소드를 upd라는 하나의 함수로 해결하는 풀이가 담겨있습니다.

---

이 문제를 풀기까지 꽤많은 시간이 걸려서 .. 꼭 정리해야겠다고 생각했습니다..

백트래킹에 대해 좀 더 잘 알게된 문제여서 뜻 깊다고 생각합니다..!!