13460번) 구슬탈출2

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

정답률이 22.63퍼인 이유를 알겠네요.

이 문제를 풀때, 구슬 도착 확인 방법을 

입구 근처의 모든 블록들을 파악하는 방식으로 구현했습니다.

해당 방식은 소개된 테스트 케이스를 모두 통과하지만

예외 케이스가 있기 때문에 틀렸다고 나옵니다.

아래 케이스에서 결과가 1로 나오지만 실제 정답값은 2입니다.

(입구로 가지 않았지만, 입구 근처에 있기 때문에)

# # # #

# R # #

# . O #

# # # #

따라서 현재 움직이는 방향에 따라 도착 구슬을 체크하게 구현했어요.

구슬 움직이기 구현은 12100.2048(EASY) 문제가 많은 도움 됐네요.

12100.2048(EASY) 선행학습을 안했다면 못풀거나, 소요시간이 2시간을 넘었을거에요.

2018년 4월 9일 - 다듬지 않은 시험용 코드 (소요시간 1시간 28분) import java.util.Scanner; public class Q13460 { static int result = -1, ySize, xSize; static int yGoal, xGoal; public static void main(String[] args) { Scanner sc = new Scanner(System.in); ySize = sc.nextInt(); xSize = sc.nextInt(); int[][] map = new int[ySize][xSize]; for (int i = 0 ; i < ySize; i++) { String temp = sc.next(); for (int j = 0; j < xSize; j++) { char tempChar = temp.charAt(j); int value = 0; switch (tempChar) { case '#' : value = 8; break; case 'R' : value = 1; break; case 'B' : value = 4; break; case 'O' : value = 9; yGoal = i; xGoal = j; break; } map[i][j] = value; } } // showMap(map); for (int i = 0 ; i < 4; i++) { moveBlock(i, 1, map); } System.out.println(result); } static void moveBlock(int direction, int count, int[][] map) { int[][] copyMap = new int[ySize][xSize]; switch (direction) { //상 case 0 : for (int i = 0; i < xSize; i++) { int nowPosition = 0; for (int j = 0; j < ySize; j++) { int tempValue = map[j][i]; if (tempValue == 8) { copyMap[j][i] = tempValue; nowPosition = j+1; } else if (tempValue == 9) { copyMap[j][i] = tempValue; nowPosition = j+1; } else if (tempValue == 1) { copyMap[nowPosition][i] = tempValue; nowPosition += 1; } else if (tempValue == 4) { copyMap[nowPosition][i] = tempValue; nowPosition += 1; } } } // showMap(copyMap); break; //하 case 1 : for (int i = 0; i < xSize; i++) { int nowPosition = ySize-1; for (int j = ySize-1; j >= 0; j--) { int tempValue = map[j][i]; if (tempValue == 8) { copyMap[j][i] = tempValue; nowPosition = j-1; } else if (tempValue == 9) { copyMap[j][i] = tempValue; nowPosition = j-1; } else if (tempValue == 1) { copyMap[nowPosition][i] = tempValue; nowPosition -= 1; } else if (tempValue == 4) { copyMap[nowPosition][i] = tempValue; nowPosition -= 1; } } } // showMap(copyMap); break; //좌 case 2 : for (int i = 0; i < ySize; i++) { int nowPosition = 0; for (int j = 0; j < xSize; j++) { int tempValue = map[i][j]; if (tempValue == 8) { copyMap[i][j] = tempValue; nowPosition = j+1; } else if (tempValue == 9) { copyMap[i][j] = tempValue; nowPosition = j+1; } else if (tempValue == 1) { copyMap[i][nowPosition] = tempValue; nowPosition += 1; } else if (tempValue == 4) { copyMap[i][nowPosition] = tempValue; nowPosition += 1; } } } // showMap(copyMap); break; //우 case 3 : for (int i = 0; i < ySize; i++) { int nowPosition = xSize-1; for (int j = xSize-1; j >= 0; j--) { int tempValue = map[i][j]; if (tempValue == 8) { copyMap[i][j] = tempValue; nowPosition = j-1; } else if (tempValue == 9) { copyMap[i][j] = tempValue; nowPosition = j-1; } else if (tempValue == 1) { copyMap[i][nowPosition] = tempValue; nowPosition -= 1; } else if (tempValue == 4) { copyMap[i][nowPosition] = tempValue; nowPosition -= 1; } } } // showMap(copyMap); break; } String tempResult = searchGoal(direction, copyMap); if (tempResult.equals("fail")) { return; } else if (tempResult.equals("success")) { if (result == -1) { result = count; } else if (result > count) { result = count; } return; } if (count == 10) { return; } for (int i = 0 ; i < 4; i++) { moveBlock(i, count+1, copyMap); } } static String searchGoal(int direction, int[][] map) { switch (direction) { //상 case 1: int tempValue = map[yGoal-1][xGoal]; if (tempValue == 4) { return "fail"; } else if (tempValue == 1) { if (0 <= yGoal-2 && map[yGoal-2][xGoal] == 4) { return "fail"; } else { return "success"; } } break; //하 case 0: tempValue = map[yGoal+1][xGoal]; if (tempValue == 4) { return "fail"; } else if (tempValue == 1) { if (yGoal+2 < ySize && map[yGoal+2][xGoal] == 4) { return "fail"; } else { return "success"; } } break; //좌 case 3: tempValue = map[yGoal][xGoal-1]; if (tempValue == 4) { return "fail"; } else if (tempValue == 1) { if (0 <= xGoal-2 && map[yGoal][xGoal-2] == 4) { return "fail"; } else { return "success"; } } break; //우 case 2: tempValue = map[yGoal][xGoal+1]; if (tempValue == 4) { return "fail"; } else if (tempValue == 1) { if (xGoal+2 < xSize && map[yGoal][xGoal+2] == 4) { return "fail"; } else { return "success"; } } break; } return "next"; } static void showMap(int[][] map) { System.out.println(); for (int i = 0 ; i < ySize; i++) { System.out.println(); for (int j = 0; j < xSize; j++) { int tempValue = map[i][j]; char temp = '.'; switch (tempValue) { case 8 : temp = '#'; break; case 1 : temp = 'R'; break; case 4 : temp = 'B'; break; case 9 : temp = 'O'; break; } System.out.print(temp + " "); } } System.out.println(); } }

앞의 코드는 DFS이고,

이번에는 BFS로 풀어봤어요.

소요시간은 절반정도로 (엄청)단축되네요.

(DFS 채점 시간 1분 소요, BFS 채점 시간 30초 소요)

2018년 4월 10일 - 다듬지 않은 코드 (소요시간 : 56분) import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Q13460 { static int result = -1, ySize, xSize; static int yGoal, xGoal; public static void main(String[] args) { Scanner sc = new Scanner(System.in); ySize = sc.nextInt(); xSize = sc.nextInt(); int[][] map = new int[ySize][xSize]; for (int i = 0 ; i < ySize; i++) { String tempString = sc.next(); for (int j = 0 ; j < xSize; j++) { char temp = tempString.charAt(j); switch (temp) { case '#' : map[i][j] = 8; break; case 'R' : map[i][j] = 1; break; case 'B' : map[i][j] = 4; break; case 'O' : map[i][j] = 9; yGoal = i; xGoal = j; break; } } } //BFS bfs(map); System.out.println(result); } static void bfs(int[][] map) { Queue<Maps> queue = new LinkedList<Maps>(); queue.add(new Maps(map, 0, -1)); while (!queue.isEmpty()) { Maps nowMap = queue.poll(); int[][] originalMap = nowMap.getMap(); int count = nowMap.getCount()+1; int beforeDirection = nowMap.getBeforeDirection(); int[][] movedMap; //상 if (beforeDirection != 0) { movedMap = new int[ySize][xSize]; for (int i = 0; i < xSize; i++) { int inputPosition = 0; for (int j = 0 ; j < ySize; j++) { int nowState = originalMap[j][i]; if (nowState == 8 || nowState == 9) { movedMap[j][i] = nowState; inputPosition = j+1; } else if (nowState == 1 || nowState == 4) { movedMap[inputPosition][i] = nowState; inputPosition += 1; } } } if (movedMap[yGoal+1][xGoal] == 1) { if (yGoal+2 < ySize && movedMap[yGoal+2][xGoal] == 4) { } else { result = count; return; } } else if (movedMap[yGoal+1][xGoal] != 4 && count < 10) { queue.add(new Maps(movedMap, count, 0)); } // showMap(movedMap); } //하 if (beforeDirection != 1) { movedMap = new int[ySize][xSize]; for (int i = 0; i < xSize; i++) { int inputPosition = ySize-1; for (int j = ySize-1 ; j >= 0; j--) { int nowState = originalMap[j][i]; if (nowState == 8 || nowState == 9) { movedMap[j][i] = nowState; inputPosition = j-1; } else if (nowState == 1 || nowState == 4) { movedMap[inputPosition][i] = nowState; inputPosition -= 1; } } } if (movedMap[yGoal-1][xGoal] == 1) { if (0 <= yGoal-2 && movedMap[yGoal-2][xGoal] == 4) { } else { result = count; return; } } else if (movedMap[yGoal-1][xGoal] != 4 && count < 10) { queue.add(new Maps(movedMap, count, 1)); } // showMap(movedMap); } //좌 if (beforeDirection != 2) { movedMap = new int[ySize][xSize]; for (int i = 0; i < ySize; i++) { int inputPosition = 0; for (int j = 0 ; j < xSize; j++) { int nowState = originalMap[i][j]; if (nowState == 8 || nowState == 9) { movedMap[i][j] = nowState; inputPosition = j+1; } else if (nowState == 1 || nowState == 4) { movedMap[i][inputPosition] = nowState; inputPosition += 1; } } } if (movedMap[yGoal][xGoal+1] == 1) { if (xGoal+2 < xSize && movedMap[yGoal][xGoal+2] == 4) { } else { result = count; return; } } else if (movedMap[yGoal][xGoal+1] != 4 && count < 10) { queue.add(new Maps(movedMap, count, 2)); } // showMap(movedMap); } //우 if (beforeDirection != 3) { movedMap = new int[ySize][xSize]; for (int i = 0; i < ySize; i++) { int inputPosition = xSize-1; for (int j = xSize-1 ; j >= 0; j--) { int nowState = originalMap[i][j]; if (nowState == 8 || nowState == 9) { movedMap[i][j] = nowState; inputPosition = j-1; } else if (nowState == 1 || nowState == 4) { movedMap[i][inputPosition] = nowState; inputPosition -= 1; } } } if (movedMap[yGoal][xGoal-1] == 1) { if (0 <= xGoal-2 && movedMap[yGoal][xGoal-2] == 4) { } else { result = count; return; } } else if (movedMap[yGoal][xGoal-1] != 4 && count < 10) { queue.add(new Maps(movedMap, count, 3)); } // showMap(movedMap); } } } static void showMap(int[][] map) { for (int i = 0 ; i < ySize; i++) { for (int j = 0; j < xSize; j++) { switch (map[i][j]) { case 8 : System.out.print("#"); break; case 1 : System.out.print("R"); break; case 4 : System.out.print("B"); break; case 9 : System.out.print("O"); break; default : System.out.print("."); break; } } System.out.println(); } System.out.println(); } } class Maps{ private int[][] map; private int count; private int beforeDirection; public Maps(int[][] map, int count, int beforeDirection) { this.map = map; this.count = count; this.beforeDirection = beforeDirection; } public int[][] getMap() { return map; } public int getCount() { return count; } public int getBeforeDirection() { return beforeDirection; } }