BFS_5547_일루미네이션_육각행렬

최근에 네이버 공채를 지원해보고, 코딩테스트를 보았다. 나름 준수하게 푼 것 같긴 한데, 생각보다 애먹었던 내용과 비슷했던 문제를 다시 풀어보고자 한다. 너비우선탐색을 진행하는데, 실제탐색은 2차원 배열로 진행하지만, 각 요소가 익숙했던 정사각형이 아닌 정육각형으로 이질감이 있게 생겼다. 물론 이에 따라서 이동가능한 경우의 수도 (상, 하, 좌, 우) 4가지에서 (좌, 좌상, 좌하, 우, 우상, 우하)6가지로 바뀌었다는 점, 더불어 현재 행이 짝수인지, 홀수인지에 따라서 이동하는 위치가 다르다는 것이다. 말로만 설명하면 어려우니 간단한 예시를 보자.

문제에서 예시로 주어진 그림을 보면 척 봐도 모든게 복잡하다. 일단 그림부터도 불편하긴 한데, 행과 열이 거꾸로 되어 있기까지 하다니,,, 하지만 이는 모양만 맞추어 주면 되고, 가장 중요한 것은 이동방향이다. 

행이 짝수일 때와 홀수 일때를 나누어서 (x,y)를 기준으로 생각해보자.

아래의 표가 일반화된 식은 아니다. 필자는 후에 행과 열을 문제에서와는 반대로 원래 우리에게 익숙했던 역행렬로 바꿀 것이기 때문에 달라질 수 있다. 지금은 이동하는 방식만을 먼저 익혀보자

이동방향	좌	좌상	좌하	우	우상	우하
홀수	(x-1, y)	(x, y-1)	(x, y+1)	(x+1, y)	(x+1, y-1)	(x+1, y+1)
짝수	(x-1, y)	(x-1, y-1)	(x-1, y+1)	(x+1, y)	(x, y-1)	(x, y+1)

 

자, 이동방향은 위와 같은 방식으로 하기로 하고, 이제는 문제를 풀기 위한 방법을 생각해보자. 

고려해야 하는 점은 건물의 외벽에 칠해진 수만 세야 하고, 내벽은 무시해야 한다는 것이다. 따라서 필자는 다음과 같은 생각으로 접근을 했다. 

1. 회색으로 칠해진 건물은 값이 1로 표현되어 있으니, map을 초기화 할때, 값이 1이라면 미리 방문 처리한다. 
2. (0, 0)부터 bfs탐색을 시작한다. 이때, map의 값이 0인 것만 탐색을 한다.
3. 현재 위치에서 이동할 수 있는 6방향 중, 이미 방문한 곳을 제외하고, 탐색을 진행했을 때, 인접한 곳이 건물이 있는 곳이라면 현재위치에 +1한다.
   1. 예를 들어, 하나의 위치에서 우, 우상, 우하 이렇게 세 방향에 인접한 건물의 외벽이 색칠되어 있다면, 현재위치++이 3번이 진행되는 것이다. 탐색을 마치고 나서 더해진 값을 모두 더하면 외벽의 전체 길이가 나온다. 

방문을 모두 마치게 되면, 따로 만들어 놓은 배열에는 아래와 같이 숫자가 마킹되어 있을 것인데 이를 모두 더한다. 

 

[ 소스코드 ]

package BFS;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class _5547_일루미네이션 {
                                //좌       좌상       우      우하    좌하    우상
    static int moveOdd[][]  = { {0, -1}, { -1,  0}, {0, 1}, {1, 1}, {1,  0}, {-1, 1}};//홀수 행
    static int moveEven[][] = { {0, -1}, { -1, -1}, {0, 1}, {1, 0}, {1, -1}, {-1, 0}};//짝수 행
    static int map[][];
    static int isInjac[][];
    static boolean visit[][];
    static int w, h;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        //열(w), 행(h)
        w = Integer.parseInt(st.nextToken());
        h = Integer.parseInt(st.nextToken());
        
        map     = new int[h+2][w+2];
        isInjac = new int[h+2][w+2];
        visit   = new boolean[h+2][w+2];
        
        for(int i=1; i<=h; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=w; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1) {
                    visit[i][j] = true;
                }
            }
        }
        
        bfs(0,0);
        
        int ans = 0;
        for(int i=0; i<isInjac.length; i++) {
            for(int j=0; j<isInjac[i].length; j++) {
                if(isInjac[i][j] == 0) continue;
                ans += isInjac[i][j];
            }
        }
        
        System.out.println(ans);
        
        /*
         * for(int a[] : isInjac) { for(int aa : a) { System.out.print(aa + " "); }
         * System.out.println(); }
         */
    }
    
    private static void bfs(int x, int y) {
        // TODO Auto-generated method stub
        Queue<hex> q = new LinkedList<hex>();
        q.add(new hex(x, y));
        visit[x][y] = true;
        
        while(!q.isEmpty()) {
            hex now = q.poll();
            int nextX = 0;
            int nextY = 0;
            
            for(int i=0; i<6; i++) {
                if(now.x % 2 == 0) {//현재위치의 y가 짝수라면
                    nextX = now.x + moveEven[i][0];
                    nextY = now.y + moveEven[i][1];
                }else {//현재 위치의 y가 홀수라면
                    nextX = now.x + moveOdd[i][0];
                    nextY = now.y + moveOdd[i][1];
                }
                
                //조건 설정하기
                if(nextX <0 || nextY < 0 || nextX >= h+2 || nextY >= w+2) continue;
                
                if(map[nextX][nextY] == 1) {
                    isInjac[now.x][now.y]++;
                    continue;
                }
                
                if(visit[nextX][nextY] || isInjac[nextX][nextY] != 0) continue;
                
                
                visit[nextX][nextY] = true;
                q.add(new hex(nextX, nextY));
                
            }
        }
    }
}
class hex{
    int x, y;
    public hex(int x, int y) {
        this.x = x;
        this.y = y;
    }
}