15683번) 감시

문제 출처 : https://www.acmicpc.net/problem/15683

음... 뭐랄까... 

제가 짠 코드의 함정을 찾는게 좀 어려웠어요.

변수명도 너무 헷갈려서 좀 어려웠네요.

2018년 5월 19일 - 다듬지 않은 코드 (소요시간 : 1시간 50분) import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; public class Q15683 { static ArrayList<CCTV> cctvList = new ArrayList<CCTV>(); static int min = 0, y, x; public static void main(String[] args) { Scanner sc = new Scanner(System.in); y = sc.nextInt(); x = sc.nextInt(); int[][] map = new int[y][x]; LinkedList<CCTV> cctv5List = new LinkedList<CCTV>(); for (int i = 0; i < y; i++) { for (int j = 0; j < x; j++) { int what = sc.nextInt(); map[i][j] = what; if (1 <= what && what <= 4) { //CCTV일 경우 cctvList.add(new CCTV(i, j, what)); } else if (what == 5) { cctv5List.add(new CCTV(i, j, what)); } } } while (!cctv5List.isEmpty()) { CCTV nowCctv = cctv5List.poll(); setCctv5(map, nowCctv.y, nowCctv.x); } for (int i = 0; i < y; i++) { for (int j = 0; j < x; j++) { if (map[i][j] == 0) { min += 1; } } } if (!cctvList.isEmpty()) { for (int i = 0; i < 4; i++) { if ( i == 2 && cctvList.get(0).what == 2) { break; } setCCTV(map, 0, i+1); } } // showMap(map); System.out.println(min); } public static void setCCTV(int[][] map, int count, int direction) { // System.out.println("카운트" + count + "\n"); int reMap[][] = new int[y][x]; for (int i = 0; i < y; i++) { for (int j = 0; j < x; j++) { reMap[i][j] = map[i][j]; } } switch (cctvList.get(count).what) { case 1: setCctv1(reMap, cctvList.get(count).y, cctvList.get(count).x, direction); break; case 2: setCctv2(reMap, cctvList.get(count).y, cctvList.get(count).x, direction); break; case 3: setCctv3(reMap, cctvList.get(count).y, cctvList.get(count).x, direction); break; case 4: setCctv4(reMap, cctvList.get(count).y, cctvList.get(count).x, direction); break; } count += 1; if (count < cctvList.size()) { //모든 cctv 검색 안했으면 다음 for (int i = 0; i < 4; i++) { if ( i == 2 && cctvList.get(count).what == 2) { break; } setCCTV(reMap, count, i+1); } } else { //모든 cctv 검색 했으면 종료 int tempResult = 0; for (int i = 0; i < y; i++) { for (int j = 0; j < x; j++) { if (reMap[i][j] == 0) { tempResult += 1; } } } if (tempResult < min) { min = tempResult; // showMap(reMap); } } } public static void setCctv1(int map[][], int y, int x, int direction) { switch (direction) { case 1 : setUp(map, y, x); break; case 2 : setRight(map, y, x); break; case 3 : setDown(map, y, x); break; case 4 : setLeft(map, y, x); break; } } public static void setCctv2(int map[][], int y, int x, int direction) { switch (direction) { case 1 : setUp(map, y, x); setDown(map, y, x); break; case 2 : setLeft(map, y, x); setRight(map, y, x); break; } } public static void setCctv3(int map[][], int y, int x, int direction) { switch (direction) { case 1 : setUp(map, y, x); setRight(map, y, x); break; case 2 : setRight(map, y, x); setDown(map, y, x); break; case 3 : setDown(map, y, x); setLeft(map, y, x); break; case 4 : setLeft(map, y, x); setUp(map, y, x); break; } } public static void setCctv4(int map[][], int y, int x, int direction) { switch (direction) { case 1 : setLeft(map, y, x); setUp(map, y, x); setRight(map, y, x); break; case 2 : setUp(map, y, x); setRight(map, y, x); setDown(map, y, x); break; case 3 : setRight(map, y, x); setDown(map, y, x); setLeft(map, y, x); break; case 4 : setDown(map, y, x); setLeft(map, y, x); setUp(map, y, x); break; } } public static void setCctv5(int map[][], int y, int x) { setUp(map, y, x); setDown(map, y, x); setLeft(map, y, x); setRight(map, y, x); } public static void setUp(int map[][], int nowY, int nowX) { for (int i = nowY-1; i >= 0; i--) { int block = map[i][nowX]; if (block == 0) { map[i][nowX] = 9; } else if (block == 6) { break; } } } public static void setDown(int map[][], int nowY, int nowX) { for (int i = nowY+1; i < y; i++) { int block = map[i][nowX]; if (block == 0) { map[i][nowX] = 9; } else if (block == 6) { break; } } } public static void setLeft(int map[][], int nowY, int nowX) { for (int i = nowX-1; i >= 0; i--) { int block = map[nowY][i]; if (block == 0) { map[nowY][i] = 9; } else if (block == 6) { break; } } } public static void setRight(int map[][], int nowY, int nowX) { for (int i = nowX+1; i < x; i++) { int block = map[nowY][i]; if (block == 0) { map[nowY][i] = 9; } else if (block == 6) { break; } } } public static void showMap(int[][] map) { for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { System.out.print(map[i][j] + " "); } System.out.println(); } System.out.println(); } } class CCTV { public int y, x, what; public CCTV(int y, int x, int what) { this.y = y; this.x = x; this.what = what; } }

2018년 5월 19일 - 다듬은 코드 import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; public class Q15683 { static ArrayList<CCTV> cctvList = new ArrayList<CCTV>(); static LinkedList<CCTV> cctv5List = new LinkedList<CCTV>(); static int mapY, mapX, minResult = 0; public static void main(String[] args) { Scanner sc = new Scanner(System.in); mapY = sc.nextInt(); mapX = sc.nextInt(); int[][] map = new int[mapY][mapX]; //지도 설정 for (int i = 0; i < mapY; i++) { for (int j = 0; j < mapX; j++) { int what = sc.nextInt(); if (what == 0) { continue; } else if (1 <= what && what <= 4) { //CCTV일 경우 cctvList.add(new CCTV(i, j, what)); } else if (what == 5) { cctv5List.add(new CCTV(i, j, what)); } map[i][j] = what; } } //CCTV 5번인 경우 미리 실행한다. setCctv5(map); //사각지대의 최대값을 설정한다. minResult = getValue(map); //CCTV의 방향을 바꾸며, 사각지대를 탐색한다. DFS if (!cctvList.isEmpty()) { searchResult(map, 0); } System.out.println(minResult); } public static void searchResult(int[][] map, int count) { for (int i = 0; i < 4; i++) { if ( i == 2 && cctvList.get(count).type == 2) { //CCTV 2번은 두번의 회전만 존재하여, 2번만 회전한다. break; } nextCctv(map, count, i+1); } } public static void setCctv5(int[][] map) { while (!cctv5List.isEmpty()) { CCTV cctv5 = cctv5List.poll(); int cctyY = cctv5.y; int cctyX = cctv5.x; setUp(map, cctyY, cctyX); setDown(map, cctyY, cctyX); setLeft(map, cctyY, cctyX); setRight(map, cctyY, cctyX); } } public static int getValue(int[][] map) { int result = 0; for (int i = 0; i < mapY; i++) { for (int j = 0; j < mapX; j++) { if (map[i][j] == 0) { result += 1; } } } return result; } public static void nextCctv(int[][] map, int count, int direction) { //지도 복사 int[][] newMap = new int[mapY][mapX]; for (int i = 0; i < mapY; i++) { for (int j = 0; j < mapX; j++) { newMap[i][j] = map[i][j]; } } //카메라 방향에 따라 사각지대 설정하기 setCctv(newMap, cctvList.get(count), direction); count += 1; if (count < cctvList.size()) { //다음 cctv가 존재하면 다음 cctv 실행 searchResult(newMap, count); } else { //모든 cctv를 실행 했으면 종료 int tempResult = getValue(newMap); if (tempResult < minResult) { minResult = tempResult; } } } public static void setCctv(int[][] map, CCTV cctv, int direction) { switch (cctv.type) { case 1: setCctv1(map, cctv.y, cctv.x, direction); break; case 2: setCctv2(map, cctv.y, cctv.x, direction); break; case 3: setCctv3(map, cctv.y, cctv.x, direction); break; case 4: setCctv4(map, cctv.y, cctv.x, direction); break; } } public static void setCctv1(int map[][], int y, int x, int direction) { switch (direction) { case 1 : setUp(map, y, x); break; case 2 : setRight(map, y, x); break; case 3 : setDown(map, y, x); break; case 4 : setLeft(map, y, x); break; } } public static void setCctv2(int map[][], int y, int x, int direction) { switch (direction) { case 1 : setUp(map, y, x); setDown(map, y, x); break; case 2 : setLeft(map, y, x); setRight(map, y, x); break; } } public static void setCctv3(int map[][], int y, int x, int direction) { switch (direction) { case 1 : setUp(map, y, x); setRight(map, y, x); break; case 2 : setRight(map, y, x); setDown(map, y, x); break; case 3 : setDown(map, y, x); setLeft(map, y, x); break; case 4 : setLeft(map, y, x); setUp(map, y, x); break; } } public static void setCctv4(int map[][], int y, int x, int direction) { switch (direction) { case 1 : setLeft(map, y, x); setUp(map, y, x); setRight(map, y, x); break; case 2 : setUp(map, y, x); setRight(map, y, x); setDown(map, y, x); break; case 3 : setRight(map, y, x); setDown(map, y, x); setLeft(map, y, x); break; case 4 : setDown(map, y, x); setLeft(map, y, x); setUp(map, y, x); break; } } public static void setUp(int map[][], int nowY, int nowX) { for (int i = nowY-1; i >= 0; i--) { int block = map[i][nowX]; if (block == 0) { map[i][nowX] = 9; } else if (block == 6) { break; } } } public static void setDown(int map[][], int nowY, int nowX) { for (int i = nowY+1; i < mapY; i++) { int block = map[i][nowX]; if (block == 0) { map[i][nowX] = 9; } else if (block == 6) { break; } } } public static void setLeft(int map[][], int nowY, int nowX) { for (int i = nowX-1; i >= 0; i--) { int block = map[nowY][i]; if (block == 0) { map[nowY][i] = 9; } else if (block == 6) { break; } } } public static void setRight(int map[][], int nowY, int nowX) { for (int i = nowX+1; i < mapX; i++) { int block = map[nowY][i]; if (block == 0) { map[nowY][i] = 9; } else if (block == 6) { break; } } } } class CCTV { public int y, x, type; public CCTV(int y, int x, int type) { this.y = y; this.x = x; this.type = type; } //시험이니깐 getter, setter 생략 }