[자바] 백준 8783 - Architektura niezależna (java)

 문제 : boj8783

---

 

필요 알고리즘 개념

 - 그래프 탐색 (bfs, dfs)

• 단순히 bfs 혹은 dfs로 그래프 탐색만 해주면 된다. 다만 약간의 아이디어가 필요하다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  bfs를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자.

 

  문제 자체는 간단하다. '#'으로 둘러싸인 부분 내부의 빈칸까지 포함해서 넓이를 구하면 된다. 예를들어 예제 입력 1의 첫번째 테스트케이스는 아래와 같은 부분의 넓이를 구하면 된다.

  

  단순히 bfs 혹은 dfs로 탐색만 해주면 되는 간단한 문제이긴한데, 생각하기에 따라 어려울 수 있다. # 바깥쪽에서 시작해 #에 포함 안된 부분을 재보려 한다. 예제 입력 1의 두 번째 테스트케이스와 같은 경우 탐색을 어디서 출발해야 할까? (0,0) 에서 시작하면 될까? 이미 외곽이 전부 #이라 불가하다.

 

  물론 아래처럼 가능한 경우도 있겠지만, 아무튼 불가능한 경우가 있으므로 동일한 로직으로 처리가 안된다.

 

  그럼 #으로 둘러쌓인 내부를 탐색하면 될까? 우선 내부에 있는 '.'임을 검증해야 하고, 외곽의 '#'도 별도로 탐색해야 하므로 코드가 많이 까다로워질 것 같다.

 

  아주 간단한 해법이 있는데 약간의 아이디어가 필요하다. 외부를 빈 칸으로 전부 둘러싸는 것이다. 

 

  그럼 임의로 만든 외부의 빈칸 아무대서나 bfs 혹은 dfs를 돌려서 '#' 외부의 넓이를 전체 넓이에서 빼주면 된다.

 

---

 

코드 : github

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

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<13);
    private static StringBuilder sb = new StringBuilder();
    private static final int[] DR = {0, 0, -1, 1};
    private static final int[] DC = {1, -1, 0, 0};

    public static void main(String[] args) throws Exception {
        int tc = Integer.parseInt(br.readLine());
        while (tc-->0) {
            new Main().solution();
        }
        System.out.print(sb);
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        boolean[][] arr = new boolean[n+2][n+2];	//외부를 임의의 빈칸으로 둘러싼다.
        for (int i = 1; i <= n; i++) {
            String row = br.readLine();
            for (int j = 1; j <= n; j++) {
                if (row.charAt(j-1) == '#')
                    arr[i][j] = true;
            }
        }

        boolean[][] v = new boolean[n+2][n+2];
        v[0][0] = true;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0,0});
        int cnt = (n+2)*(n+2);	// 빈칸으로 둘러싼부분까지 포함한 전체 넓이
        while (!q.isEmpty()) {	// bfs 진행
            int[] cur = q.poll();
            int cr = cur[0];
            int cc = cur[1];
            cnt--;	// '#'으로 둘러쌓인 부분 외부를 탐색하며 전체넓이에서 빼준다.
            for (int d = 0; d < 4; d++) {
                int nr = cr + DR[d];
                int nc = cc + DC[d];
                if (nr<0||nr>=n+2||nc<0||nc>=n+2||v[nr][nc]||arr[nr][nc]) continue;
                v[nr][nc] = true;
                q.add(new int[]{nr, nc});
            }
        }
        sb.append(cnt).append('\n');
    }
}