15684번) 사다리 조작

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

음....

맨 첨에는 DP문제로 생각해서 예제를 통해서 규칙을 찾아봤어요.

규칙이 있긴 한데, 이를 구현하기는 어렵다 생각해서

DFS 방식으로 풀었어요.

어느정도 제한 조건이 있어서, 시간 초과에는 걸리지 않았네요.

사다리 삽입 가능한 부분과 삽입한 부분, 삽입 불가능한 부분을 구분하는 것이 핵심인것 같네요.

삽입 불가능한 부분 덕분에 더 효율적으로 코드를 구현할 수 있었어요.

삽입 불가능한 부분은 사다리가 놓여져있는 공간의 좌우 공간입니다.

사다리를 추가할 때마다 좌우에 추가하지 못하게끔 세팅해야해요.

그리고 i번째의 결과가 i번인지 확인하는 작업은 사다리 개수가 짝수개일때만 해야합니다.

DP방식으로 풀기위해 규칙을 찾아봤는데, 사다리의 총 개수가 짝수개여야만 가능한 규칙을 찾았어요.

시험 코드 - 다듬지 않은 코드 (소요시간 1시간 50분) import java.util.Scanner; public class Q15684 { static int result = 4, nowSadariNum = 0; static int[][] ogMap; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int verticalNum = sc.nextInt(); int count = sc.nextInt(); int horizenNum = sc.nextInt(); //0 -> 삽입 가능 //1 -> 삽입 함 //2 -> 삽입 불가능 ogMap = new int[horizenNum][verticalNum-1]; for (int i = 0; i < count; i++) { int tempY = sc.nextInt(); int tempX = sc.nextInt(); ogMap[tempY-1][tempX-1] = 1; if (0 < tempX-1) { ogMap[tempY-1][tempX-2] = 2; } if (tempX < verticalNum-1) { ogMap[tempY-1][tempX] = 2; } nowSadariNum += 1; } // showMap(ogMap); if (getSuccess(ogMap)) { System.out.println(0); return; } int[][] copyMap = new int[horizenNum][verticalNum-1]; for (int i = 0; i < ogMap.length; i++) { for (int j = 0; j < ogMap[0].length; j++) { int type = ogMap[i][j]; if (type > 0) { copyMap[i][j] = type; } } } for (int j = 0; j < copyMap.length; j++) { for (int i = 0; i < copyMap[0].length; i++) { if (copyMap[j][i] == 0) { copyMap[j][i] = 1; searchDFS(copyMap, j, i, 1); copyMap[j][i] = 0; } } } if (result == 4) { result = -1; } System.out.println(result); } static void searchDFS(int[][] map, int y, int x, int count) { if (0 < x && map[y][x-1] == 0) { map[y][x-1] = 2; } if (x+1 < map[0].length && map[y][x+1] == 0) { map[y][x+1] = 2; } // showMap(map); if ((nowSadariNum + count)%2 == 0 && getSuccess(map) && count < result) { result = count; return; } count += 1; if (3 < count) { return; } //현재 열에서도 체크하고  if (x+1 < map[0].length) { for (int i = x+1; i < map[0].length; i++) { if (map[y][i] == 0) { map[y][i] = 1; searchDFS(map, y, i, count); map[y][i] = 0; } } } //다음 열에서도 체크하고 for (int j = y+1; j < map.length; j++) { for (int i = 0; i < map[0].length; i++) { if (map[j][i] == 0) { map[j][i] = 1; searchDFS(map, j, i, count); map[j][i] = 0; } } } if (0 < x && map[y][x-1] == 2) { map[y][x-1] = ogMap[y][x-1]; } if (x+1 < map[0].length && map[y][x+1] == 2) { map[y][x+1] = ogMap[y][x+1]; } } static boolean getSuccess(int[][] map) { for (int i = 0; i < map[0].length; i++) { if (i != getResult(map, i)) { return false; } } return true; } static int getResult(int[][] map, int x) { for (int i = 0; i < map.length; i++) { if (0 <= x-1 && map[i][x-1] == 1) { x -= 1; } else if (x < map[0].length && map[i][x] == 1){ x += 1; } } return x; } static void showMap(int[][] map) { System.out.println(); for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { System.out.print("ㅣ"); int type = map[i][j]; if (type == 1) { System.out.print("─"); } else if (type == 0){ System.out.print("□"); } else { System.out.print("."); } } System.out.println("ㅣ"); } System.out.println(getSuccess(map)); } }

다듬은 코드 + 주석 추가 import java.util.Scanner; public class Q15684 { static int result = 4, nowSadariNum = 0; static int[][] ogMap; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int verticalNum = sc.nextInt(); int count = sc.nextInt(); int horizenNum = sc.nextInt(); //0 -> 삽입 가능 //1 -> 삽입 함 //2 -> 삽입 불가능 ogMap = new int[horizenNum][verticalNum-1]; for (int i = 0; i < count; i++) { int tempY = sc.nextInt(); int tempX = sc.nextInt(); ogMap[tempY-1][tempX-1] = 1; if (0 < tempX-1) { ogMap[tempY-1][tempX-2] = 2; } if (tempX < verticalNum-1) { ogMap[tempY-1][tempX] = 2; } nowSadariNum += 1; } // showMap(ogMap); if (getSuccess(ogMap)) { System.out.println(0); return; } int[][] copyMap = new int[horizenNum][verticalNum-1]; for (int i = 0; i < ogMap.length; i++) { for (int j = 0; j < ogMap[0].length; j++) { int type = ogMap[i][j]; if (type > 0) { copyMap[i][j] = type; } } } for (int j = 0; j < copyMap.length; j++) { for (int i = 0; i < copyMap[0].length; i++) { if (copyMap[j][i] == 0) { searchNext(copyMap, j, i, 1); } } } if (result == 4) { result = -1; } System.out.println(result); } static void searchNext(int[][] copyMap, int j, int i, int count) { //사다리 추가하기 copyMap[j][i] = 1; if (0 < i && copyMap[j][i-1] == 0) { copyMap[j][i-1] = 2; } if (i+1 < copyMap[0].length && copyMap[j][i+1] == 0) { copyMap[j][i+1] = 2; } searchDFS(copyMap, j, i, count); //사다리 제거하기 copyMap[j][i] = 0; if (0 < i && copyMap[j][i-1] == 2) { copyMap[j][i-1] = ogMap[j][i-1]; } if (i+1 < copyMap[0].length && copyMap[j][i+1] == 2) { copyMap[j][i+1] = ogMap[j][i+1]; } } static void searchDFS(int[][] map, int y, int x, int count) { //사다리 개수가 짝수 일때만 검사하기. (i번째가 i결과가 나오기 위해서는 사다리 개수가 짝수여야만 한다.) if ((nowSadariNum + count)%2 == 0 && getSuccess(map) && count < result) { result = count; return; } count += 1; if (3 < count) { return; } //현재 열에서 체크  if (x+1 < map[0].length) { for (int i = x+1; i < map[0].length; i++) { if (map[y][i] == 0) { searchNext(map, y, i, count); } } } //다른 열에서도 체크 for (int j = y+1; j < map.length; j++) { for (int i = 0; i < map[0].length; i++) { if (map[j][i] == 0) { searchNext(map, j, i, count); } } } } static boolean getSuccess(int[][] map) { for (int i = 0; i < map[0].length; i++) { if (i != getResult(map, i)) { return false; } } return true; } static int getResult(int[][] map, int x) { for (int i = 0; i < map.length; i++) { if (0 <= x-1 && map[i][x-1] == 1) { x -= 1; } else if (x < map[0].length && map[i][x] == 1){ x += 1; } } return x; } static void showMap(int[][] map) { System.out.println(); for (int i = 0; i < map.length; i++) { for (int j = 0; j < map[0].length; j++) { System.out.print("ㅣ"); int type = map[i][j]; if (type == 1) { System.out.print("─"); } else if (type == 0){ System.out.print("□"); } else { System.out.print("."); } } System.out.println("ㅣ"); } System.out.println(getSuccess(map)); } }