[백준]16932: 모양 만들기(java)

문제

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

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

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

입력

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

출력

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

제한

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

예제 입력 1 

3 3
0 1 1
0 0 1
0 1 0

예제 출력 1 

5

---

풀이

처음에 단순 1로 놔보고 0으로 돌려놓는 식의 풀이로 풀었더니 시간 초과가 나서 고민을 다시 한 문제였다.

shapeInfo라는 HashMap과 shapeKey로 각 섬을 넘버링해주고, HashMap의 shapeKey의 value로 크기를 줬다.

섬을 찾고 섬의 크기를 지정해주는 함수는 다음과 같다.

for(int i=0; i<N; i++) {
    for(int j=0; j<M; j++) {
        if(map[i][j] == 1) {
            setShapeInfo(i, j);
        }
    }
}

public static void setShapeInfo(int x, int y) {
    Queue<Point> q = new LinkedList<>();
    q.add(new Point(x, y));
    map[x][y] = shapeKey;
    int shapeSize = 1;

    while(!q.isEmpty()) {
        Point now = q.poll();
        for(int i=0; i<4; i++) {
            int nx = now.x+dist[i][0];
            int ny = now.y+dist[i][1];

            if(!isIn(nx, ny)  || map[nx][ny] != 1) continue;
            map[nx][ny] = shapeKey;
            q.add(new Point(nx, ny));
            shapeSize++;
        }
    }
    shapeInfo.put(shapeKey, shapeSize);
    shapeKey++;
}

 

이후에 0인 곳에 1을 놓고 상, 하, 좌, 우에있는 섬을 연결해 크기값을 반환하여 매번 그 크기를 갱신해준다.

public static int getLinkedShapeSize(int x, int y) {
    HashSet<Integer> visited = new HashSet<>();
    int size = 1;
    for(int i=0; i<4; i++) {
        int nx = x + dist[i][0];
        int ny = y + dist[i][1];

        if(!isIn(nx, ny) || map[nx][ny] == 0 || visited.contains(map[nx][ny])) continue;
        visited.add(map[nx][ny]);
        size += shapeInfo.get(map[nx][ny]);
    }
    return size;
}

예전에 풀었던 다리 만들기2 문제가 아이디어를 떠올리는데 많은 도음을 준 문제였던 것 같다.

전체 코드

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

public class BJ_G4_16932_모양만들기 {
    static class Point {
        int x;
        int y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static int N, M;
    static int[][] map;
    static int[][] dist = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static HashMap<Integer, Integer> shapeInfo = new HashMap<>();
    static int shapeKey = 2;
    public static void main(String[] args) throws Exception {
        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[N][M];
        ArrayList<Point> zeroList = new ArrayList<>();

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 0) zeroList.add(new Point(i, j));
            }
        }
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(map[i][j] == 1) {
                    setShapeInfo(i, j);
                }
            }
        }

        int max = 0;
        for(int s=0; s<zeroList.size(); s++) {
            int x = zeroList.get(s).x;
            int y = zeroList.get(s).y;
            max = Math.max(max, getLinkedShapeSize(x, y));
        }

        System.out.println(max);
    }

    public static int getLinkedShapeSize(int x, int y) {
        HashSet<Integer> visited = new HashSet<>();
        int size = 1;
        for(int i=0; i<4; i++) {
            int nx = x + dist[i][0];
            int ny = y + dist[i][1];

            if(!isIn(nx, ny) || map[nx][ny] == 0 || visited.contains(map[nx][ny])) continue;
            visited.add(map[nx][ny]);
            size += shapeInfo.get(map[nx][ny]);
        }
        return size;
    }

    public static void setShapeInfo(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));
        map[x][y] = shapeKey;
        int shapeSize = 1;

        while(!q.isEmpty()) {
            Point now = q.poll();
            for(int i=0; i<4; i++) {
                int nx = now.x+dist[i][0];
                int ny = now.y+dist[i][1];

                if(!isIn(nx, ny)  || map[nx][ny] != 1) continue;
                map[nx][ny] = shapeKey;
                q.add(new Point(nx, ny));
                shapeSize++;
            }
        }
        shapeInfo.put(shapeKey, shapeSize);
        shapeKey++;
    }

    private static boolean isIn(int x, int y) {
        return 0<=x && x<N && 0<=y && y<M;
    }
}