99클럽 코테 스터디 18일차 TIL + Java Algorithm

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

• 백준 - 일루미네이션 (문제 링크)
• 그래프 탐색
• 너비 우선 탐색 (BFS)
• 정육각형 격자

---

문제 설명

부유한 집안의 상속자 상근이네 집은 정육각형이 붙어있는 상태입니다. 상근이는 크리스마스가 다가오기 때문에 여자친구에게 잘 보이기 위해 건물의 벽면을 조명으로 장식하려고 합니다. 외부에 보이지 않는 부분에 조명을 장식하는 것은 낭비라고 생각했기 때문에 밖에서 보이는 부분만 장식하려고 합니다.

주어진 지도의 건물 위치에 따라 외부에서 보이는 벽면의 길이를 계산하는 프로그램을 작성하세요.

입력

• 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100)
• 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. 각 줄에는 W개의 정수가 공백으로 구분되어 있다. 정수는 건물이 있을 때는 1, 없을 때는 0이다. 건물이 적어도 하나는 있다.

출력

• 조명을 장식하는 벽면의 길이의 합을 출력한다.

예제 입력 1

8 4
0 1 0 1 0 1 1 1
0 1 1 0 0 1 0 0
1 0 1 0 1 1 1 1
0 1 1 0 1 0 1 0

예제 출력 1

64

예제 입력 2

8 5
0 1 1 1 0 1 1 1
0 1 0 0 1 1 0 0
1 0 0 1 1 1 1 1
0 1 0 1 1 0 1 0
0 1 1 0 1 1 0 0

예제 출력 2

56

---

문제 접근

이 문제는 정육각형 격자에서 주어진 건물 배치를 통해 외부에서 보이는 벽면의 길이를 계산하는 문제입니다.

BFS(너비 우선 탐색)를 이용해 외부 영역을 탐색하며, 건물의 외벽에 접한 부분을 계산하는 방식으로 접근할 수 있습니다.

1. 그래프 초기화
   • 주어진 입력을 통해 건물 배치를 인접 행렬로 초기화합니다.
2. BFS 탐색
   • BFS를 이용해 외부에서 시작하여 외부 영역을 탐색합니다.
   • 외부 영역과 접하는 건물의 벽면을 계산합니다.
3. 결과 계산
   • BFS를 통해 계산된 벽면의 길이를 합산하여 출력합니다.

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static int w, h;
    private static int[][] map;
    private static int[][] result;
    private static boolean[][] visited;
    private static int[][] oddDir = {{0, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}}; // 홀수 행
    private static int[][] evenDir = {{0, -1}, {-1, -1}, {-1, 0}, {0, 1}, {1, 0}, {1, -1}}; // 짝수 행

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

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

        map = new int[w + 2][h + 2];
        visited = new boolean[w + 2][h + 2];
        result = new int[w + 2][h + 2];

        for (int i = 1; i <= w; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= h; 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 < w + 2; i++) {
            for (int j = 0; j < h + 2; j++) {
                answer += result[i][j];
            }
        }

        System.out.println(answer);
    }

    public static void bfs() {
        Queue<Home> q = new LinkedList<>();
        q.add(new Home(0, 0));
        visited[0][0] = true;

        while (!q.isEmpty()) {
            Home temp = q.poll();
            int x = temp.x;
            int y = temp.y;

            for (int dir = 0; dir < 6; dir++) {
                int nx = 0;
                int ny = 0;
                if (x % 2 == 1) {
                    nx = x + oddDir[dir][0];
                    ny = y + oddDir[dir][1];
                } else {
                    nx = x + evenDir[dir][0];
                    ny = y + evenDir[dir][1];
                }

                if (nx < 0 || nx >= w + 2 || ny < 0 || ny >= h + 2) continue;
                if (map[nx][ny] == 1) {
                    result[x][y] += 1;
                    continue;
                }

                if (visited[nx][ny]) continue;
                visited[nx][ny] = true;
                q.add(new Home(nx, ny));
            }
        }
    }
}

class Home {
    int x;
    int y;

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

풀이 설명

1. 그래프 초기화
   • 입력으로 주어진 너비 w와 높이 h를 통해 지도 크기를 설정하고, 가장자리를 포함한 2차원 배열 map을 초기화합니다.
   • 입력된 건물 배치를 map에 저장하고, 건물이 있는 위치를 visited 배열에 표시합니다.
2. BFS 탐색
   • BFS를 이용해 외부에서 시작하여 외부 영역을 탐색합니다.
   • Queue를 이용해 탐색을 진행하며, 현재 위치에서 이동할 수 있는 방향을 계산합니다.
   • 현재 위치가 홀수 행인지 짝수 행인지에 따라 이동할 방향이 달라지므로, oddDir과 evenDir 배열을 사용하여 이동 방향을 설정합니다.
   • 외부 영역과 접하는 건물의 벽면을 만나면, 해당 위치의 result 값을 증가시킵니다.
3. 결과 계산
   • BFS 탐색이 완료되면, result 배열에 저장된 외부 벽면의 길이를 모두 합산하여 출력합니다.

 

---

 

마무리하며

• 이번 문제를 통해 BFS를 활용하여 그래프 탐색을 수행하는 방법을 익힐 수 있었습니다.
• 정육각형 격자의 특성을 고려하여 이동 방향을 설정하고, 외부 영역을 탐색하는 과정으로 문제를 해결했습니다.