[BOJ - JAVA] 5547 - 일루미네이션 (BFS)

# 주소

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

5547번: 일루미네이션

# 문제

# 문제 해설 및 코드 리뷰

package com.core.hello;

import java.awt.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main{
    static int n, m;
    static int[][] arr;
    static int[][] odd = {{-1,0},{0,-1},{1,0},{1,1},{0,1},{-1,1}};
    static int[][] even = {{-1,-1},{0,-1},{1,-1},{1,0},{0,1},{-1,0}};
    static boolean[][] visit;
    static Queue<Point> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[m+2][n+2];
        visit = new boolean[m+2][n+2];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                arr[i][j] = scan.nextInt();
            }
        }
        bfs();
    }
    static void bfs(){
        queue.offer(new Point(0,0));
        visit[0][0] = true;
        while(!queue.isEmpty()){
            Point now = queue.poll();
            int nx = now.x;
            int ny = now.y;
            for(int i = 0; i < 6; i++){
                int px;
                int py;
                if(nx % 2 == 0) {
                    px = nx + even[i][0];
                    py = ny + even[i][1];
                }
                else {
                    px = nx + odd[i][0];
                    py = ny + odd[i][1];
                }
                if(px >= 0 && px <= m + 1 &&  py >= 0 && py <= n + 1){
                    if(!visit[px][py]){
                        if(arr[px][py] == 0){
                            visit[px][py] = true;
                            queue.offer(new Point(px, py));
                        }
                    }
                }
            }
        }
        int sum = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(arr[i][j] == 0)
                    continue;
                for(int t = 0; t < 6; t++){
                    int nx; int ny;
                    if(i % 2 == 0){
                        nx = i + even[t][0];
                        ny = j + even[t][1];
                    }else{
                        nx = i + odd[t][0];
                        ny = j + odd[t][1];
                    }
                    if(visit[nx][ny])
                        sum++;
                }
            }
        }
        System.out.println(sum);
    }
}

static int n, m;
static int[][] arr;
static int[][] odd = {{-1,0},{0,-1},{1,0},{1,1},{0,1},{-1,1}};
static int[][] even = {{-1,-1},{0,-1},{1,-1},{1,0},{0,1},{-1,0}};
static boolean[][] visit;
static Queue<Point> queue = new LinkedList<>();

y값이 odd, even일 때마다 인덱스 방향이 바뀌기 때문에 구분지어서 방향을 설정합니다.

bfs기법을 사용할 것이기 때문에 Queue를 사용합니다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
arr = new int[m+2][n+2];
visit = new boolean[m+2][n+2];
for(int i = 1; i <= m; i++){
    for(int j = 1; j <= n; j++){
        arr[i][j] = scan.nextInt();
    }
}
bfs();

n과 m을 입력받아서 arr, visit의 크기를 지정합니다.

이중for문으로 arr를 입력받고 bfs문을 실행합니다.

queue.offer(new Point(0,0));
visit[0][0] = true;

인덱스 (0,0)부터 탐색할 것이므로 visit을 true라 하고 queue에 담습니다.

while(!queue.isEmpty()){
    Point now = queue.poll();
    int nx = now.x;
    int ny = now.y;

nx와 ny를 선언합니다.

for(int i = 0; i < 6; i++){
    int px;
    int py;
    if(nx % 2 == 0) {
        px = nx + even[i][0];
        py = ny + even[i][1];
    }
    else {
        px = nx + odd[i][0];
        py = ny + odd[i][1];
    }
    if(px >= 0 && px <= m + 1 &&  py >= 0 && py <= n + 1){
        if(!visit[px][py]){
            if(arr[px][py] == 0){
                visit[px][py] = true;
                queue.offer(new Point(px, py));
            }
        }
    }
}

6개의 odd, even방향에 대해 for문으로 모두 탐색합니다.

px와 py를 새로 설정할 것인데, 만약 nx가 짝수라면 px = nx + even, py = ny + even으로 정합니다.

마찬가지로 nx가 홀수라면 px, py = nx, ny + even으로 설정합니다.

그리고 px와 py가 0과 m+1, n+1사이일 때 방문하지 않은 인덱스에 대해서 arr[px][py] == 0이면 visit을 true라 하고 queue에 px,py를 담습니다.

이로 인해 arr가 0인 점을 모두 방문하여 visit을 true로 바꾸었기 때문에 이후의 건물의 벽면을 셀 필요가 없게됩니다.

int sum = 0;
for(int i = 1; i <= m; i++){
    for(int j = 1; j <= n; j++){
        if(arr[i][j] == 0)
            continue;
        for(int t = 0; t < 6; t++){
            int nx; int ny;
            if(i % 2 == 0){
                nx = i + even[t][0];
                ny = j + even[t][1];
            }else{
                nx = i + odd[t][0];
                ny = j + odd[t][1];
            }
            if(visit[nx][ny])
                sum++;
        }
    }
}

그러므로 다시 이중 for문을 이용하여 sum의 값을 셀텐데, arr[i][j] == 0인 지점은 continue;하고 1인 지점만 파악할 건데요.

다시 for문을 이용하여 각 인덱스당 6번씩 탐색할 것입니다.

물론 x값에 따라 짝수일때에는 even, 홀수일 때에는 odd배열을 이용하여 nx,ny를 구해야하지요.

그래서 만약 새로 이동한 nx,ny지점이 방문한 지점이라면 sum값을 추가해주어, 벽의 길이를 구할 수 있습니다.

그림 사진에서 나와있는 그림처럼, 그림의 내부에 0값이 아니라 1이 있어도 저 부분은 셀 수 없는 지점이어야 합니다.

따라서 sum값을 셀 때 if(visit[nx][ny])라고 해야 하는데, 그게 아니라 if(arr[nx][ny] == 0)이렇게 하면 틀립니다.

그것이 바로 저 벽 내부에 있는 공간 때문에 그렇습니다.

그 부분은 visit도 false이고 arr값도 0이지만 위의 while문에서 이 지점을 따로 탐색하지는 않기 때문에 아무 것도 아닌 공간이 되어야 하는 것입니다.

이렇게 이해해봅시다.

우리가 구하는 것은 1로 연결된 벽의 외벽의 길이입니다.

하지만 벽 내부에 또 1이 있든 0이 있든 우리 입장에선 전혀 신경쓸 부분이 아니게 됩니다.

그러므로 벽 외부에 있는 0인 지점들을 모두 visit = true로 바꾸어 버려서, 나중에 이 벽의 외부 길이를 구하려면 arr가 1인 지점이면서 새로 이동시켰을 때 visit = true인 곳을 모두 각각 더하면 정답이 되는 것이지요.

 

왜 한 점을 기준으로 sum이 가질 수 있는 최대값이 6일까요?

이유는 간단합니다.  

한 점당 외부에 visit = true인 곳을 가지려면 6개의 벽과 인점해야하기 때문이지요.

당연히 벽 내부에 또 건물이 있다해도, sum의 값은 0이되어야 마땅합니다.

탐색하지도 않을 뿐더러, 탐색된다 하여도 그 외부 지점들은 모두 visit = false이기 때문에 sum = 0입니다.

감사합니다.