일루미네이션

📍 문제 설명

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

5547번: 일루미네이션

 

💡 접근

그림을 보면 건물에서 인접한 6 방향의 벽의 숫자만큼 조명을 장식한다.

주의해야 할 점은 행이 짝수냐 홀수냐에 따라 인접한 6방향의 좌표가 다르기 때문에 짝수/홀수에 맞는 인접한 좌표를 따로 사용해야 한다.

그리고 범위를 벗어나는 경우도 벽으로 인정되어야 하기 때문에 행과 열 길이의 +2 만큼의 배열을 생성했다.

0,0 부터 시작해서 벽인 지점을 모두 체크하고 / 건물의 위치에서 벽인 지점의 갯수만큼 계속 더해주면 된다.

 

👩‍💻 코드

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

public class Main {
    static int[][] board;
    static boolean[][] isWall;
    static int n, m;
    //짝수, 홀수 행에 따라 탐색 범위가 달라진다.
    static int[][] even = {{-1,-1}, {0,-1}, {-1,0}, {1,0}, {1,-1}, {0,1}};
    static int[][] odd = {{0,-1}, {-1,1}, {-1,0}, {1,0}, {0,1}, {1,1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        board = new int[m+2][n+2];
        isWall = new boolean[m+2][n+2];

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

        Queue<Point> q = new LinkedList<>();
        q.add(new Point(0, 0));
        isWall[0][0] = true;

        while (!q.isEmpty()) {
            Point cp = q.poll();

            for(int i = 0; i < 6; i++) {
                int nx = 0, ny = 0;
                if(cp.x % 2 == 0) {
                    nx = cp.x + even[i][0];
                    ny = cp.y + even[i][1];
                }
                else {
                    nx = cp.x + odd[i][0];
                    ny = cp.y + odd[i][1];
                }
                if(nx<0 || ny<0 || nx>m+1 || ny>n+1 || board[nx][ny] != 0 || isWall[nx][ny]) continue;
                    isWall[nx][ny] = true;
                    q.offer(new Point(nx, ny));
            }
        }

        int sum = 0;
        for(int i = 1; i < m+1; i++) {
            for(int j = 1; j < n+1; j++) {
                if(board[i][j] == 0) continue;
                int nx = 0, ny = 0;
                for(int k = 0; k < 6; k++) {
                    if(i % 2 == 0) {
                        nx = i + even[k][0];
                        ny = j + even[k][1];
                    }
                    else {
                        nx = i + odd[k][0];
                        ny = j + odd[k][1];
                    }
                    if(isWall[nx][ny]) sum++;
                }
            }
        }
        System.out.println(sum);
    }

    private static class Point {
        private int x;
        private int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}