[백준] 5547 일루미네이션 - BFS(너비우선탐색) + 아이디어(Idea) JAVA

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

5547번: 일루미네이션

 

문제풀이

BFS 문제인데, 어느정도 아이디어를 떠올려야 풀 수 있는 문제였습니다.

이 문제의 가장 큰 중요한 아이디어는,

1. 벽이 존재하지 않는 곳에서 BFS를 돌면서 정육면체 6방향 (좌, 좌상, 우상, 우, 우하, 좌하)을 확인하며 해당 방향에 벽이 존재하는지 확인하고, 벽의 개수를 result[][] 에 저장한뒤 마지막에 result에 저장된 모든 수를 더하면 변의 개수를 알 수 있습니다.

2. 정육각형이지만, 입력값은 직사각형 형태로 주어지기에 X와 Y값을 계산하는것이 포인트입니다.

//좌, 좌상, 우상, 우, 우하, 좌하  ( 시계방향 )
    	int OddDir[][] = { {0, -1}, { -1,  0}, {-1, 1}, {0, 1}, {1,  1}, {1, 0}};//홀수 행
        int EvenDir[][] = { {0, -1}, { -1, -1}, {-1, 0}, {0, 1}, {1, 0}, {1, -1}};//짝수 행

위 코드처럼 짝수와 홀수의 x와 y의 이동위치가 다르므로, 위처럼 이동방향을 정합니다.

추가로, 행과 열이 바뀌었으므로 일반적으로 행과 열을 구하듯이 하면안되고, 구한뒤에 행과 열을 대칭이동(y=x대칭) 시켜줘야합니다.

(문제를 풀다가 도중에 행과 열이 바뀐 값인것을 알아차려서 코드에는 단순히 H와 W를 반대로 입력하게 하여, 처리를 했습니다. 원래는 W와 H 순서로 받은뒤 new int[H+2][W+2] 로 하면됩니다.)

 

이 문제에서 어떻게 변의 개수를 구할까 고민했는데 이떄, 마지막 정육각형 벽들은 벽의 개수를 구하기 힘드므로,

map[H+2][W+2] 이렇게 추가로 벽을 만들어주어 BFS를 시작하면 무조건 map의 테두리에는 지나갈 수 있는 공간이 있기에 해당 아이디어를 떠올리는것이 중요했습니다.

 

코드

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

public class Main {
	
	public static int W, H;
	public static int[][] map;
	public static int[][] result;
	static boolean[][] visited;

    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	//W : 행, H : 열
    	H = Integer.parseInt(st.nextToken());
    	W = Integer.parseInt(st.nextToken());
    	
    	
    	//외벽과 닿는 모든 면을 정육각형으로 둘러주기 위해 +2 를 합니다.
    	// 0 (흰색부분) 으로 둘러쌓이게 처리하는 것 입니다.
    	map = new int[W+2][H+2];
    	visited = new boolean[W+2][H+2];
    	result = new int[W+2][H+2];
    	for(int i=1;i<=W;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=1;j<=H;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    			if(map[i][j] == 1) {
    				visited[i][j] = true;
    			}
    		}
    	}
    	
    	BFS(0,0);
    	
    	int answer = 0;
    	for(int i=0; i<W+2; i++) {
    		for(int j=0;j<H+2;j++) {
    			answer += result[i][j];
    		}
    	}
    	
    	System.out.println(answer);
    } 
    
    public static void BFS(int startx, int starty) {
    	
        //좌, 좌상, 우상, 우, 우하, 좌하  ( 시계방향 )
    	int OddDir[][] = { {0, -1}, { -1,  0}, {-1, 1}, {0, 1}, {1,  1}, {1, 0}};//홀수 행
        int EvenDir[][] = { {0, -1}, { -1, -1}, {-1, 0}, {0, 1}, {1, 0}, {1, -1}};//짝수 행
    	Queue<Node> q = new LinkedList<>();
    	q.add(new Node(startx, starty));
    	visited[startx][starty] = true;
    	
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int x = temp.x;
    		int y = temp.y;
    		
    		for(int dir=0;dir<6;dir++) {
    			int nx = 0;
    			int ny = 0;
    			if(x %2 == 1) {
    				nx = x + OddDir[dir][0];
    				ny = y + OddDir[dir][1];
    			}else {
    				nx = x + EvenDir[dir][0];
    				ny = y + EvenDir[dir][1];
    			}
    			
    			if( nx < 0 || nx >= W + 2 || ny < 0 || ny >= H + 2) continue;
    			if(map[nx][ny] == 1) {
    				result[x][y] += 1;
    				continue;
    			}
    			//이미 간곳은 visited[nx][ny] =true로 수정하여 중복안되게 합니다.
    			if(visited[nx][ny] == true) continue;
    			visited[nx][ny] = true;
    			q.add(new Node(nx, ny));
    		}
    	}
    }
    
}

class Node{
	int x; 
	int y;
	public Node(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

 

시간이 오래 걸리는 코드입니다.

위의 코드와 반대로, 벽 안의 0 을 1로 채워준뒤, 벽 기준으로 0 의 개수를 세어나갑니다.

위의 코드와 비교하여 시간이 더 소요됩니다. (각 점을 기준으로 모두 BFS를 실행하기 떄문입니다.) 위의 코드는 1번의 BFS로 모두 Counting 할 수 있습니다.

package Main;

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

public class Main {
	private static int N, W, H;
    private static int[][] arr;
    private static int answer = 0;
    private static int[][] dr = {
    		{-1, -1, 0, 0, 1, 1},
    		{-1, -1, 0, 0, 1, 1}
    };
    private static int[][] dc = {
    		{0, 1, -1, 1, 0, 1},
    		{-1, 0, -1, 1, -1, 0}
    };
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        W = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        arr = new int[H][W];
        for(int i=0;i<H; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j=0;j<W; j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken()); 
        	}
        }
        
        for(int i=0;i<H; i++) {
        	for(int j=0;j<W; j++) {
        		if(arr[i][j] == 0) {
        			//만약 나갈 수 있다면, 1로 감싸져있지 않으므로 0 으로 여전히 유지합니다.
        			//나갈 수 없다면 1로 감싸져있으므로 벽으로 인식합니다.
        			arr[i][j] = isBlockOut(i, j) == true ? 0 : 1;
        		}
        	}
        }
        
        boolean[][] visited;
        visited = new boolean[H][W];
        for(int i=0;i<H; i++) {
        	for(int j=0;j<W; j++) {
        		if(arr[i][j] == 1) {
        			answer += func(i, j, visited);
        		}
        	}
        }
        
        System.out.println(answer);
    }
    private static boolean isBlockOut(int sr, int sc) {
    	Queue<Node> q = new LinkedList<>();
    	q.offer(new Node(sr, sc));
    	boolean[][] visited = new boolean[H][W];
    	visited[sr][sc] = true;
    	while(!q.isEmpty()) {
    		Node temp = q.poll();
    		int or = temp.r;
    		int oc = temp.c;
			for(int dir =0 ; dir < 6; dir++) {
				int nr = or + dr[or%2][dir];
				int nc = oc + dc[or%2][dir];

				if(nr < 0 || nr >= H || nc < 0 || nc >= W) return true;
				if(visited[nr][nc] == true) continue;
				if(arr[nr][nc] == 1) continue;
				visited[nr][nc] = true;
				q.offer(new Node(nr, nc));
			}
    	}
    	return false;
    }
    
    private static int func(int sr, int sc, boolean[][] visited) {
    	int ret = 0;
    	//만약 짝수라면
		for(int dir = 0; dir < 6; dir++) {
			int nr = sr + dr[sr%2][dir];
			int nc = sc + dc[sr%2][dir];
			
			if(nr < 0 || nc < 0 || nr >= H || nc >= W) {
				ret += 1;
				continue;
			}
			else if( arr[nr][nc] == 0 ) {
				ret += 1;
			}
		}

		return ret;
    }
    
}
class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r=r;
		this.c=c;
	}
}


//private static boolean isBlockOutDFS(int sr, int sc, boolean[][] visited) {
//
//boolean ret = false;
//visited[sr][sc] = true;
//for(int dir =0; dir<6; dir++) {
//	int nr = sr + dr[sr%2][dir];
//	int nc = sc + dc[sr%2][dir];
//	
//	//만약 밖에 나갈 수 있으면 밖과 연결되있으므로 true를 반환한다.
//	if(nr < 0 || nr >= H || nc < 0 || nc >= W) return true;
//	
//	//만약 벽이라면 무시한다.
//	if(arr[nr][nc] == 1) continue;
//	//만약 이미 방문한 적 있다면, 무시한다.
//	if(visited[nr][nc] == true) continue;
//	visited[nr][nc] = true;
//	
//	//만약 한개라도 true라면, 
//	ret = ret | isBlockOutDFS(nr, nc, visited);
//	visited[nr][nc] = false;
//}
//
////만약 한개라도 못나갔다면, 시작구간을 벽으로 채우면 된다.
//if(ret == false) {
//	arr[sr][sc] = 1;
//}
//visited[sr][sc] = false;
//return false;
//}

 

처음에 DFS를 활용해서 최대한 isBlockOutDFS의 작동시간을 줄일려고 했습니다.

하지만, 이 방법의 경우 만약 해당 dfs 방향에서 실패한 경우가 생긴다면, 그 재귀함수 호출이 끝나면서 호출한 부분 모두가 벽으로 칠해지면서 잘못된 연산이 생깁니다. 4가지 방향으로 각기 다른 방식으로 작동한다는점을 기억해야 합니다.

private static boolean isBlockOutDFS(int sr, int sc, boolean[][] visited) {

boolean ret = false;
visited[sr][sc] = true;
for(int dir =0; dir<6; dir++) {
	int nr = sr + dr[sr%2][dir];
	int nc = sc + dc[sr%2][dir];
	
	//만약 밖에 나갈 수 있으면 밖과 연결되있으므로 true를 반환한다.
	if(nr < 0 || nr >= H || nc < 0 || nc >= W) return true;
	
	//만약 벽이라면 무시한다.
	if(arr[nr][nc] == 1) continue;
	//만약 이미 방문한 적 있다면, 무시한다.
	if(visited[nr][nc] == true) continue;
	visited[nr][nc] = true;
	
	//만약 한개라도 true라면, 
	ret = ret | isBlockOutDFS(nr, nc, visited);
	visited[nr][nc] = false;
}

//만약 한개라도 못나갔다면, 시작구간을 벽으로 채우면 된다.
if(ret == false) {
	arr[sr][sc] = 1;
}
visited[sr][sc] = false;
return false;
}