글 읽기 - 질문에 있는 모든 반례케이스가 다 돌아가는데.. 바로 틀렸다가 나옵니다. .

oun7204 5년 전 0

1%도 못넘기고 바로 틀렸다가 나옵니다...

반례가 있는가 싶어서 질문에 있는 모든 케이스를 해 보았는데 잘 돌아가요..

어디가 틀린건지 알 수 있을까요?

아니면 다른 반례가 있는 건가요?

도와주세요ㅜㅜ

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Beakjoon_15683 {


	int N, M;
	int[][] map;
	ArrayList<Pair> cam_list = new ArrayList<>();
	ArrayList<int[]> cam_status = new ArrayList<>();
	int Min = 100000000;
	public Beakjoon_15683() {
		// TODO Auto-generated constructor stub
		Scanner  sc  = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
	
		map = new int[N][M];
		int[][] tempMap = new int[N][M];
		for(int i = 0; i<N; i++) {
			for(int j = 0; j<M; j++) {
				
				map[i][j] = sc.nextInt();
				tempMap[i][j] = map[i][j];
				
				if(map[i][j] > 0 && map[i][j] <6) {
					cam_list.add(new Pair(i,j,0));
					int[] cam = new int[2];
					cam[0] = map[i][j];
					cam_status.add(cam);
				}
			}
		}
		
		dfs(cam_status,0,map,tempMap);
		System.out.print(Min);
		
	}
	
	public void dfs(ArrayList<int[]> cam_status,int count, int[][] map, int[][] original) {
		
		if(count == cam_status.size()) {
			
			
//			System.out.println("map[][]");
			//오면 캠 설정에 맞게 시야를 봐준다.
			for(int j=0; j<N; j++) {
				for(int k = 0;k<M; k++) {
					
					map[j][k] = original[j][k];
//					System.out.print(map[j][k] + " ");
					
				}
//				System.out.println();
			}
//			System.out.println("감시");
			
			int[] arrX = {0,0,-1,0,1};//x가 세로이다
			int[] arrY = {0,1,0,-1,0};//y는 가로이다..
			
			
			for(int i = 0; i<cam_status.size(); i++) {
				
				int currentX = cam_list.get(i).getX();
				int currentY = cam_list.get(i).getY();
				
				int currentCam_num = cam_status.get(i)[0];
				int currentCam_status = cam_status.get(i)[1];
				
				int nextX, nextY;
				
				Queue<Pair> queue = new LinkedList<>();
				
				switch(currentCam_num) {
				case 1:
					
					nextX = currentX + arrX[currentCam_status];
					nextY = currentY + arrY[currentCam_status];
					
					
					
					queue.add(new Pair(nextX,nextY,currentCam_status));
					break;
				case 2:
					
					for(int j = 0; j<2 ; j++) {
						
						int temp = j+ (currentCam_status+j)%5;
						
						if(temp == 5) {
							temp = 1;
						}
						
						nextX = currentX + arrX[temp];
						nextY = currentY + arrY[temp];
						
						queue.add(new Pair(nextX, nextY,temp));
					}
					
					break;
				case 3:
					
					for(int j = 0; j<2; j++) {
						
						int temp = j+currentCam_status;
						
						if(temp == 5) {
							temp = 1;
						}
						
						nextX = currentX + arrX[temp];
						nextY = currentY + arrY[temp];
						
						queue.add(new Pair(nextX,nextY,temp));
					}
					
					break;
				case 4:
					
					for(int j = 0; j<3; j++) {
						
						int temp = j+currentCam_status;
						
						if(temp > 4) {
							temp = temp%4;
						}
						
						nextX = currentX + arrX[temp];
						nextY = currentY + arrY[temp];
						
						queue.add(new Pair(nextX, nextY, temp));
					}
					
					break;
				case 5:
					
					for(int j=1; j<5; j++) {
						
						nextX = currentX + arrX[j];
						nextY = currentY + arrY[j];
						
						queue.add(new Pair(nextX, nextY, j));
						
					}
					break;
				}
				
				//처음거를 넣어준 다음 쭉가준다.
				
				while(!queue.isEmpty()) {
					
					Pair pair = queue.poll();
					
					currentX = pair.getX();
					currentY = pair.getY();
					
					if(currentX >=0 && currentX <N && currentY >=0 && currentY <M && map[currentX][currentY] != 6) {
						
						nextX = currentX + arrX[pair.getDirect()];
						nextY = currentY + arrY[pair.getDirect()];
						
						if(map[currentX][currentY] == 0) {
							map[currentX][currentY] = 7;
						}
						
						queue.add(new Pair(nextX, nextY, pair.getDirect()));
					}
					
					
					
//					if(nextX >=0 && nextX <N && nextY >=0 && nextY <M && map[nextX][nextY] != 6) {
//						//이 조건이면 볼 수 있다.
//						
//						if(map[nextX][nextY] == 0) {
//							map[nextX][nextY] = 7;
//						}
						
//						for(int j=0; j<N; j++) {
//							for(int k = 0;k<M; k++) {
//								
//								System.out.print(map[j][k]);
//								
//							}
//						}
						
//					}
					
					
				}
				
				
				
				
				
			}
			
			//이게 끝나면 뽑아준다.
			int sum = 0;
			for(int j=0; j<N; j++) {
				for(int k = 0;k<M; k++) {
					
//					System.out.print(map[j][k] + " ");
					if(map[j][k] == 0) {
						sum ++;
					}
					
					
				}
//				System.out.println();
			}
			
			Min = Math.min(Min, sum);
			//그리고 map 초기화 시켜준다.
			
			return;
			
			
		}
		
		for(int i= 1; i<5; i++) {
			cam_status.get(count)[1] =i;
			dfs(cam_status,count+1,map,original);
			
		}
	}
	
	
	
	class Pair{
		private int x,y, direct;
		public Pair(int x, int y, int direct) {
			this.x = x;
			this.y = y;
			this.direct =direct;
		}
		int getX() {return this.x;}
		int getY() {return this.y;}
		int getDirect() {return this.direct;}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		new Beakjoon_15683();

	}

}

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

문제

문제

출처

ICPC

질문에 있는 모든 반례케이스가 다 돌아가는데.. 바로 틀렸다가 나옵니다. .

oun7204 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말