99클럽 코테 스터디 18일차 TIL + [백준] 5547 일루미네이션 java 완벽 설명! ^^

1. 문제 설명

2. 접근 방식

KEY WORD: BFS, IDEA

해당 문제는 문제를 풀기 위한 IDEA만 생각해낸다면 간단한 BFS 문제이다. 문제에 대한 접근 방식은 다음과 같다.

(1) 입력받은 좌표의 변두리 부분도 페인트를 칠할 수 있다. 가령

파란색으로 칠한 부분을 봐라. 만약 입력 좌표 그대로 2차원 배열을 만든다면, 해당 변두리 부분은 배열을 벗어나게 되어, 페인트를 칠할 때 골치가 아파진다. (자칫 잘못하면 OutOfArrayIndex 에러가 나기 때문이다!!)
따라서 우리는 해당 좌표도 배열 내에서 받을 수 있도록 2차원 배열을 테두리까지 넉넉하게 만들고, 여기에 입력받은 좌표값들을 집어넣는다.

int [][] map = new int [row+2][col+2]

그러면 이렇게 받을 수 있다. 파란색으로 칠해진 부분은 변방 테두리로 우리가 넣은 것이다.

(2) 건물이 있는 좌표는 방문 처리 한다.
우리는 외벽의 숫자만 세면 된다. 내가 맨 처음에 하려던 풀이가 건물의 모든 벽을 구해서 내벽을 빼려 했는데, 그 방법은 구현이 쉽지가 않았다. 그 대신 (3)의 방법을 시작하면 쉽다.

(3) (0,0)에서 육방탐색 BFS를 시작한다. 특정 방향의 정점을 탐색했는데 그 정점이 건물 이라면, 외벽 카운트를 +1 올린다. 왜 이렇게 하면 될까? 이유는 다음과 같다.

• (0,0)에서 탐색을 시작하면, 건물로 둘러싸여 내벽이 된 곳은 접근하지 못한다.
• 따라서 바깥에서 만나는 부분은 모두 외벽이 된다.

잠깐! 육방 탐색을 하는 방법은??

해당 문제는 그래프 배치가 6각형 형태로 되어있다.

따라서 BFS로 그래프를 탐색할 때도, 육방 탐색을 해야한다. 문제에서 주어진 사진은 통상적인 2차원 배열의 행과 열을 반대로 적어놔서 헷갈릴 수 있다. 육각형 그래프를 2차원 배열로 표현하고, 정중앙의 값으로 인접 행렬과의 차이를 나타내면 다음과 같다.

육각형 그래프가 짝수행과 홀수행마다 위치가 달라서, 둘을 따로 계산해야함을 잊지 말자.
이제 위에서 정리한 접근 방식을 토대로 문제를 풀어보자.

3. 코드 분석

import java.io.*;
import java.util.*;

public class Main {
    static int [][] forEven = new int[][]{{-1,-1}, {-1,0}, {0,1}, {1,0}, {1,-1}, {0,-1}};
    static int [][] forOdd  = new int[][]{{-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {0,-1}};
    static int paint = 0;

    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br   = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st  = new StringTokenizer(br.readLine());
        int col = Integer.parseInt(st.nextToken());
        int row = Integer.parseInt(st.nextToken());
        int [][] map = new int[row+2][col+2];

        for (int i = 1; i <= row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= col; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bfs(map, 0,0);
        System.out.println(paint);
    }

    public static void bfs(int [][] map, int x, int y) {
        // 미방문 길: 0, 건물:1, 방문 길 2
        ArrayDeque<Coordinate> aq1 = new ArrayDeque<>();
        aq1.add(new Coordinate(x,y));
        map[x][y] = 2;
        while (!aq1.isEmpty()){
            Coordinate now = aq1.poll();
            int [][] direction = (now.row%2 == 0? forEven : forOdd);
            int cnt = 0;
            // 현재 위치에서 6방 검색
            for (int i = 0; i < direction.length; i++) {
                int nRow = now.row + direction[i][0];
                int nCol = now.col + direction[i][1];
                if(nRow >= 0 && nRow < map.length && nCol >= 0 && nCol < map[0].length){
                    // 건물이면 외벽을 칠해야함으로 cnt++;
                    if(map[nRow][nCol] == 1) cnt++;
                    // 미방문 길이면 방문 체크하고 queue에 넣자!
                    else if (map[nRow][nCol] == 0) {
                        map[nRow][nCol] = 2;
                        aq1.add(new Coordinate(nRow,nCol));
                    }
                }
            }
            paint += cnt;
        }
    }
}
class Coordinate {
    int row;
    int col;

    public Coordinate(int row, int col){
        this.row = row;
        this.col = col;
    }
}