[백준] 5547 일루미네이션 - BFS + 아이디어 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;
	}
}