[BOJ] 백준 17135 캐슬 디펜스

BFS도 가능 !

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int n,m,d,result;
	static int[][] map;
	static int[] archers = new int[3];
	static int[] dr = {0,-1,0};
	static int[] dc = {-1,0,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		d = Integer.parseInt(st.nextToken());
		map = new int[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());
				if(map[i][j]==1) {
					
				}
			}
		}
		combi(0,0);
		System.out.println(result);
	}
	private static void combi(int idx,int cnt) {
		if(cnt==3) {
			fight();
			return;
		}
		for(int i=idx;i<m;i++) {
			archers[cnt] = i;
			combi(i+1,cnt+1);
		}
	}
	private static void fight() {
		int castle = n;
		int cnt = 0;
		int[][] copyM = new int[n][m];
		for(int i=0;i<n;i++) {
			copyM[i] = map[i].clone();
		}
		while(castle>=0) {
			for(int i=0;i<3;i++) {
				int archer = archers[i];
				PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[2]!=b[2]?a[2]-b[2]:a[1]!=b[1]?a[1]-b[1]:a[0]-b[0]);
				pq.offer(new int[] {castle,archer,0});
				out:
				while(!pq.isEmpty()) {
					int[] curr = pq.poll();
					if(curr[2]>=d) break;
					for(int d=0;d<3;d++) {
						int nr = curr[0] + dr[d];
						int nc = curr[1] + dc[d];
						if(nr<0 || nr>=castle || nc<0 || nc>=m) continue;
						if(copyM[nr][nc]==1) {
							cnt++;
							copyM[nr][nc] = -castle;
							break out;
						}
						if(copyM[nr][nc]==-castle) break out;
						pq.offer(new int[] {nr,nc,curr[2]+1});
					}
				}
			}
			castle--;
		}
		result = Math.max(result, cnt);
	}
}