99클럽 코테 스터디 18일차 TIL / [백준] 일루미네이션

오늘의 학습 키워드

---

BFS

문제

---

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

• 플랫폼: 백준
• 문제명: 일루미네이션
• 난이도: 골드 4

풀이

---

import java.io.*;
import java.util.*;
public class Main {

    static int oddDx[] = {1, 1, 1, 0, -1, 0}; // 홀수 열
    static int oddDy[] = {-1, 0, 1, 1, 0, -1}; // 홀수 행
    static int evenDx[] = {0, 1, 0, -1, -1, -1}; // 짝수 열
    static int evenDy[] = {-1, 0, 1, 1, 0, -1}; // 짝수 행

		static int[][] map; // 건물 배치 정보 (0이면 x, 1이면 건물 o)
		static boolean[][] visited; // 해당 좌표 방문 여부
		static int[][] adjCnt; // 인접한 벽면의 개수
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());

        map = new int[h + 2][w + 2];
        visited = new boolean[h + 2][w + 2];
        adjCnt = new int[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());
            }
        }

        System.out.println(bfs(w, h));
    }

    public static int bfs(int w, int h) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(0, 0));
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            int cx = cur.x;
            int cy = cur.y;

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

                if (cy % 2 == 0) {
                    nx = cx + evenDx[i];
                    ny = cy + evenDy[i];
                } else {
                    nx = cx + oddDx[i];
                    ny = cy + oddDy[i];
                }

								// 이동할 수 있다면
                if (nx >= 0 && nx <= w + 1 && ny >= 0 && ny <= h + 1) {
			              // 방문하지 않은 좌표인 경우
                    if (!visited[ny][nx]) {
			                  // 건물이 없다면 이동
                        if (map[ny][nx] == 0) {
                            visited[ny][nx] = true;
                            queue.offer(new Point(nx, ny));
                        } 
                        // 건물이 있다면 adjCnt + 1
                        else {
                            adjCnt[cy][cx]++;
                        }
                    }
                }
            }
        }

        int sum = 0;

        for (int i = 0; i <= h + 1; i++) {
            for (int j = 0; j <= w + 1; j++) {
                sum += adjCnt[i][j];
            }
        }

        return sum;
    }

    public static class Point {
        int x;
        int y;

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

접근

• 우선, 육각형이므로 진행 방향은 총 6가지가 됩니다. (좌상단, 좌, 좌하단, 우하단, 우, 우상단)
• 그리고 문제에서 정의되어 있다시피 y가 홀수일 때와 짝수일 때 규칙이 다릅니다.
  • 그러므로 두 경우를 모두 정의해야 합니다.

    static int oddDx[] = {1, 1, 1, 0, -1, 0}; // 홀수 열
    static int oddDy[] = {-1, 0, 1, 1, 0, -1}; // 홀수 행
    static int evenDx[] = {0, 1, 0, -1, -1, -1}; // 짝수 열
    static int evenDy[] = {-1, 0, 1, 1, 0, -1}; // 짝수 행

• 다음으로, 정답을 도출해내기 위한 배열 3개가 필요한데, 각각은 다음의 의미를 가집니다.

  static int[][] map; // 건물 배치 정보 (0이면 x, 1이면 건물 o)
  static boolean[][] visited; // 해당 좌표 방문 여부
  static int[][] adjCnt; // 인접한 벽면의 개수

  • 인접한 벽면의 개수를 구하기위해 배열의 크기를 [h+2][w+2]로 설정해야 합니다. (끝에 위치한 건물의 벽면의 개수를 카운트 해야하므로, 상하좌우 + 1씩 한 값입니다.)
• 이후 BFS를 통해 건물이 위치하지 않은 좌표를 탐색합니다.

  • 건물이 위치하지 않은 좌표로만 이동을 진행하며, 만약 건물과 인접한 좌표의 경우 adjCnt + 1을 해줍니다.

  • 그럼 최종적으로 adjCnt에는 인접한 벽면의 개수가 저장되고, adjCnt를 전체 순회하며 sum 값을 구하면 정답이 도출됩니다.

    public static int bfs(int w, int h) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(0, 0));
        visited[0][0] = true;
    
        while (!queue.isEmpty()) {
            Point cur = queue.poll();
            int cx = cur.x;
            int cy = cur.y;
    
            for (int i = 0; i < 6; i++) {
                int nx, ny;
    
                if (cy % 2 == 0) {
                    nx = cx + evenDx[i];
                    ny = cy + evenDy[i];
                } else {
                    nx = cx + oddDx[i];
                    ny = cy + oddDy[i];
                }
    
    						// 이동할 수 있다면
                if (nx >= 0 && nx <= w + 1 && ny >= 0 && ny <= h + 1) {
    	              // 방문하지 않은 좌표인 경우
                    if (!visited[ny][nx]) {
    	                  // 건물이 없다면 이동
                        if (map[ny][nx] == 0) {
                            visited[ny][nx] = true;
                            queue.offer(new Point(nx, ny));
                        } 
                        // 건물이 있다면 adjCnt + 1
                        else {
                            adjCnt[cy][cx]++;
                        }
                    }
                }
            }
        }
    
        int sum = 0;
    
        for (int i = 0; i <= h + 1; i++) {
            for (int j = 0; j <= w + 1; j++) {
                sum += adjCnt[i][j];
            }
        }
    
        return sum;
    }

소요 시간

2시간

회고

---

상하좌우, 혹은 대각선을 이동하는 유형의 문제는 많이 풀이해봤지만 육각형 이동 유형은 처음 풀이해봤습니다. 2차원 배열의 형태로 보기보단 육각형의 그림을 보면서 풀이하는 게 훨씬 직관적이더라고요!