[백준] 16988 Baaaaaaaaaduk2

1. 문제

www.acmicpc.net/problem/16988

16988번: Baaaaaaaaaduk2 (Easy)

2. 접근방법

조합을 통해 모든 흰돌을 둘 수 있는 곳 중 2곳을 골라도

400 C 2 = 79800 개의 상황 뿐이 안되기 때문에

조합으로 돌을 두고 bfs로 주변 검은돌을 찾아서 죽었는지 안죽었는지

죽었다면 몇개의 돌이 죽었는지 검사하면 된다.

 

하지만 돌을 죽일 수 있는 위치는 굉장히 한정적인데 모든 장소에서 2군데를 고르는 것은 비효율 적이라 생각해서

 

나는 bfs를 사전에 먼저 돌려서 검은돌을 죽일 수 있는 위치만 후보군으로 두고

조합을 진행하였다.

 

예를 들면

 

이 그림에선 저 4개만 후보군이 되어서 조합을 진행하면 된다.

 

그런데 후보군을 정하면서 주의해야 할 점은

 

이런 모양일때

칸 하나가 두개의 돌을 죽일 수 있는 후보군이라

후보가 중복 될 수 있다.

나는 HashSet에 row*100 + col 의 형태로 저장해 중복처리를 해주었다.

 

또 이 모양일 때

아래돌을 먼저 검사하면서 빈칸에 visit 처리를 하고

위의 돌을 검사하러 가면 위 돌을 죽일 수 있는 아래 빈칸이 이미 visit처리가 되어있어

검사를 안하고 넘어 갈 수 있다.

 

또 반대로 visit 검사를 안한다면

이 모양에서

한 자리를 2번 빈칸으로 인식해 못죽이는 돌로 인식할 수도 있다.

 

위 사항들만 유의하면서 풀이 하도록 하자.

3. 자바 코드

package Gold;

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

public class G3_16988Baaaaaaaaaduk2 {
	static int N,M;
	static int map[][];
	static boolean visit[][];
	static boolean zerovisit[][];
	static int groupnum = 3;
	static List<Integer> candiarr;
	static HashSet<Integer> candiset = new HashSet<>();
	static int ans = 0;
	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];
		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());
			}
		}
		for(int i = 0 ; i < N ; i++) { //findcandi
			for(int j = 0 ; j < M ; j++) 
				if(map[i][j] == 2 && !visit[i][j]) 
					findcandi(i, j);
		}
		candiarr = new ArrayList<>(candiset);
		if(candiarr.size() == 1) 
			ans = finddead();
		
		
		comb(0, 0);
		System.out.println(ans);
	}
	static int dr[] = {1,-1,0,0};
	static int dc[] = {0,0,1,-1}; 
	static void findcandi(int x, int y) {
		Queue<Point> que = new LinkedList<Point>();
		que.offer(new Point(x,y));
		
		visit[x][y] = true;
		zerovisit = new boolean [N][M];
		ArrayList<Integer> arr = new ArrayList<>();
		while(!que.isEmpty()) {
			Point now = que.poll();
			for(int i = 0 ; i < 4 ; i++) {
				int row = now.x + dr[i];
				int col = now.y + dc[i];
				if(row < 0 || col <0 || row>= N || col >= M || map[row][col] == 1)
					continue;
				if(map[row][col] == 0) {
					if(zerovisit[row][col])
						continue;
					zerovisit[row][col] = true;
					if(arr.size() == 2)
						return;
					else
						arr.add(row*100+col);
					continue;
				}
				if(visit[row][col])
					continue;
				visit[row][col] = true;
				que.add(new Point(row,col));
			}
		}
		candiset.addAll(arr);
	}
	static int [] sel = new int[2];
	static void comb(int num, int selcnt) {
		if(selcnt == 2) {
			ans = Math.max(ans, finddead());
			return;
		}
		if(num == candiarr.size())
			return;
		
		sel[selcnt] = num;
		comb(num+1,selcnt+1);
		comb(num+1,selcnt);
	}
	static int finddead() {
		visit = new boolean [N][M];
		int zero1 = candiarr.get(sel[0]);
		int zero2 = candiarr.get(sel[1]);
		int cnt = 0;
		map[zero1/100][zero1%100] = 1;
		map[zero2/100][zero2%100] = 1;
		for(int s = 0 ; s < 2 ; s++) {
			int zero = candiarr.get(sel[s]);
			for(int i = 0 ; i < 4 ; i++) {
				int row = zero/100 + dr[i];
				int col = zero%100 + dc[i];
				if(row < 0 || col <0 || row>= N || col >= M || visit[row][col])
					continue;
				if(map[row][col] == 2) 
					cnt += bfs(row,col);
			}
		}
		map[zero1/100][zero1%100] = 0;
		map[zero2/100][zero2%100] = 0;
		return cnt;
	}
	static int bfs(int x, int y) {
		Queue<Point> que = new LinkedList<Point>();
		que.offer(new Point(x,y));
		visit[x][y] = true;
		int cnt = 0;
		boolean isdead = true;
		while(!que.isEmpty()) {
			Point now = que.poll();
			cnt++;
			for(int i = 0 ; i < 4 ; i++) {
				int row = now.x + dr[i];
				int col = now.y + dc[i];
				if(row < 0 || col <0 || row>= N || col >= M || map[row][col] == 1)
					continue;
				if(visit[row][col])
					continue;
				if(map[row][col] == 0) {
					isdead = false;
					continue;
				}
				visit[row][col] = true;
				que.add(new Point(row,col));
			}
		}
		if(!isdead)
			return 0;
		else
			return cnt;
	}
}

4. 마치며

난이도에 비해 쓸데없이 복잡하게 풀었는데

효율성 5등 했으니 만족