글 읽기 - 감시, 반례부탁드립니다.

imsosleepy 5년 전 0

주어진 예제는 전부 맞습니다.

반례부탁드립니다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	int N;
	int M;
	int[][] map;
	int count;
	ArrayList<Camera> list;
	public Main() {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		
		map = new int[N][M];
		list = new ArrayList<Camera>();
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				map[i][j] = sc.nextInt();
				if(map[i][j]!=0 &&map[i][j]!=6) {
					list.add(new Camera(i,j,map[i][j]));
					count++;
				}
			}
		}
		// DFS로 카메라의 방향의 경우의수들을 list에 저장한다.
		DFS(0,new ArrayList<Integer>());
		System.out.println(min);
	}
	
	// 원본 맵 복사
	int[][] mapCopy(int[][] map,int[][] copy){
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				copy[i][j] = map[i][j];
			}
		}
		return copy;
	}
	
	int min = Integer.MAX_VALUE;
	public void DFS(int cnt, ArrayList<Integer> dList) {
		if(cnt==count) {
			int area=0;
			int[][] copyMap = new int[N][M];
			copyMap = mapCopy(map, copyMap);
			for(int i=0;i<cnt;i++) {
				copyMap = checkMap(dList,copyMap);
			}
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(copyMap[i][j] == 0) area++;
				}
			}
			
			min = Math.min(min, area);
			return;
		}
		
		for(int i=0;i<4;i++) {
			dList.add(i);
			DFS(cnt+1,dList);
			dList.remove(dList.size()-1);
		}
	}
	// 카메라의 방향과 카메라의 타입으로 맵을 채운다.
	public int[][] checkMap(ArrayList<Integer> dList,int[][] map) {
		for(int i=0;i<list.size();i++) {
			Camera camera = list.get(i);
			switch(camera.type) {
			case 1: // 1번 카메라
				switch(dList.get(i)) {
				case 0:
					map = checkUp(map, camera);
					break;
				case 1:
					map = checkRight(map, camera);
					break;
				case 2:
					map = checkDown(map, camera);
					break;
				case 3:
					map = checkLeft(map, camera);
					break;
				}
				break;
			case 2: // 2번 카메라
				switch(dList.get(i)) {
				case 0:
					map = checkUp(map, camera);
					map = checkDown(map, camera);
					break;
				case 1:
					map = checkRight(map, camera);
					map = checkLeft(map, camera);
					break;
				}
				break;
			case 3: // 3번 카메라
				switch(dList.get(i)) {
				case 0:
					map = checkUp(map, camera);
					map = checkRight(map, camera);
					break;
				case 1:
					map = checkRight(map, camera);
					map = checkDown(map, camera);
					break;
				case 2:
					map = checkDown(map, camera);
					map = checkLeft(map, camera);
					break;
				case 3:
					map = checkLeft(map, camera);
					map = checkUp(map, camera);
					break;
				}
				break;
			case 4: // 4번 카메라
				switch(dList.get(i)) {
				case 0:
					map = checkUp(map, camera);
					map = checkRight(map, camera);
					map = checkLeft(map, camera);
					break;
				case 1:
					map = checkRight(map, camera);
					map = checkLeft(map, camera);
					map = checkDown(map, camera);
					break;
				case 3:
					map = checkUp(map, camera);
					map = checkRight(map, camera);
					map = checkDown(map, camera);
					break;
				case 4:
					map = checkUp(map, camera);
					map = checkLeft(map, camera);
					map = checkDown(map, camera);
					break;
				}
				break;
			case 5: // 5번 카메라
				map = checkUp(map, camera);
				map = checkRight(map, camera);
				map = checkLeft(map, camera);
				map = checkDown(map, camera);
				break;
			}
		}
		
		return map;
	}
	
	
	
	public int[][] checkUp(int[][] map, Camera camera) {
		for(int i=camera.x-1;i>=0;i--) {
			if(map[i][camera.y] == 6) break;
			else map[i][camera.y] = 9;
		}
		return map;
	}
	public int[][] checkDown(int[][] map, Camera camera) {
		for(int i=camera.x+1;i<N;i++) {
			if(map[i][camera.y] == 6) break;
			else map[i][camera.y] = 9;
		}
		return map;
	}
	public int[][] checkRight(int[][] map,Camera camera) {
		for(int i=camera.y+1;i<M;i++) {
			if(map[camera.x][i] == 6) break;
			else map[camera.x][i] = 9;
		}
		return map;
	}
	public int[][] checkLeft(int[][] map,Camera camera) {
		for(int i=camera.y-1;i>=0;i--) {
			if(map[camera.x][i] == 6) break;
			else map[camera.x][i] = 9;
		}
		return map;
	}
	
	class Camera {
		int x;
		int y;
		int type;
		int direction;
		public Camera(int x, int y, int type) {
			this.x = x;
			this.y = y;
			this.type = type;
		}
		public Camera(int x, int y, int type,int direction) {
			this.x = x;
			this.y = y;
			this.type = type;
			this.direction = direction;
		}
		
	}
	
	
	public static void main(String[] args) {
		new Main();
	}

}

djm03178 5년 전 7

반례 몇 개 드립니다.

5
6 0 0 6
6 6 2 0
6 6 4 0
6 3 0 6
0 0 5 0
0 6 6 0
0 6 0 4
6 6 6 0
output: 9
correct answer: 8

5
0 0 0 6
4 1 6 6
0 6 0 6
6 0 3 6
6 0 1 6
6 0 5 6
6 6 5 6
output: 4
correct answer: 3

7
0 0 0 0 0 6
6 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 4
0 0 0 0 6 0
0 6 3 0 2 0
output: 16
correct answer: 15

imsosleepy 5년 전 0

120줄의 switch문의 오타와

카메라를 덮어쓰는경우를 고려안했네요

답변감사합니다.

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

문제

문제

출처

ICPC

감시, 반례부탁드립니다.

imsosleepy 5년 전 0

djm03178 5년 전 7

imsosleepy 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말