99클럽 코테 스터디 18일차 TIL + 일루미네이션 (java)

 

💡 문제

• 일루미네이션
• https://www.acmicpc.net/problem/5547

권장 시간

• 1시간 30분

소요 시간

• 1시간 40분 + a

풀이 코드

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

class Point {
    int h, w;

    public Point(int h, int w) {
        this.h = h;
        this.w = w;
    }
}

public class BOJ5547 {
    int H, W;

    int[][] map;
    boolean[][] isVisited;
    Queue<Point> q = new LinkedList<>();

    // 홀수 행과 짝수 행 방향 설정 - 육각형이므로 6방향
    int oddDir[][] = {{0, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}};
    int evenDir[][] = {{0, -1}, {-1, -1}, {-1, 0}, {0, 1}, {1, 0}, {1, -1}};

    public void solution() throws Exception {
        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]; // 패딩 추가
        isVisited = 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());
            }
        }

        // BFS를 외부 영역인 (0, 0)부터 시작
        q.add(new Point(0, 0));
        isVisited[0][0] = true;

        bfs();

		// 장식 길이 구하기
        int perimeter = 0;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                if (map[i][j] == 1) {
                    // 육각형의 각 방향에 대해 경계 검사
                    for (int t = 0; t < 6; t++) {
                        int nx, ny;
                        if (i % 2 == 0) { // 짝수 행
                            nx = i + evenDir[t][0];
                            ny = j + evenDir[t][1];
                        } else { // 홀수 행
                            nx = i + oddDir[t][0];
                            ny = j + oddDir[t][1];
                        }
                        // 경계가 맵 바깥이거나 외부 '0'과 접하는 경우 경계로 간주
                        if (nx < 0 || ny < 0 || nx > H + 1 || ny > W + 1 || map[nx][ny] == 0 && isVisited[nx][ny]) {
                            perimeter++;
                        }
                    }
                }
            }
        }
        System.out.println(perimeter);
    }

    private void bfs() {
        while (!q.isEmpty()) {
            Point curr = q.poll();

            for (int i = 0; i < 6; i++) {
                int nh, nw;
                if (curr.h % 2 == 0) { // y가 짝수인 경우
                    nh = curr.h + evenDir[i][0];
                    nw = curr.w + evenDir[i][1];
                } else { // y가 홀수인 경우
                    nh = curr.h + oddDir[i][0];
                    nw = curr.w + oddDir[i][1];
                }

                // 예외처리
                if (nh >= 0 && nw >= 0 && nh <= H + 1 && nw <= W + 1 && !isVisited[nh][nw] && map[nh][nw] == 0) {
                    q.add(new Point(nh, nw));
                    isVisited[nh][nw] = true; // 방문 체크는 큐에 넣을 때만 하도록 함
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new BOJ5547().solution();
    }
}

주요사항

어렵다…

 

문제를 풀이하면서 내가 가장 착각한 것은 건물의 외벽으로 장식의 길이를 구하려 한 것이다.

반대로 건물이 없는 곳을 기준으로 건물이 있는 곳과 맞닿은 벽을 구하면 훨씬 쉽게 풀릴 문제였다!

 

흑흑…

 

BFS의 목적

1. 외부 0 영역 식별:
   • BFS는 격자의 외부 경계에서 시작하여, 외부와 연결된 모든 0 셀을 탐색합니다. 이 외부 0 영역은 육각형 벽(1)과 인접한 경계로 간주됩니다.
   • (0, 0)부터 시작하는 이유는 패딩된 격자의 외부에서 출발하여 모든 외부 공간을 방문하고 이를 isVisited 배열에 표시하기 위함입니다.
2. 내부 0 영역과의 구분:
   • 0 셀은 외부 영역에 위치할 수도 있고, 1로 둘러싸인 내부 영역에 위치할 수도 있습니다. BFS를 통해 외부 0 영역을 명확히 구분하면 내부 0 셀과 혼동되지 않습니다.
   • 외부 0과 연결되지 않은 내부 0은 탐색 중 방문되지 않기 때문에 경계 계산에 포함되지 않습니다.
3. 경계 계산에 필요한 정보 제공:
   • BFS를 통해 방문한 0 셀만이 외부와 연결된 것으로 간주되므로, 경계를 계산할 때 육각형 셀의 이웃이 isVisited 배열에서 true로 표시된 0일 경우에만 경계로 인정합니다.
   • 이를 통해 경계 계산 시 내부 0이 아닌 외부 0과의 접촉만을 경계로 간주하게 됩니다.