글 읽기 - 반례가 있을까요? 17%에서 실패하는데...

limky 4년 전 0

반례가 있을까요? 17%에서 실패하는데...

package SAMSUNG;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class BackJoon_17141 {

	static int moldNum = 0;
	static LinkedList<Point> virus = new LinkedList<>();
	static int map[][];
	static int ans = Integer.MAX_VALUE;
	static int virusCnt = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String[] strArr = str.split(" ");
		
		int n = Integer.parseInt(strArr[0]);
		int r = Integer.parseInt(strArr[1]);
		
		map = new int[n][n];
		
		for(int i=0; i<map.length; i++){
			String str1 = br.readLine();
			String[] strArr1 = str1.split(" ");
			for(int j=0; j<map[0].length; j++){
				map[i][j] = Integer.parseInt(strArr1[j]);
				if(map[i][j] != 1) moldNum++;
				if(map[i][j] == 2) {
					virusCnt++;
					virus.add(new Point(i, j));
					//map[i][j] = 3;
				}
			}
		}
		
		moldNum = moldNum - r;
		LinkedList<Integer> list = new LinkedList<>();
		combination(list, virusCnt, r, 0);
		if(ans == Integer.MAX_VALUE) ans = -1;
		System.out.println(ans);
		
	}
	static int[] dX = {0, -1, 0, 1};
	static int[] dY = {-1, 0, 1, 0};
	private static int clear(LinkedList<Integer> list, int[][] tmpMap) {
		LinkedList<Point> q = new LinkedList<>();
		for(int i=0; i<list.size(); i++){
			q.add(virus.get(list.get(i)));
		}
		
		int clearNum = 0;
		for(int n=0; ; n++){
			if(q.isEmpty()) break;
			
			int size = q.size();
			for(int num=0; num<size; num++){
				Point p = q.poll();
				for(int i=0; i<4; i++){
					int nX = p.x + dX[i];
					int nY = p.y + dY[i];
					if(-1<nX && nX<tmpMap.length && -1<nY && nY<tmpMap[0].length){
						if(tmpMap[nX][nY] == 1)continue;//벽
						if(tmpMap[nX][nY] == 0 || tmpMap[nX][nY] == 2){
							//청소대상
							clearNum++;
							tmpMap[p.x][p.y] = 3;
							tmpMap[nX][nY] = 3;
							q.add(new Point(nX, nY));
						}
						
					}
				}
				
			}
			
			
			System.out.println(n+1);
			System.out.println("먼지 수 : "+moldNum+" 청소 수 : "+clearNum);
			for(int m=0; m<tmpMap.length; m++){
				System.out.println(Arrays.toString(tmpMap[m]));
			}
			System.out.println();
			 
			if((moldNum - clearNum) == 0) {
			//	System.out.println("올바른 청소 : "+(n+1));
				if(clearNum == 0) return 0;
				return n+1;
			}
			
		}	
		
		return Integer.MAX_VALUE;

		
		
	}
	
	private static void combination(LinkedList<Integer> list, int n, int r, int index) {
		if(r == 0){//r이 0이면 다 뽑았다는 뜻
			for(int i : list){
				System.out.print(i+" ");
			}
			System.out.println("선택");
			int tmpMap[][] = copyMap();
			int tmpAns = clear(list, tmpMap);
			if(ans > tmpAns){
				ans = tmpAns;
			}
			return;
		}
		if(index == n) return; //다 탐색했으면 종료..
		
		list.add(index);
		combination(list, n, r-1, index+1);//뽑았으니 ,r-1
		list.removeLast();
		combination(list, n, r, index+1);//안뽑았으니, r
	}

	private static int[][] copyMap() {
		int [][]copyMap = new int[map.length][map[0].length];
		for(int i=0; i<map.length; i++){
			for(int j=0; j<map[0].length; j++){
				copyMap[i][j] = map[i][j];
			}
		}
		return copyMap;
	}

	

}

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

문제

문제

출처

ICPC

반례가 있을까요? 17%에서 실패하는데...

limky 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말