백준 2234. 성곽 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/2234

"BFS 그리고 비트마스킹(필수는아님..)"

비트마스킹을 사용하지 않고도 0 ~ 15 까지의 숫자별로 가능한 방향을 이차원 배열로 정의해줘서 풀면됨... 하지만 아래 풀이는 비트마스킹 써씅ㅁ.

solve1()을 통해 아래 두개의 답을 구할 수 있다.

1. BFS를 돈다.

2. 1번 BFS를 돌면서 각 방의 size가 구해지므로 최대값을 비교해 구한다.

마지막 문제에 대한 답을 구하는게 관건인듯 하다. 나는 1,2 번을 구하면서 새로운 int[][] arr 을 정의해서 이곳에 0~ 방의 개수 까지 카운터를 마킹했다.(영역 나누기 처럼) 동시에 각 index마다 방의 크기를 ArrayList에 저장해두었다.

그 후에 새로 정의한 맵 arr 전체를 돌면서, 0 ~ 카운터 까지 K를 기준으로 다른 영역을 (즉 , 다른 번호를) 만나면 아래와 같이 최대값을 갱신해주었다.

max = Math.max (max, width[K] + width[other] )

--------

더 좋은 방안일거 같은건, solve1()을 구하면서, 벽으로 막혀 탐색이 불가능한 지역을 만나면 현재 위치 x,y 와 이동 불가 지역인 nx,ny 를 저장해 두고 나중에 각 방의 사이즈를 모두 구한 다음에 비교 해주면 더 좋을 듯, 

이 때 x,y 를 1차원 index로 변환 ( nx + y ) ...

List<List<Integer>> list .... 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static int n,m;
    static int[][] map;
    static int[][] arr;
    static ArrayList<Integer> widths = new ArrayList<>();
    static boolean[][] visited;
    static Queue<Integer> q = new LinkedList<>();
    static int max;
    static int count;
    static int dx[] = {0,-1,0,1};
    static int dy[] = {-1,0,1,0};
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        map = new int[m][n];
        arr = new int[m][n];
        visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        count = solve1();
        
        System.out.println(count);
        System.out.println(max);
        if(count == m * n) {
            System.out.println(2);
        }
        else {
            System.out.println(solve2());
        }
    }
    
    static int solve1() {
        int room = -1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(visited[i][j]) continue;
                room++;
                visited[i][j] = true;
                q.add(i);
                q.add(j);
                int size = 0;
                while(!q.isEmpty()) {
                    int x = q.poll();
                    int y = q.poll();
                    size ++;
                    arr[x][y] = room;
                    int val = map[x][y];
                    
                    int[] d = {val & 1 , val & 2, val & 4, val & 8};
                    
                    for (int k = 0; k < 4; k++) {
                        int nx = x + dx[k];
                        int ny = y + dy[k];
                        
                        if(!isRange(nx, ny) || visited[nx][ny] || d[k] != 0 )
                            continue;
                        
                        visited[nx][ny] = true;
                        q.add(nx);
                        q.add(ny);
                    }
                }
                widths.add(size);
                max = Math.max(max, size);
            }
        }
        return room+1;
    }
    
    static int solve2() {
        visited = new boolean[m][n];
        int max2 = 0;
        
        for (int k = 0; k < count; k++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if(arr[i][j] != k || visited[i][j]) continue;
                    
                    visited[i][j] = true;
                    q.add(i);
                    q.add(j);
                    
                    while(!q.isEmpty()) {
                        int x = q.poll();
                        int y = q.poll();
                        
                        for (int d = 0; d < 4; d++) {
                            int nx = x + dx[d];
                            int ny = y + dy[d];
                            
                            if(!isRange(nx, ny) || visited[nx][ny])
                                continue;
                            
                            if(arr[nx][ny] != k) {
                                max2 = Math.max(max2, widths.get(k) + widths.get(arr[nx][ny]));
                                continue;
                            }
                            visited[nx][ny] = true;
                            q.add(nx);
                            q.add(ny);
                        }
                    }
                    
                }
            }
        }
        return max2;
    }
    
    static boolean isRange(int x, int y) {
        if(x < 0 || x >= m || y < 0 || y >= n) return false;
        return true;
    }
}