글 읽기 - 6%에서 실패인데 반례를 못찾겠습니다ㅠㅠ

tkdfhrtnalsgh 2년 전 0

질문글에 있는 테스트케이스도 다 맞게 나오는데 어디가 잘못되었을까요...ㅜㅜ

조합으로 배치할 궁수의 위치를 구하고

디펜스를 진행하며 각 궁수가 처치할 적의 위치를 bfs로 좌,상,우 순으로 탐색하며 구하였습니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int D = Integer.parseInt(st.nextToken());
		int[][] map = new int[N+1][M];
		int enemyCount = 0;
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				int temp = Integer.parseInt(st.nextToken());
				map[i][j] = temp;
				if(temp == 1) {
					enemyCount++;
				}
			}
		}
		int result = -1;
		if(M<=3) {
			result = enemyCount;
		}
		else{
			result = combination(map, D, 0, 0, enemyCount, 0);
		}
		System.out.println(result);
	}
	public static int combination(int[][] map, int d, int current, int count, int enemyCount, int sum) {
		int rowSize = map.length; int columnSize = map[0].length;
		if(count==3) {
			int[][] tempMap = Arrays.copyOf(map, rowSize);
			for(int i=0;i<rowSize;i++) {
				tempMap[i] = Arrays.copyOf(map[i], columnSize);
			}
			int[] aIndex = new int[3];
			int indexCount = 0;
			for(int i=0;i<columnSize;i++) {
				if(tempMap[rowSize-1][i]==2) {
					aIndex[indexCount++] = i;
					if(indexCount==3) {
						break;
					}
				}
			}
			int temp = defense(tempMap, aIndex, d, enemyCount, 0, sum);
			if(temp > sum) {
				sum = temp;
			}
			return sum;
		}
		else if(columnSize-current < 3-count || current==columnSize) {
			return sum;
		}
		else {
			for(int i=current; i<columnSize;i++) {
				map[rowSize-1][i] = 2;
				int temp = combination(map, d, current+1, count+1, enemyCount, sum);
				if(temp==enemyCount) {
					return temp;
				}
				if(temp>sum) {
					sum = temp;
				}
				map[rowSize-1][i] = 0;
			}
			return sum;
		}
	}
	public static int defense(int[][] map, int[] aIndex, int d, int enemyCount, int currentSum, int sum) {
		int rowSize = map.length; int columnSize = map[0].length;
		if(enemyCount+currentSum<=sum) {
			return sum;
		}
		else if(enemyCount==0) {
			if(currentSum>sum) {
				sum = currentSum;
			}
			return sum;
		}
		else {
			int[][] location = new int[3][];
			for(int i=0;i<3;i++) {
				boolean[][] check = new boolean[rowSize][columnSize];
				for(int j=0;j<columnSize;j++) {
					check[rowSize-1][j] = true;
				}
				Deque<Location> queue = new ArrayDeque<Location>();
				queue.add(new Location(rowSize-1, aIndex[i], 0));
				while(!queue.isEmpty()) {
					Location current = queue.pop();
					int r = current.x; int c = current.y;
					int depth = current.depth;
					check[r][c] = true;
					if(depth>d) {
						location[i] = new int[] {-1,-1};
						break;
					}
					if(map[r][c]==1) {
						location[i] = new int[] {r, c};
						break;
					}
					int[] direction = {0,-1, -1,0, 0,1};
					for(int j=0;j<3;j++) {
						int x = r+direction[j*2];
						int y = c+direction[j*2+1];
						if(x>=0 && y>=0 && x<map.length && y<map[0].length && !check[x][y]) {
							queue.add(new Location(x,y,depth+1));
						}
					}
				}
			}
			for(int i=0;i<3;i++) {
				int x = location[i][0]; int y = location[i][1];
				if(x!=-1 && map[x][y]==1) {
					map[x][y]=0;
					enemyCount--;
					currentSum++;
				}
			}
			for(int j=0;j<columnSize;j++) {
				if(map[rowSize-2][j]==1) {
					enemyCount--;
				}
			}
			for(int i=rowSize-2;i>0;i--) {
				map[i] = map[i-1];
			}
			int[] temp0 = new int[columnSize];
			for(int j=0;j<columnSize;j++) {
				temp0[j] = 0;
			}
			map[0] = temp0;
			return defense(map, aIndex, d, enemyCount, currentSum, sum);
		}
	}
}
class Location{
	int x; int y; int depth;
	Location(int x, int y, int depth){
		this.x = x; this.y = y; this.depth = depth;
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

6%에서 실패인데 반례를 못찾겠습니다ㅠㅠ

tkdfhrtnalsgh 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말