[백준] 14939 불 끄기 - 비트마스킹(BitMasking) + 그리디(Greedy) + 순서강제하기 JAVA

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

 

코드설명

비트마스킹(BitMasking) + 그리디(Greedy) 를 활용합니다.

 

처음에 문제를 접했을때, 완전탐색으로 하는 것을 생각했습니다.

하지만, 100개의 전구를 껏다 키면 총 2^100 개의 가짓수가 나오게 됩니다.

 

그렇기에, 그리디 알고리즘을 사용하여 최대한 시간초과를 줄여야 합니다. 그 과정에서 비트마스킹을 활용하여 불필요한 메모리 공간을 줄일 수 있습니다. 비트마스킹을 활용하지 않고, 따로 VISITED 배열을 활용하여서 작업해도 되지만, 비트마스킹을 활용한다면 더 효과적입니다.

 

문제를 풀기 위해서는 아래의 성질을 이해합니다.

어떤 순서로 칸들을 클릭하든 상관이 없습니다. 각 칸의 상태는 자신과 인접한 칸들이 몇번 클릭되었는지에 따라 정해집니다. 따라서 어느 순서대로 클릭을 하건 같은 칸을 같은 횟수로 클릭한다면, 격자의 최종 상태는 변함이 없습니다.

한칸을 두 번 이상 클릭할 필요가 없습니다. 같은 칸을 두 번 클릭하는 것은 결국 한번도 클릭하지 않은 것과 같습니다.

앞에서 칸들을 클릭하는 순서는 상관이 없다는 것을 알았기 때문에, 같은 칸을 두번 이상 클릭하는 것은 아무 소용이 없습니다.

맨 위쪽 맨 왼쪽에서부터 클릭한다고 가정합니다. 즉, 맨 위 칸에서 모든 경우의 수를 만들어가면서 진행합니다.

이렇게 할경우 자연스레, 맨 아래줄칸 외에는 모든 칸이 불을 끈다는 점을 알 수 있습니다.

 

최적화하여 진행할경우,

시간복잡도는 O(2^10) + O(90) 이 됩니다.

기존에 O(2^25)에 비하면, 엄청나게 줄어듭니다.

 

코드를 작성하면서 헷갈렸던 부분들입니다.

 

첫번쨰는, 비트마스킹에 대한 이해입니다.

맨 첫번쨰 칸을 비트마스킹으로 진행했는데,  이 부분은 완탐으로 구현해도 됩니다. 하지만, 그렇게할경우 다른 함수를 만들어서 진행해야하기에 좋지 않습니다.  그러므로 비트마스킹을 활용하는 것을 추천합니다.

 

비트마스킹 구현 중에 처음에 == 1 조건을 넣었습니다. 코드에서 if( (i & (1 << j)) == 1 ) 조건이 == 1이 아닌 > 0이어야 하는 이유는 비트 연산의 결과를 올바르게 판별하기 위해서입니다. 비트 연산에서 i & (1 << j)는 i의 j번째 비트가 1인지 아닌지를 검사합니다. 이때, == 1로 비교하면 j가 0 일때만, 10진수로 변환되어 1이 나옵니다. 그러나 i의 j번째 비트가 1일 때는 j번째 비트가 1이기만 하면 되므로 > 0으로 검사해야 합니다.

다시 말해, i & (1 << j)의 결과는 i의 j번째 비트가 1인 경우 2의 j승 값이 되며, 0이 아닌 어떤 값이라도 됩니다. 그러므로 정확한 조건 검사는 > 0이어야 합니다. 이를 통해 j번째 비트가 1일 경우를 정확히 확인할 수 있습니다.

 

즉, 2진수로 변환하더라도 결국 비트연산자 & 로 반환되는 값은 10진수라는 것 입니다. 그렇기에 조건을 > 0 으로 해야만 합니다.

 

결국 우리는 위의 로직을 가지고 맨 위의 칸을 아무것도 안누르는 방식부터 (i = 0) ~ 모든 칸을 누르는 방식(i=1023)까지 숫자를 통해 모두 불을 킬 수 있습니다.

for(int i=0; i<(1<<10); i++) {

    //첫째줄을 먼저 결정시킵니다. 가장 맨 위줄부터 완성시킵니다.
    for(int j=0; j<10;j++) {
        if( (i & (1 << j)) > 0 ) {
            ret += turnLight(0, j);
        }
    }
    ...
    ...

 

 

두번쨰는, 모든 불이 꺼졌는지 확인합니다. 처음에 모든 경우를 다 확인했지만, 사실 마지막 줄만 확인해도 됩니다.

for(int col=0;col<10;col++) {
    if( map[9][col] == 'O') {
        isAllOff = false;
        break;
    }
}

코드

비트마스킹과 그리디 알고리즘을 사용하여 시간을 단축시킨 코드입니다.

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

public class Main {
	public static int N, M;
	public static int answer = Integer.MAX_VALUE;
	public static char[][] map;
	public static int[] dx = {0,-1,1,0,0};
	public static int[] dy = {0,0, 0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		map = new char[10][10];
		for(int i=0;i<10;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			map[i] = str.toCharArray();
		}
		
//		System.out.println(1 << 1); 1 << 1 : 2 이다. 비트를 왼쪽으로 1번 이동시킨다. 0001 에서 0010으로.
//		System.out.println(Math.pow(2,  10));
		simulate();
//		System.out.println(answer);
	}
	
	public static void simulate() {
		int switchCnt = 0;
		
		char[][] storeMap = new char[10][10];
		for(int i=0;i<10;i++) {
			for(int j=0;j<10;j++) {
				storeMap[i][j] = map[i][j];
			}
		}
		
		//for(int i=0; i<Math.pow(2,  10); i++) {
		//첫번째 행의 모든 가능한 상태를 확정하고, 맨 윗행부터 맨 아랫행까지 차례대로 전구를 꺼진상태로 변경합니다.
		//이때 배열을 통해서도 똑같이 구현가능하지만, 비트마스킹을 활용할경우 코드가 훨씬 간단해집니다.
		for(int i=0; i< (1 << 10) ; i++) {
			switchCnt = 0;
			for(int j=0;j<10;j++) {
				for(int k=0;k<10;k++) {
					map[j][k] = storeMap[j][k];
				}
			}
			
			//첫번쨰 행의 전구를 비트마스킹에 따라 변화시키는 과정입니다.
			for(int c=0; c<10; c++) {
				if( (i & (1 << c)) > 0 ) {
					changeStatus(0, c);
					switchCnt += 1;
				}
			}
			
			for(int r=0; r< 9; r++) {
				for(int c=0; c<10; c++) {
					if(map[r][c] == 'O') {
						changeStatus(r + 1, c);
						switchCnt += 1;
					}
				}
			}
			
			if(isAllLightDown() == true) {
				answer = Math.min(answer, switchCnt);
			}
			
		}
		if(answer == Integer.MAX_VALUE) {
			System.out.println(-1);
		}else {
			System.out.println(answer);
		}
		
		
	}
	//기본적으로 clone()은 얕은복사.(참조 복사)
	//예외로, array에서 clone은 deep copy, 
	
	public static void changeStatus(int r, int c) {
		for(int dir = 0; dir < 5; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			
			if(nr < 0 || nr >= 10 || nc < 0 || nc >= 10) continue;
			map[nr][nc] = (map[nr][nc] == '#') ? 'O' : '#';
		}
	}
	
	public static boolean isAllLightDown() {
		for(int c=0;c<10;c++) {
			if(map[9][c] == 'O') {
				return false;
			}
		}
		return true;
	}
	
}

 

조금 다르게 풀어본 코드(위의 코드와 거의 동일)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static char[][] map;
	public static int[] dr = {0, -1, 1, 0, 0};
	public static int[] dc = {0, 0, 0, -1, 1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		map = new char[10][10];
		for(int i=0;i<10;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			map[i] = st.nextToken().toCharArray();
		}
		
		System.out.println(countSwitchToLightDown());
	}

	//어떤 순서로 칸들을 클릭하든 상관이 없습니다. 각 칸의 상태는 자신과 인접한 칸들이 몇번 클릭되었는지에 따라 정해집니다.
	//따라서 어느 순서대로 클릭을 하건 같은 칸을 같은 횟수로 클릭한다면, 격자의 최종 상태는 변함이 없습니다.
	//한칸을 두 번 이상 클릭할 필요가 없습니다. 같은 칸을 두 번 클릭하는 것은 결국 한번도 클릭하지 않은 것과 같습니다.
	//앞에서 칸들을 클릭하는 순서는 상관이 없다는 것을 알았기 때문에, 같은 칸을 두번 이상 클릭하는 것은 아무 소용이 없습니다.
	//맨 위쪽 맨 왼쪽에서부터 클릭한다고 가정합니다. 즉, 맨 위 칸에서 모든 경우의 수를 만들어가면서 진행합니다.
	public static int countSwitchToLightDown() {
		
		char[][] storeMap = new char[10][10];
		for(int j=0; j<10; j++) {
			for(int k=0; k<10;k++) {
				storeMap[j][k] = map[j][k];
			}
		}
		int ret = 0;
		int minRet = Integer.MAX_VALUE;
		//첫번째 칸을 먼저 완전탐색으로 결정시킵니다. ( 10칸 밖에 없기 떄문에 2^10 개의 연산으로 처리할 수 있습니다. )
		//비트마스킹을 활용하지 않고, Combination 조합으로 진행해도 됩니다.
		//하지만, 비트마스킹을 활용할경우 더 깔끔한 코드가 완성되기에 비트마스킹을 사용합니다.
		for(int i=0; i<(1<<10); i++) {
			ret = 0;
			for(int j=0; j<10; j++) {
				for(int k=0; k<10;k++) {
					map[j][k] = storeMap[j][k];
				}
			}	
			
			//첫째줄을 먼저 결정시킵니다. 가장 맨 위줄부터 완성시킵니다.
			for(int j=0; j<10;j++) {
				if( (i & (1 << j)) > 0 ) {
					ret += turnLight(0, j);
				}
			}
			
			//나머지 줄들을 결정시킬 것 입니다.
			for(int row = 1; row <= 9; row++) {
				for(int col = 0; col <10; col++) {
					if(map[row-1][col] == 'O') {
						ret += turnLight(row, col);
					}
				}
			}

			boolean isAllOff = true;
			//모든 불이 꺼졌는지 확인합니다. 처음에 모든 경우를 다 확인했지만, 사실 마지막 줄만 확인해도 됩니다.
//			for(int row=0;row <10;row++) {
//				for(int col=0;col<10;col++) {
//					if( map[row][col] == 'O') {
//						isAllOff = false;
//						break;
//					}
//				}
//				if(isAllOff == false) break;
//			}
			for(int col=0;col<10;col++) {
				if( map[9][col] == 'O') {
					isAllOff = false;
					break;
				}
			}
			
			if(isAllOff == true)
				minRet = Math.min(minRet, ret);
		}
		return minRet;
	}
	
	public static int turnLight(int r, int c) {
		for(int dir = 0; dir < 5; dir++) {
			int nr = r + dr[dir];
			int nc = c + dc[dir];
			if(nr < 0 || nr >= 10 || nc < 0 || nc >= 10 ) continue;
			if( map[nr][nc] == '#') map[nr][nc] = 'O';
			else map[nr][nc] = '#';
		}
		return 1;
	}

}

 

완전탐색코드(시간초과)

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

public class Main {
	public static int N, M;
	public static int answer = Integer.MAX_VALUE;
	public static char[][] map;
	public static int[] dx = {0,-1,1,0,0};
	public static int[] dy = {0,0, 0,-1,1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		map = new char[10][10];
		for(int i=0;i<10;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			map[i] = str.toCharArray();
			
//			for(int j=0;j<10;j++) {
//				System.out.print(map[i][j]);
//			}
//			System.out.println();
		}
		
		simulate(0, 0, 0, 0);
		System.out.println(answer);
	}
	
	public static void simulate(int level, int r, int c, int switchCnt) {
//		System.out.println("==============");
//		for(int i=0;i<10;i++) {
//			for(int j=0;j<10;j++) {
//				System.out.print(map[i][j]);
//			}
//			System.out.println();
//		}
		if(level == 100) {
			if(isAllDown() == true) {
				answer = Math.min(answer, switchCnt);
			}
			return ;
		}
		
		if( r >= 10 ) {
			r = 0;
			c = c + 1;
		}
		
		char[][] storeMap = new char[10][10];
		for(int i=0;i<10;i++) {
			for(int j=0;j<10;j++) {
				storeMap[i][j] = map[i][j];
			}
		}
		
		//전구의 색깔을 바꾸는 경우
		changeStatus(r, c);
		simulate(level + 1, r, c + 1, switchCnt + 1);
		
		
		//전구의 색깔을 바꾸지 않는 경우
		for(int i=0;i<10;i++) {
			for(int j=0;j<10;j++) {
				map[i][j] = storeMap[i][j];
			}
		}
		simulate(level + 1, r, c + 1, switchCnt);
		
		
	}
	public static void changeStatus(int r, int c) {
		for(int dir = 0; dir < 5; dir++) {
			int nr = r + dx[dir];
			int nc = c + dy[dir];
			
			if(nr < 0 || nr >= 10 || nc < 0 || nc >= 10) continue;
			map[nr][nc] = (map[nr][nc] == '#') ? 'O' : '#';
		}
	}
	
	public static boolean isAllDown() {
		for(int i=0;i<10;i++) {
			for(int j=0;j<10;j++) {
				if(map[i][j] == 'O')
					return false;
			}
		}
		
		return true;
	}
	
	
}

class Node{
	int r;
	int c;
}