백준 16988 - (Java)Baaaaaaaaaduk2

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

16988번: Baaaaaaaaaduk2 (Easy)

 

1. 유형

BFS, 구현

 

2. 문제 분석

 

dfs와 bfs를 사용하는 문제였습니다.

 

• 1번 돌을 놓을 두 곳을 찾아서 돌 놓기
• 1번 돌로 둘러싸여 있는지 판단하기
  • bfs를 시작할 2번 돌 찾기
  • bfs 돌리기
    • 만약 완전히 둘러싸였으면 2번 돌 카운트

 

1번 돌 놓을 자리 찾기

2중  for문을 돌려서 아직 돌이 놓아지지 않은 자리를 찾습니다.

 

BFS를 시작할 곳을 찾습니다. 2 번돌이 놓아져 있고, 아직 방문하지 않은 곳에서 BFS시작

 

코드

import java.util.*;
import java.io.*;

public class Main {
	static int map[][], N, M, D[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }, total = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());

		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = stoi(st.nextToken());
			}
		}
		dfs(0, 0, 0);
		System.out.println(total);
	}

	static void dfs(int r, int c, int dep) {
		if (dep == 2) {
			solve();
			return;
		}
		for (int i = r; i < map.length; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j] ==0) {
					map[i][j] = 1;
					dfs(i, j, dep+1);
					map[i][j] = 0;
				}
			}
		}
	}

	static void solve() {
		boolean visit[][] = new boolean[N][M];
		int cnt = 0;
		for (int i = 0; i < visit.length; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 2 && !visit[i][j]) {
					cnt += bfs(visit, i, j);
				}
			}
		}
		total = Math.max(total, cnt);
	}

	static int bfs(boolean visit[][], int r, int c) {
		Queue<int[]> q = new LinkedList<>();
		visit[r][c] = true;
		q.add(new int[] { r, c});
		boolean findzero = false;
		int cnt = 1;
		while (!q.isEmpty()) {
			int cur[] = q.poll();
			for (int i = 0; i < 4; i++) {
				int nr = cur[0] + D[i][0];
				int nc = cur[1] + D[i][1];
				if (boundCheck(nr, nc) || visit[nr][nc] || map[nr][nc] == 1)
					continue;
				if (map[nr][nc] == 0) {
					findzero = true;
					continue;
				}
				visit[nr][nc] = true;
				q.add(new int[] { nr, nc });
				++cnt;
			}
		}
		if (findzero) {
			return 0;
		} else
			return cnt;
	}

	static boolean boundCheck(int a, int b) {
		if (a < 0 || a >= N || b < 0 || b >= M)
			return true;
		return false;
	}

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