아이디어

• 단순히 입력 처리가 번거로운 순열 문제처럼 보이지만 핵심은 입력받은 수의 중복도만큼만 중복될 수 있다는 것에 있다.
• 각 수의 등장 횟수는 배열 B에 기록했다.
• 1번 이상 등장한 수만 모아 배열 A에 저장해두자.
• A에 대해 중복순열을 작성한다. 이때, 숫자가 등장했다면 사용할 수 있는 횟수를 차감한다.
  • 사용할 수 있는 횟수가 0이 되면 그 수는 더 이상 사용하지 않는다.
  • 다음 숫자로 가기 전 사용 횟수를 원상복귀 시켜놓아야 한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, M, ans;
	static int[][] map;
	static boolean[][] visited;
	
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, 1, 0, -1};
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());

		map = new int[N][M];
		for (int y=0; y<N; y++) {
			tk = new StringTokenizer(rd.readLine());
			for (int x=0; x<M; x++) {
				map[y][x] = Integer.parseInt(tk.nextToken());
			}
		}
		visited = new boolean[N][M];
		
		comb(0, 0);
		
		System.out.println(ans);
	}
	
	static void comb(int srcIdx, int tgtIdx) {
		if (tgtIdx == 3) {
			ans = Math.max(ans, simulate());
			return;
		}
		if (srcIdx == N*M) return;
		int y = srcIdx / M;
		int x = srcIdx % M;
		if (map[y][x] != 0) {
			comb(srcIdx + 1, tgtIdx);
			return;
		}
		
		map[y][x] = 1;
		comb(srcIdx + 1, tgtIdx + 1);
		map[y][x] = 0;
		comb(srcIdx + 1, tgtIdx);
	}
	
	static int simulate() {
		for (int y=0; y<N; y++)
			for (int x=0; x<M; x++)
				visited[y][x] = false;

		for (int y=0; y<N; y++) {
			for (int x=0; x<M; x++) {
				if (map[y][x] == 2)
					dfs(y, x);
			}
		}
		
		int r=0;
		for (int y=0; y<N; y++)
			for (int x=0; x<M; x++)
				if (map[y][x] == 0 && !visited[y][x]) r++;
		return r;
	}
	
	static void dfs(int y, int x) {
		visited[y][x] = true;
		
		for (int d=0; d<4; d++) {
			int ny=y+dy[d];
			int nx=x+dx[d];
			if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
			if (visited[ny][nx]) continue;
			if (map[ny][nx] == 1) continue;
			dfs(ny, nx);
		}
	}
}

메모리 및 시간

• 메모리: 20600 KB
• 시간: 192 ms

리뷰

• 단순히 순열, 조합 브루트포스가 아니라 횟수를 신경 써야 한다는 점을 놓치면 안 되는 문제