[Java]16932 모양만들기

 

 

https://www.acmicpc.net/problem/16932

 

 

 

 

 

 

 

👉문제

---

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.

1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.

배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

 

 

👉입력

---

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

 

 

👉출력

---

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

 

 

👉제한

---

• 2 ≤ N, M ≤ 1,000
• 0과 1의 개수는 하나 이상이다.

 

 

 

👉풀이

---

처음에는 DFS로 0인 부분에서 시작하여 1인 부분을 계속 탐색하여 최대값을 찾았는데 시간 초과가 나서 생각을 다시 하여 풀이 방법을 바꿔서 풀었습니다. 우선 모양마다 크기를 저장해주고 그 모양에 번호를 지정해줍니다. 그리고 다시 0인 것과 인접한 모양을 붙여서 최대값을 찾아줬습니다.

 

 

 

 

소스 코드

 

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

public class Main {
    static int n, m, cnt, idx, sum;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] set;
    static HashMap<Integer, Integer> size;

    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());
        visited = new boolean[n][m];
        arr = new int[n][m];
        set = new int[n][m];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int max = Integer.MIN_VALUE;
        size = new HashMap<>();
        idx = 0;
        sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1 && !visited[i][j]) {
                    cnt = 1;
                    visited[i][j] = true;
                    dfs(i, j);
                    size.put(idx, cnt);
                    idx++;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 0) {
                    zeroToOne(i, j);
                    max = Math.max(max, sum);
                }
            }
        }

        System.out.println(max);
    }

    static void dfs(int x, int y) {
        set[x][y] = idx;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (arr[nx][ny] == 1 && !visited[nx][ny]) {
                    visited[nx][ny] = true;
                    cnt++;
                    dfs(nx, ny);
                }
            }
        }
    }

    static void zeroToOne(int x, int y) {
        HashSet<Integer> hashSet = new HashSet<>();
        sum = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if (arr[nx][ny] == 1) hashSet.add(set[nx][ny]);
            }
        }
        for (int i : hashSet) sum += size.get(i);
    }
}