아이디어

• 각 칸의 꼭짓점을 정점으로 하고, 타일의 선으로 연결되어 있으면 가중치가 0이고 반대 방향으로 놓아져있으면 1인 그래프를 생각하자.
  • 이 그래프의 크기는 (N+1)x(M+1)이다.
• 이때 0-1 BFS를 이용해 (0, 0)부터 (N, M)까지 가는 최단거리를 구한다.
  • 이때, enqueued된 적이 있더라도 시작점으로부터의 거리가 더 짧으면 Deque에 추가되어야 한다는 점을 주의

코드

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);
		}
	}
}

메모리 및 시간

• 메모리: 36596 KB
• 시간: 492 ms

리뷰

• 지인들과 대회 중 아깝게 못 푼 문제인 줄 알았는데, enqueued(depth[][]) 처리 때문에 시간을 꽤 잡아먹은 걸 보면 어차피 시간 내 풀기 힘들었을 것 같다.