14890번) 경사로

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

2018년 4월 6일 - 시험용 코드(45분) import java.util.HashSet; import java.util.Scanner; public class Q14890 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int mapSize = sc.nextInt(); int[][] map = new int[mapSize][mapSize]; int helperSize = sc.nextInt(); for (int i = 0; i < mapSize; i++) { for (int j = 0; j < mapSize; j++) { map[i][j] = sc.nextInt(); } } int result = 0; for (int i = 0; i < mapSize; i++) { int tempResult = getResult(map[i], helperSize); // System.out.println("#" + (i+1) + " / " +  tempResult); result += tempResult; } for (int i = 0; i < mapSize; i++) { int[] route = new int[mapSize]; for (int j = 0; j < mapSize; j++) { route[j] = map[j][i]; } int tempResult = getResult(route, helperSize); // System.out.println("#" + (i+1) + " / " +  tempResult); result += tempResult; } System.out.println(result); } static int getResult(int[] route, int helperSize) { HashSet<Integer> helperPosition = new HashSet<Integer>(); int mapSize = route.length; int beforeLevel = route[0]; for (int i = 1; i < mapSize; i++) { int nowLevel = route[i]; if (beforeLevel == nowLevel) { continue; } else if (beforeLevel == nowLevel-1) { //올라가면 이전을 살펴봐야한다. if (i-helperSize >= 0) { for (int k = i-1; k >= i-helperSize; k--) { if (beforeLevel != route[k] || helperPosition.contains(k)) { return 0; } helperPosition.add(k); // System.out.println(beforeLevel); } } else { return 0; } } else if (beforeLevel == nowLevel+1) { //내려가면 다음을 봐야한다. if (i+helperSize-1 < mapSize) { helperPosition.add(i); for (int k = i+1; k < i+helperSize; k++) { if (nowLevel != route[k] || helperPosition.contains(k)) { return 0; } helperPosition.add(k); } i += helperSize-1; } else { return 0; } } else { return 0; } beforeLevel = nowLevel; } return 1; } }

위의 코드에서는 사다리를 사용한 자리를 체크하는 HashSet을 사용했다면,

아래 코드는 배열을 통해, 사다리를 사용한 자리를 체크 했습니다.

확실히 세번 풀어보니, 넘나 쉽게 느껴졌네요.

2018년 4월 12일 - 다듬지 않은 코드 (소요시간 26분) import java.util.Scanner; public class Q14890 { static int size, helperSize; public static void main(String[] args) { Scanner sc = new Scanner(System.in); size = sc.nextInt(); helperSize = sc.nextInt(); int[][] map = new int[size][size]; for (int i = 0 ; i < size; i++) { for (int j = 0 ; j < size; j++) { map[i][j] = sc.nextInt(); } } int result = 0; for (int i = 0 ; i < size; i++) { result += searchRoute(map[i]); } for (int i = 0; i < size; i++) { int[] tempMap = new int[size]; for (int j = 0; j < size; j++) { tempMap[j] = map[j][i]; } result += searchRoute(tempMap); } System.out.println(result); } static int searchRoute(int[] map) { boolean[] isUsedHelper = new boolean[size]; for (int i = 0; i < size-1; i++) { int nowBlock = map[i]; int nextBlock = map[i+1]; if (nowBlock == nextBlock) { continue; } else if (nowBlock == nextBlock-1) { //올라 갈때 -> 이전 블록 검사 if (0 <= i+1-helperSize) { //우선 놓을 만큼의 공간이 있다. for (int j = i; j >= i+1-helperSize; j--) { if (isUsedHelper[j] || nowBlock != map[j]) { return 0; } isUsedHelper[j] = true; } } else { return 0; } } else if (nowBlock == nextBlock+1) { //내려 갈때 -> 다음 블록 검사 if (i+helperSize < size) { //우선 놓을 만큼의 공간이 있다. isUsedHelper[i+1] = true; for (int j = i+2; j <= i+helperSize; j++) { if (isUsedHelper[j] || nextBlock != map[j]) { return 0; } isUsedHelper[j] = true; } //놓을 수 있다. i += helperSize-1; } else { return 0; } } else { return 0; } } return 1; } }