[백준/JAVA] 5547번: 일루미네이션

📖 문제

5547번: 일루미네이션

 

 

💡  풀이 방식

• BFS

 

외벽과 닿는 모든 면을 정육각형으로 돌리기 위해

격자 판 숫자를 저장할 map 배열과, 벽 개수를 저장할 2차원 배열 result의 크기는 [행+2][열+2]로 설정한다.

map = new int[H+2][W+2];  // 외벽과 닿는 모든 면을 정육각형으로 돌리기 위해 +2
result = new int[H+2][W+2]; // 벽 개수 저장 리스트
visited = new boolean[H+2][W+2];

 

 

격자를 입력받는데, 건물이 있는 경우(1)는 방문 처리를 한다.

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)
            visited[i][j] = true;
    }
}

 

 

(0,0) 부터 BFS를 수행한다.

 

행이 홀수냐 짝수냐에 따라 인접한 6칸의 인덱스 방향이 바뀌므로 구분지어 방향을 설정한다.

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

 

 

인접한 칸이 격자 범위를 벗어나지 않고, 건물이 있다면(1), 현재 위치의 벽 개수에 +1한다.

인접한 칸이 격자 범위를 벗어나지 않고, 방문한 적 없고,  건물이 없는(0) 칸이라면, 해당 칸으로 탐색을 수행한다.

while(!q.isEmpty()) {
    int[] now = q.poll();

    for(int d = 0 ; d < 6; d++) {
        int nx = 0;
        int ny = 0;

        if(now[0] % 2 == 1) {	// 홀수 행
            nx = now[0] + odd[d][0];
            ny = now[1] + odd[d][1];
        }
        else {	// 짝수 행
            nx = now[0] + even[d][0];
            ny = now[1] + even[d][1];
        }

        // 격자 범위 벗어나면 pass
        if(nx < 0 || nx >= H+2 || ny < 0 || ny >= W+2)  continue;

        if(map[nx][ny] == 1) {
            result[now[0]][now[1]]++;
            continue;
        }

        if(!visited[nx][ny]) {
            visited[nx][ny] = true;
            q.add(new int[]{nx, ny});
        }
    }
}

 

 

 

 

💥 유의사항

행이 홀수냐 짝수냐에 따라 인접한 6칸의 인덱스 방향이 바뀌므로 구분지어 방향을 설정하는 것이 포인트,,

 

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    // 좌, 좌상, 우상, 우, 우하, 좌하 (시계 방향)
    static int[][] odd = {{0,-1}, {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}};     // 홀수 행
    static int[][] even = {{0,-1}, {-1,-1}, {-1,0}, {0,1}, {1,0}, {1,-1}};  // 짝수 행
    
    static int W,H;
    static int[][] map, 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 = Integer.parseInt(st.nextToken());   // 열
        H = Integer.parseInt(st.nextToken());   // 행
        
        map = new int[H+2][W+2]; // 외벽과 닿는 모든 면을 정육각형으로 돌리기 위해 +2
        result = new int[H+2][W+2]; // 벽 개수 저장 리스트
        visited = 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) // 미리 방문처리
                    visited[i][j] = true;
            }
        }
        
        bfs();
        
        int answer = 0;
        for(int i = 0 ; i < H+2 ; i++) {
            for(int j = 0 ; j < W+2 ; j++) {
                answer += result[i][j];
            }
        }
        
        System.out.println(answer);
    }
    
    private static void bfs() {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {0, 0});
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 6; d++) {
                int nx = 0;
                int ny = 0;
                
                if(now[0] % 2 == 1) {    // 홀수 행
                    nx = now[0] + odd[d][0];
                    ny = now[1] + odd[d][1];
                }
                else {    // 짝수 행
                    nx = now[0] + even[d][0];
                    ny = now[1] + even[d][1];
                }
                
                // 격자 범위 벗어나면 pass
                if(nx < 0 || nx >= H+2 || ny < 0 || ny >= W+2)  continue;
                
                if(map[nx][ny] == 1) {
                    result[now[0]][now[1]]++;
                    continue;
                }
                
                if(!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

2차원 벽 개수 저장 배열을 사용하지 않고, 마지막에 계산을 통해 변수에 값을 갱신하는 식으로 푸셨다.

[백준] 5547번: 일루미네이션

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

---

💦 어려웠던 점

- 행이 홀수냐 짝수냐에 따라 다르게 설정할 생각을 하지 못 했다.

- 격자 크기도 +2할 생각을 하지 못 함

 

🧐 새로 알게 된 내용

- 홀수 행과 짝수 행의 인접한 방향 배열을 따로 작성해 활용할 아이디어

- 이동 가능한 경우의 수가 6가지인 점!

- 벽이 있는 칸(1)을 기준으로 bfs 탐색하며 직접 길이를 구할 생각을 했는데, 벽이 없는 칸 기준으로 인접한 6방향에 맞닿은  해야 외벽에 칠해진 수를 구하는 것이 포인트..

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준] 5547 일루미네이션 - BFS + 아이디어 JAVA

 

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