백준 14502 연구소 (자바)

백준 14502 연구소 (자바)

728x90

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class algo_14502_김어진 { static int N; static int M; static int answer = 0; static int[] dx = {-1,0,1,0}; static int[] dy = {0,1,0,-1}; public static void main(String[] args) throws Exception { System.setIn(new FileInputStream("input.txt")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st= new StringTokenizer(br.readLine(), " "); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); int[][] board= new int[N][M]; for (int i = 0; i < N; i++) { board[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); } dfs(board,-1,-1,0); System.out.println(answer); } private static void dfs(int[][] board, int row, int col,int cnt) { if(cnt==3) { int[][] tmpBoard = new int[N][M]; for (int i = 0; i < N; i++) { tmpBoard[i] = Arrays.copyOfRange(board[i], 0, M); } infect(tmpBoard); int blank = safeArea(tmpBoard); answer = Math.max(answer, blank); return; } for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if((i>row && board[i][j]==0) ||(i==row&& j>col && board[i][j]==0)) { board[i][j]=1; dfs(board,i,j,cnt+1); board[i][j]=0; } } } } private static int safeArea(int[][] board) { int blank=0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if(board[i][j]==0) { blank++; } } } return blank; } private static void infect(int[][] board) { for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if(board[i][j]==2) { bfs(board,i,j); } } } } private static void bfs(int[][] board, int x, int y) { boolean[][] check = new boolean[N][M]; Queue q=new LinkedList(); q.add(new Integer[] {x,y}); check[x][y]=true; while(!q.isEmpty()) { Integer[] pos = q.poll(); x = pos[0]; y =pos[1]; for (int i = 0; i < 4; i++) { int nx = x+dx[i]; int ny = y + dy[i]; if(nx>=0 && nx < N && ny>=0 && ny

728x90

from http://arch1tect.tistory.com/156 by ccl(A) rewrite - 2021-09-17 10:28:05