글 읽기 - 올라와 있는 예제데이터를 다 통과하였지만 틀렸습니다가 나옵니다

qdae123 4년 전 0

어디가 틀렸는지 확인받고 싶습니다 ㅠㅠ
import java.util.Scanner;

/**
 * 백준 15683. 감시 
 * 
 * @author ksh
 * 
 * 1~5번 CCTV
 * 		> 감시 방향에 있는 칸 전체 감시 
 * 		> 벽은 통과 불가 
 * 		> 감시 못하면 사각지대 
 * 		> 회전은 90도 -> 1~5번의 상, 하, 좌, 우 방향을 다 만들어 놓고 모든 케이스 계산 (중복 순열 4^5)
 * 		> 	CCTV는 CCTV 통과 가능 
 * 
 * 사각지대 최소 크기는? 
 */
public class Main {
	static class Dir {
		int[] dr;
		int[] dc;
		Dir(int[] dr, int[] dc) {
			this.dr = dr;
			this.dc = dc;
		}
	}
	
	static class CCTV {
		Dir[] dir;
		CCTV (Dir[] dir) {
			this.dir = dir;
		}
	}
	
	// CCTV1
	// 상 - 상
	// 하 - 하
	// 좌 - 좌
	// 우 - 우
	static CCTV cctv1 = new CCTV(
			new Dir[] {
					new Dir(new int[]{-1}, new int[]{0}),
					new Dir(new int[]{1}, new int[]{0}),
					new Dir(new int[]{0}, new int[]{-1}),
					new Dir(new int[]{0}, new int[]{1})
			}
	);
	
	//CCTV2
	// 상 - 상, 하  
	// 하 - 상, 하 
	// 좌 - 좌, 우 
	// 우 - 좌, 우 
	static CCTV cctv2 = new CCTV(
			new Dir[] {
						new Dir(new int[]{-1, 1}, new int[]{0, 0}),
						new Dir(new int[]{-1, 1}, new int[]{0, 0}),
						new Dir(new int[]{0, 0}, new int[]{-1, 1}),
						new Dir(new int[]{0, 0}, new int[]{-1, 1})
			}
	);

	
	//CCTV3
	// 상 - 상, 우 
	// 하 - 하, 우 
	// 좌 - 하, 좌 
	// 우 - 상, 좌 
	static CCTV cctv3 = new CCTV(
			new Dir[] {
						new Dir(new int[]{-1, 0}, new int[]{0, 1}),
						new Dir(new int[]{1, 0}, new int[]{0, 1}),
						new Dir(new int[]{1, 0}, new int[]{0, -1}),
						new Dir(new int[]{-1, 0}, new int[]{0, -1})
			}
	);
	
	//CCTV4
	// 상 - 상, 좌, 우  
	// 하 - 하, 좌, 우  
	// 좌 - 상, 하, 좌
	// 우 - 상, 하, 우 
	static CCTV cctv4 = new CCTV(
			new Dir[] {
						new Dir(new int[]{-1, 0, 0}, new int[]{0, -1, 1}),
						new Dir(new int[]{-1, 0, 0}, new int[]{0, -1, 1}),
						new Dir(new int[]{-1, 1, 0}, new int[]{0, 0, -1}),
						new Dir(new int[]{-1, 1, 0}, new int[]{0, 0, 1})
			}
	);
	
	// CCTV5
	// 상 - 상, 하, 좌, 우
	// 하 - 상, 하, 좌, 우
	// 좌 - 상, 하, 좌, 우
	// 우 - 상, 하, 좌, 우
	static CCTV cctv5 = new CCTV(
			new Dir[] {
						new Dir(new int[]{-1, 1, 0, 0}, new int[]{0, 0, -1, 1}),
						new Dir(new int[]{-1, 1, 0, 0}, new int[]{0, 0, -1, 1}),
						new Dir(new int[]{-1, 1, 0, 0}, new int[]{0, 0, -1, 1}),
						new Dir(new int[]{-1, 1, 0, 0}, new int[]{0, 0, -1, 1})
			}
	);
	
	static CCTV[] cctvList = {cctv1, cctv2, cctv3, cctv4, cctv5};
	
	static int N, M;
	static int[][] map;
	static int Cnt;
	static int wall;
	static int ans = Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		map = new int[N][M];
		
		for(int r = 0; r < N; r++) {
			for(int c = 0; c < M; c++) {
				map[r][c] = sc.nextInt();
				if(map[r][c] != 0 && map[r][c] !=6) {
					Cnt++;
				}
				
				if(map[r][c] == 6) {
					wall++;
				}
			}
		}
		
		sel = new int[Cnt];
		reperm(0);
		
		System.out.println(ans);
	}
	
	static int[] sel;
	static void reperm(int s_idx) {
		if(s_idx == Cnt) {
			
			int cctvCnt = -1;
			visited = new boolean[N][M];
			
			for(int r = 0; r < N; r++) {
				for(int c = 0; c < M; c++) {
					if(map[r][c] != 0 && map[r][c] !=6) {
						cctvCnt++;
						
						solve(r, c, map[r][c]-1, sel[cctvCnt]);
					}
				}
			}
			
			int temp = 0;
			for(int r = 0; r < N; r++) {
				for(int c = 0; c < M; c++) {
					if(!visited[r][c]) {
						temp++;
					}
				}
//				System.out.println(Arrays.toString(visited[r]));
			}
//			System.out.println(temp-Cnt-wall);
			ans = Math.min(ans, temp-Cnt-wall);
			return;
		}
		
		for(int i = 0; i <4; i++) {
			sel[s_idx] = i;
			reperm(s_idx+1);
		}
	}
	
	static boolean[][] visited;
	static void solve(int r, int c, int cctvType, int direction) {
		CCTV cur = cctvList[cctvType];
		Dir dir = cur.dir[direction];
		
		int dirSize = dir.dr.length;
		for(int i = 0; i < dirSize; i++) {
			int nr = r + dir.dr[i];
			int nc = c + dir.dc[i];
			while (nr >= 0 && nr < N && nc >= 0 && nc <M) {

				if(map[nr][nc] == 6) {
					break;
				}
				
				if(map[nr][nc] == 0) {					
					visited[nr][nc] = true;
				}
				
				nr = nr + dir.dr[i];
				nc = nc + dir.dc[i];
			}
		}
	}
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

올라와 있는 예제데이터를 다 통과하였지만 틀렸습니다가 나옵니다

qdae123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
