[백준 16988] Baaaaaaaaaduk2(Easy) (JAVA)

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

16988번: Baaaaaaaaaduk2 (Easy)

 

 

작년에 시간초과나고 포기한 문제였다..

다시 풀었는데 한번에 맞아서 뿌듯..!

bfs로 검은돌끼리 퍼져나가게 했다. 흰돌로 둘러싸인 흑돌갯수를 카운트해주었다.

도중에 빈공간 인 곳과 만나면 empty변수값을 증가시켜주어,

bfs가 끝났을 때 empty가 0일 때만 total값에 더해주었다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Baduk {
	int x;
	int y;

	public Baduk(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

}

public class Main_bj_16988_바둑2 {

	static int N, M, ans = 0;// 행,열
	static int[][] map;// 0은 빈칸,1은 나의돌,2는 상대돌
	static boolean[][] visit;
	static int[] dx = { 0, 0, 1, -1 };
	static int[] dy = { 1, -1, 0, 0 };
	static List<Baduk> list;

	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];
		visit = new boolean[N][M];
		list = new ArrayList<Baduk>();

		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) {
					list.add(new Baduk(i, j));
				}
			}
		} // 입력끝
		for (int i = 0; i < list.size() - 1; i++) {
			for (int j = i + 1; j < list.size(); j++) {
				Baduk a = list.get(i);
				Baduk b = list.get(j);
				map[a.x][a.y] = 1;
				map[b.x][b.y] = 1;
				solve();
				map[a.x][a.y] = 0;
				map[b.x][b.y] = 0;
				visit = new boolean[N][M];
			}
		}
		System.out.println(ans);

	}

	private static void solve() {
		Queue<Baduk> q;
		int total=0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 2 &&visit[i][j]==false) {
					q = new LinkedList<Baduk>();
					visit[i][j] = true;
					q.offer(new Baduk(i, j));
					int nowCnt = 1;
					int empty = 0;
					while (!q.isEmpty()) {
						Baduk b = q.poll();
						for (int d = 0; d < 4; d++) {
							int nx = b.x + dx[d];
							int ny = b.y + dy[d];
							if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny] == true || map[nx][ny] == 1)
								continue;
							if (map[nx][ny] == 0) {
								empty++;
							}
							if (map[nx][ny] == 2) {
								visit[nx][ny] = true;
								q.offer(new Baduk(nx, ny));
								nowCnt++;
							}
						}
					}
					if (empty > 0)
						continue;
					total+=nowCnt;

				}
			}
		}
		if(total>ans)ans=total;

	}

}