[JAVA] 백준 15683번: 감시

🔗 문제

15683번: 감시

15683번: 감시

 

입력

첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다.

CCTV의 최대 개수는 8개를 넘지 않는다.

출력

첫째 줄에 사각 지대의 최소 크기를 출력한다.

 

 

✏️ 풀이

 

먼저 문제 정리 부터 한다.

 

[맵이 가질 수 있는 상태]

• EMPTY : 0 (사각지대)
• CCTV : 1 ~ 5
• WALL : 6
• 감시구역 : -1

[CCTV의 감시]

• CCTV는 자신이 가진 type에 따라 감시 방향이 다르다.
• CCTV는 감시하다가 CCTV보이면 무시하고 진행한다.
• CCTV는 감시는 벽을 통과할 수 없다.
• CCTV의 방향이 정해진게 아니라 90도씩 회전이 가능하다.
  • 즉, 각 타입마다 탐색해야할 방향이 바뀐다.

---

• 맵의 크기가 8x8이라는 점
• cctv 위치가 미리 정해져있고 많아봤자 8개라는 점

cctv 방향을 틀면서 dfs로 완전 탐색을 해도 무리가 없겠구나 !!

---

 

메서드 만들기

 

이 문제에서 필요한 행위들은 무엇일까?

 

solve()

먼저 각 cctv들의 방향을 골라가면서 완전 탐색할 함수가 필요하다. (dfs)

이 함수는 내부에서 현재 보고 있는 cctv의 type에 맞게 방향을 틀어줘야 한다.

그리고 다음 cctv를 고르기 위해 재귀함수를 호출한다.

• 기저 조건 : 모든 cctv를 고를 때까지
•  

change()

고르기만 하면 되나? 아니다. cctv가 감시를 얼마나 잘 하고 있는지 길을 감시하는 cctv를 감시를 해주자

• 어느 타입의 어느 위치에 있는 cctv가 어떤 방향으로 감시하고 있나요?
• 사각 지대를 셀 때 구분할 수 있는 표시도 해주자 (개선사항 참고)

 

---

---

<< 개선 전>>

dfs에서 cctv를 고를 때마다 감시 구역을 표기하는 방식을 선택했다. (map값을 변경 시킴)

맵이 작기 때문에 그냥 미리 복사해서 덮어쓰는 방식을 선택했다.이유는 구현이 쉬워서였다. 하지만 이렇게 되면 재귀가 리턴되고 나서 다른 분기로 갈 때 다시 복구해줘야 한다. 어떻게 다시 되돌릴까???

 

 

🤔 만약 맵이 작지 않았더라면?

바로 맵을 바꾸지 않고 방향에 따라 감시할 수 있는 구역을 저장했을 것 같다.

모든 cctv 방향을 정하고 나서야 하나씩 값을 꺼내서 map을 바꾸고 바꾼 곳만 복귀하는 식

또 이렇게 하면 회전할 때 마다 중복되는 방향 감시도 효율있게 처리할 수 있을 것 같다

 

 

<< 개선 후>>>

더 좋은 방법을 찾아서 개선해보았다.

 

변경된 좌표를 저정하는 것도 아니고 모든 맵을 순회하는 방법이 아니다.

• cctv가 감시하는 구역이 빈 곳이었다면 1씩 감소시킨다.
• 탐색이 끝났다면 “봤던 방향”의 구역이 음수라면 1씩 증가시켜 복구시킨다.

이렇게 하면 이전에 배열을 계속해서 생성해서 덮어썼던 것도 해결되어 메모리도 줄일 수 있고,

모든 N*M이 아닌 변경된 부분만 보기 때문에 시간을 1/2이나 줄일 수 있었다.

 

---

 

cctv type에 맞는 방향 고르기

 

상하좌우 정보를 갖는 배열을 만들어보자.

final static int dx[] = {0, -1, 0, 1};
final static int dy[] = {-1, 0, 1, 0};

 

type은 상하좌우 각 1개씩, 2개씩, 3개씩, 4개씩 쓰기도 한다.

type에 맞는 방향을 찾기 위해 반복문으로 적절하게 인덱스를 +1, +2해서 맞춰준다.

이러면 인덱스의 범위를 초과하는 경우가 있는데

• 상하좌우 순서로 된 배열에서 우상하 순서로 접근할 때..

 

그냥 나머지 연산을 해줘서 보정해주면 잘 된다.

타입에 따라 봐야할 방향을 미리 저장해서 반복문을 대체하는 방법도 있다.

하지만 나중에 내 코드를 못 알아볼 것 같아서 적당히 나와 타협했다 :-)

 

---

🧠 아직도 남은 개선점

회전을 할 때, 반복되는 연산이 있다.

type 3이나 4에서 이미 봤던 방향에서 방향이 바뀌었다고 또 돌기 때문이다.

이 부분을 개선한다면 더 효율적일 것 같다.

 

개선점은 아니지만 변경되는 map을 매개변수로 주다가 소스가 복잡해보여서 전역변수로 변경했더니, 시간을 좀 더 소비했다. 하지만 이 또한 나와 타협했다.

 

 

💾  소스

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static StringBuilder sb;
	static StringTokenizer st;
	static BufferedReader br;

	final static int dx[] = {0, -1, 0, 1};
	final static int dy[] = {-1, 0, 1, 0};
	
	static int map[][];
	static int N, M, answer = Integer.MAX_VALUE;
	static List<Pair> cctv;

	static boolean isValid(final int x, final int y)
	{
		if(x<0 || y<0 || x>=N || y>=M)
			return false;
		return true;
	}
	
	
	static class Pair
	{
		int x, y;

		public Pair(int x, int y)
		{
			super();
			this.x = x;
			this.y = y;		
		}
	}
	
	//################################################################################

	static void change(final int idx, final int d, final boolean isPlus)
	{	
		int x = cctv.get(idx).x + dx[d];
		int y = cctv.get(idx).y + dy[d];
		
		while(isValid(x, y) && map[x][y] != 6)
		{
            if(isPlus && map[x][y] < 0) ++map[x][y];
			else if(!isPlus && map[x][y] <= 0) --map[x][y];
			
			x += dx[d];
			y += dy[d];
		}
	}
	
	static int countArea()
	{
		int result = 0;
		for(int i=0; i<N; ++i)
		{
			for(int j=0; j<M; ++j)
			{
				if(map[i][j] == 0) ++result;
			}
		}
		return result;
	}
	
	static void solve(final int idx)
	{
		if(idx == cctv.size())
		{
			int tmp = countArea();
			answer = (answer < tmp ? answer : tmp);
			return;
		}
		
		int x = cctv.get(idx).x;
		int y = cctv.get(idx).y;
		int type = map[x][y];
		
		if(type == 1)
		{
			for(int d=0; d<4; ++d)
			{
				change(idx, d, false);
				solve(idx+1);
				change(idx, d, true);
			}
		}
		else if(type == 2)
		{
			for(int d=0; d<4; ++d)
			{
				change(idx, d, false);
				change(idx, (d+2)%4, false);
				solve(idx+1);
				change(idx, d, true);
				change(idx, (d+2)%4, true);
			}
		}
		else if(type == 3)
		{
			for(int d=0; d<4; ++d)
			{
				change(idx, (d)%4, false);
				change(idx, (d+1)%4, false);
				solve(idx+1);
				change(idx, (d)%4, true);
				change(idx, (d+1)%4, true);
			}
		}
		else if(type == 4)
		{
			for(int d=0; d<4; ++d)
			{
				change(idx, d, false);
				change(idx, (d+1)%4, false);
				change(idx, (d+2)%4, false);
				solve(idx+1);
				change(idx, d, true);
				change(idx, (d+1)%4, true);
				change(idx, (d+2)%4, true);
			}
		}
		else if(type == 5)
		{
			for(int d=0; d<4; ++d)
			{
				change(idx, d, false);
			}
			solve(idx+1);
		}
		
	}

	public static void main(String[] args) throws IOException {
	
		br = new BufferedReader(new InputStreamReader(System.in));
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		map = new int[N][M];
		cctv = new ArrayList<Pair>();
		
		for(int i=0; i<N; ++i)
		{
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; ++j)
			{
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] != 0 && map[i][j] !=6)
				{
					cctv.add(new Pair(i, j));
				}
			}
		}
		
		solve(0);
		
		System.out.print(answer);
		
	} // main

	
}