[백준] 16932번 모양만들기

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

16932번: 모양 만들기

---

1. 이해하기

• 0과 1로 이뤄진 배열에서 1을 하나 놓음으로 1로 이뤄진 가장 큰 영역을 찾는 문제이다.
• 모든 0에 1을 놔보면서 크기를 비교한다.
• 하지만 1을 놓고 그때마다 dfs를 수행한다면 시간 초과가 일어난다. 따라서 더 좋은 방법을 찾아야 한다.
• 1을 놓기 전에 먼저 각 영역의 크기를 구해놓는다면 1을 놓을 때는 4방향 탐색만해서 크기를 더하면 된다.

---

2. 구현하기

• dfs(x,y,si): (x,y)에서 si(몇번째 영역을 구하는 것인지 나타내는 인덱스)의 크기를 구한다.
  • 전역 변수 cnt를 써서 크기를 구한다.
  • 1을 놓기전에 수행하는 작업이다.

static void dfs(int x, int y, int si) {
    visited[x][y] = si;
    size[si] = Math.max(size[si], cnt);

    for(int i = 0; i < 4; i++) {
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(OOB(nx,ny) || visited[nx][ny] != 0 || map[nx][ny] == 0) continue;
        cnt++;
        dfs(nx,ny,si);
    }
}

static boolean OOB(int x, int y) {
    return x < 0 || x >= N || y < 0 || y >= M;
}

• 다음은 전체를 탐색하면서 0인 부분에서만 4방향 탐색을 하면서 사이즈 비교를 해보면 된다.

---

3. 전체 코드

package algo;

import java.util.Scanner;

public class Boj16932_모양만들기 {
	static int N,M,ans;
	static int[][] map;
	static int[][] visited;
	static int[] size;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		sc.nextLine();
		map = new int[N][M];
		size = new int[N*N+1];
		visited = new int[N][M];
		for(int i = 0; i < N; i++) {
			String[] s = sc.nextLine().split(" ");
			for(int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(s[j]);
			}
		}
		
		int si = 1;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] == 1 && visited[i][j] == 0) {
					cnt = 1;
					dfs(i,j,si);
					si++;
				}
			}
		}
		
		boolean[] check = new boolean[si+1];
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(map[i][j] == 0) {
					int s = 1;
					for(int d = 0; d < 4; d++) {
						int nx = i+dx[d];
						int ny = j+dy[d];
						if(OOB(nx,ny) || check[visited[nx][ny]]) continue;
						s += size[visited[nx][ny]];
						check[visited[nx][ny]] = true;
					}
					ans = Math.max(s,ans);
					for(int d = 0; d < 4; d++) {
						int nx = i+dx[d];
						int ny = j+dy[d];
						if(OOB(nx,ny)) continue;
						check[visited[nx][ny]] = false;
					}
				}
			}
		}
		
		System.out.println(ans);
		sc.close();
	}
	
	static int[] dx = {0,0,1,-1}, dy = {1,-1,0,0};
	static int cnt;
	static void dfs(int x, int y, int si) {
		visited[x][y] = si;
		size[si] = Math.max(size[si], cnt);
		
		for(int i = 0; i < 4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(OOB(nx,ny) || visited[nx][ny] != 0 || map[nx][ny] == 0) continue;
			cnt++;
			dfs(nx,ny,si);
		}
	}
	
	static boolean OOB(int x, int y) {
		return x < 0 || x >= N || y < 0 || y >= M;
	}
}