백준 16988 : Baaaaaaaaaduk2 (Easy)

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

16988번: Baaaaaaaaaduk2 (Easy)

[ 문제풀이 ]

전형적인 삼성 스타일의 문제로 바둑돌 2개를 둘 수 있는 모든 경우의 수에 대해서 죽일 수 있는 상대 돌의 개수를 찾아주면 되는 문제이다.

바둑돌 2개를 두는 방법은 백트래킹 기반의 조합으로 구해주면 된다.

상대 돌의 갯수를 찾는 방법은 2인 돌에서 시작하여 dfs를 통해 방문할 수 있는 모든 2인 돌을 탐색하면서 0(빈 공간)을 만나지 않는다면 탐색한 2인 돌의 개수를 카운트해주면 된다.

0을 만났다는건 해당 탐색에 존재하는 2인 돌은 상대 돌을 죽일 수 없다는 것을 의미한다.

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

public class Main {
	
	static int N, M, ans, cnt;
	static boolean flag;
	static int[][] map;
	static boolean[][] visit;
	
	static int[][] dir = {{-1,0},{1,0},{0,1},{0,-1}};
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[N][M];
			visit = new boolean[N][M];
			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());
				}
			}
			
			selectNode(0, 0);
			bw.write(ans + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static void selectNode(int pos, int count) {
		if (count == 2) {
			ans = Math.max(ans, getCount());
			for (int i = 0; i < N; ++i) Arrays.fill(visit[i], false);
			return;
		}
		if (pos == N * M) return;
		
		int y = pos / M, x = pos % M;
		if (map[y][x] != 0) {
			selectNode(pos + 1, count);
		} else {
			map[y][x] = 1;
			selectNode(pos + 1, count + 1);
			map[y][x] = 0;
			selectNode(pos + 1, count);
		}
	}

	public static int getCount() {
		int count = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < M; ++j) {
				if (map[i][j] == 2 && !visit[i][j]) {
					flag = false; cnt = 0;
					dfs(i, j);
					if (!flag) count += cnt;
				}
			}
		}
		return count;
	}
	
	public static void dfs(int y, int x) {
		cnt++;
		visit[y][x] = true;
		
		for (int d = 0; d < 4; ++d) {
			int ny = y + dir[d][0];
			int nx = x + dir[d][1];
			
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (map[ny][nx] == 1 || visit[ny][nx]) continue;
			if (map[ny][nx] == 0) {
				flag = true;
				continue;
			}
			dfs(ny, nx);
		}
	}
}