[BOJ 16988] Baaaaaaaaaduk2 (Easy) (Java)

BOJ 16988 Baaaaaaaaaduk2 (Easy)

문제풀이

예전에 봤을 때는 왜 그렇게 어려웠던건지... 다시 보니 간단한 문제다.
1. 돌 두개를 놓는 모든 경우를 수행한다.
2. 맵 전체 검은 돌에 대한 라벨링을 한다. 동시에 죽은 그룹의 돌을 모두 세어 ans에 최댓값 갱신을 한다.

• 대각선은 신경쓰지 않는다. 맵 밖으로 벗어나는 것도 신경쓰지 않는다.

• 빈칸과 인접한 그룹은 살아있는 그룹이다.

• 돌 두개를 놓는 모든 경우를 구하는 방법

  • r * 충분히 큰 수 + c 를 인자로 넘기는 재귀함수로

  private static void placement(int cnt, int limit) {
  	if(cnt == 2) {
  		// 돌 두개를 착수했을 때 수행할 부분 
  		return;
  	}
  
  	for(int r = 0 ; r < N ; ++r) {
  		for(int c = 0 ; c < M ; ++c) {
  			// 이전 셀에 대한 값 보다 큰 셀 부터 시작한다.
  			if(r * 100 + c < limit) continue;
  			if(map[r][c] == 0) {
  				map[r][c] = 1;
  				// r * 100 + c를 다음 limit로 넘긴다.
  				placement(cnt + 1, r * 100 +c);
  				map[r][c] = 0;
  			}
  		}
  	}
  }

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static class Node {
		int r, c;
		
		Node(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	static int[][] map;
	static boolean[][] visited;
	static int N, M, ans;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		
		map = new int[N][M];
		visited = new boolean[N][M];
		
		for(int r = 0 ; r < N ; ++r) {
			st = new StringTokenizer(br.readLine());
			for(int c = 0 ; c < M ; ++c) {
				map[r][c] = stoi(st.nextToken());
			}
		}
		
		placement(0, 0);
		
		System.out.println(ans);
	}
	
	private static void placement(int cnt, int limit) {
		if(cnt == 2) {
			// 죽은 돌 세어보기
			initVisited();
			int dead = 0;
			for(int r = 0 ; r < N ; ++r) {
				for(int c = 0 ; c < M ; ++c) {
					if(map[r][c] == 2 && !visited[r][c]) {
						// 돌을 놓았을 때 여러 그룹이 동시에 죽을 수 있다. 
						dead += countDeadBlackStone(r, c);
					}
				}
			}
			
			ans = dead > ans ? dead : ans;
			
			return;
		}
		
		for(int r = 0 ; r < N ; ++r) {
			for(int c = 0 ; c < M ; ++c) {
				// 이전 셀에 대한 값 보다 큰 셀 부터 시작한다.
				if(r * 100 + c < limit) continue;
				
				if(map[r][c] == 0) {
					map[r][c] = 1;
					placement(cnt + 1, r * 100 +c);
					map[r][c] = 0;
				}
			}
		}
		
		
	}
	
	private static int countDeadBlackStone(int r, int c) {
		Queue<Node >q = new LinkedList<>();
		int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
		int cnt = 1;
		boolean isDead = true;

		q.offer(new Node(r, c));
		visited[r][c] = true;
		
		while(!q.isEmpty()) {
			Node now = q.poll();
			
			for(int i = 0 ; i < 4 ; ++i) {
				int nr = now.r + dir[i][0];
				int nc = now.c + dir[i][1];
				if(nr >= N || nr < 0 || nc >= M || nc < 0 || visited[nr][nc]) continue;
				
				if(map[nr][nc] == 0) isDead = false;
				else if(map[nr][nc] == 2) {
					q.offer(new Node(nr, nc));
					visited[nr][nc] = true;
					cnt++;
				}
			}
		}
		
		if(isDead) {
			return cnt;
		}
		return 0;
	}
	
	private static void initVisited() {
		for(int r = 0; r < N ; ++r) {
			for(int c = 0 ; c < M ; ++c) {
				visited[r][c] = false;
			}
		}
	}

	private static void print() {
		for(int r = 0; r < N ; ++r) {
			for(int c = 0 ; c < M ; ++c) {
				System.out.print(map[r][c] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}