99클럽 코테 스터디 18일차 TIL [bfs]

- 오늘의 학습 키워드 : bfs

[문제 이름 :   일루미네이션 (백준 5547번, G4) ]

문제 url : https://www.acmicpc.net/problem/5547

문제를 풀면서, 세 가지 핵심만 깨달으면 bfs로 문제를 풀 수 있다. (이 세 개를 생각하는데 두 시간이 걸렸다...)

1. 정육각형의 좌표가 (행,열)이 아닌 (열, 행)으로 되어있기 때문에, 실제 계산할 때는 반대로 값을 계산해야 하는 것 (이는 시뮬레이션 문제를 많이 풀어본 사람이라면 쉽게 생각할 수 있다.)

2. 홀수 행, 짝수 행(y)별로 정육각형의 6곳이 이동하는 경우가 다르다. 이 규칙을 먼저 찾고, 건물이 없는 곳을 Queue에 넣으며 Queue에서 뺐을 때 (=poll()) 다음 위치에 건물이 있다면, 이는 외부 선(구하고자 하는 합의 일부)이므로 값을 더해준다.
3. 기존 유형의 문제에서는 [h][n] 또는 [h+1][n+1]만큼 배열 크기를 지정하고 문제를 풀어나가지만, 정육면체의 외부 선의 길이를 구해야 하기 때문에 경계값을 +1 추가해서 [h+2][n+2]만큼 크기를 지정하여 외부 선임을 판단해야 한다. (이게 제일 오래 걸렸다.)

 

내가 작성한 코드는 아래와 같다.

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

public class Main {
    static int w, h;
    static boolean[][] visited;
    static int[][] map;
    // 좌부터 반시계
    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}};
    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];
        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());
            }
        }

        System.out.println(bfs());
    }

    static int bfs() {
        int count = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {0,0});
        visited[0][0] = true;

        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            int x = now[1];
            int y = now[0];

            int[][] direction;
            if(y % 2 == 0) {
                direction = even;
            } else {
                direction = odd;
            }

            for(int[] cur : direction) {
                int nx = x + cur[1];
                int ny = y + cur[0];

                if(ny >= 0 && ny <= h+1 && nx >=0 && nx <= w+1) {
                    // 방문하지 않은 곳인 경우
                    if(!visited[ny][nx]) {
                        // 건물이 있다면 벽의 길이 추가
                        if(map[ny][nx] == 1) {
                            count++;
                        } else {
                            // 건물이 없다면 계속 탐색
                            visited[ny][nx] = true;
                            queue.add(new int[] {ny, nx});
                        }
                    }
                }
            }
        }
        return count;
    }
}

[풀이 과정]

 1. 홀수, 짝수 좌표에 따라 정육각형의 좌표를 이동하는 경우의 수(6가지)에 해당하는 배열을 선언하고, 2차원 배열을 입력받는다. 이때, 경계값 처리를 위해 배열의 크기를 [h+2][w+2]로 선언한다.

2. (0,0)에서부터 bfs로 탐색을 하며 해당 위치가 짝수, 홀수임에 따라 값을 더해준 뒤, 해당하는 좌표가 건물이 있으면 길이값을 1씩 더해준다.

3. 건물이 없는 곳에 대하여 Queue에 좌표값을 저장한다.

 

건물이 없는 곳을 bfs로 탐색하면서, 6가지 경우의 수로 이동을 할 때 건물이 있으면, 외부 선이므로 길이를 더해주는 것으로 이해하면 된다.

풀이 시간 : 2시간 30분

내일은 위상 정렬의 개념에 대해 학습하고, 관련 문제를 풀어보고자 한다.