* 핵심
문제를 하루종일 삽질하면서 풀었다.
첫번째 실수는 문제를 이해를 잘못해서 각 미로를 nCr로 조합한다는 경우를 생각하지 못했고,
두번째 실수는 visited를 매번 초기화하지 않아서 한바퀴밖에 돌지않는 경우가 발생했다.
문제를 뜯어보면 3가지 역할로 분리할 수 있다.
1. nCr 함수 : 판을 쌓는 순서를 참가자가 자유롭게 정할 수 있으므로 5!의 경우의 수가 발생
2. Rotation(DFS) 함수 : 판을 돌리는 경우의 수는 총 4가지이므로 4^5(판의 개수) 의 경우의 수 발생 >> DFS로 경우의 수 찾기
3. BFS 함수 : Rotaion으로 받은 map을 가지고 0,0,0에서 4,4,4로 가는 경우의 수를 찾는 함수
문제를 위처럼 3단계로 나누고 실수없이 구현하면 금방 풀 수 있는 문제였다.
특히, 자바는 파라미터가 Call by Reference이기 때문에 DFS 함수를 호출하고 다시 값을 변경해주는 것 또한 잊지말아야 한다.
* 문제
문제
평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다.
대회의 규칙은 아래와 같다.
- 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 칸을, 검은 칸은 참가자가 들어갈 수 없는 칸을 의미한다.
- 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. 그러나 판을 뒤집을 수는 없다.
- 회전을 완료한 후 참가자는 판 5개를 쌓는다. 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다. 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로이다. 이 때 큐브의 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸이고 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸이다.
- 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.
- 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 우승한다. 만약 미로의 입구 혹은 출구가 막혀있거나, 입구에서 출구에 도달할 수 있는 방법이 존재하지 않을 경우에는 탈출이 불가능한 것으로 간주한다.
이 대회에서 우승하기 위해서는 미로를 잘 빠져나올 수 있기 위한 담력 증진과 체력 훈련, 그리고 적절한 운이 제일 중요하지만, 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만드는 능력 또한 없어서는 안된다. 주어진 판에서 가장 적은 이동 횟수로 출구에 도달할 수 있게끔 미로를 만들었을 때 몇 번 이동을 해야하는지 구해보자.
입력
첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 의미한다.
출력
첫째 줄에 주어진 판으로 설계된 미로를 탈출하는 가장 적은 이동 횟수를 출력한다. 단, 어떻게 설계하더라도 탈출이 불가능할 경우에는 -1을 출력한다.
* 소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | import java.io.*; import java.util.*; public class Main { public static StringTokenizer stk; public static StringBuilder sb = new StringBuilder(); public static int[][][] map = new int[5][5][5]; public static boolean[][][] visited = new boolean[5][5][5]; public static int[] p = {0, 0, 0, 0, 0}; //nCr로 순서를 정할 때 idx를 저장하는 배열 public static int[] dx = {1, -1, 0, 0, 0, 0}; public static int[] dy = {0, 0, 1, -1, 0, 0}; public static int[] dh = {0, 0, 0, 0, 1, -1}; public static int ans = Integer.MAX_VALUE; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); for (int i = 0; i < 5; i++) { //높이 for (int j = 0; j < 5; j++) { //가로 stk = new StringTokenizer(br.readLine()); for (int k = 0; k < 5; k++) { //세로 map[i][j][k] = Integer.parseInt(stk.nextToken()); } } } nCr(0, new boolean[5]); System.out.println(ans == Integer.MAX_VALUE ? -1 : ans); } //참가자가 5개의 판을 쌓는 5!의 경우의 수 public static void nCr(int cnt, boolean[] visited) { if (cnt == 5) { //경우의 수를 찾았을때마다 만든 배열을 가지고 Backtracking 함수 호출 int[][][] nmap = new int[5][5][5]; for (int i = 0; i < 5; i++) { int idx = p[i]; for (int x = 0; x < 5; x++) { for (int y = 0; y < 5; y++) { nmap[i][x][y] = map[idx][x][y]; } } } Backtracking(0, new int[5][5][5], nmap); return; } for (int i = 0; i < 5; i++) { if (!visited[i]) { visited[i] = true; p[i] = cnt; nCr(cnt + 1, visited); p[i] = 0; visited[i] = false; } } return; } //dfs를 이용하여 각 높이별 회전할 때의 저장배열 public static void Backtracking(int height, int[][][] nmap, int[][][] map) { if (height == 5) { //배치한 판을 회전시킨 경우의 수마다 bfs if (nmap[0][0][0] == 1 && nmap[4][4][4] == 1) { int tmp = bfs(nmap); if (tmp != -1) ans = Math.min(ans, tmp); } return; } for (int cnt = 1; cnt <= 4; cnt++) { //반시계 돌리는 횟수 for (int i = 0; i < 5; i++) { for (int j = 0; j < 5; j++) { if (map[height][i][j] == 1) { switch (cnt) { case 1: nmap[height][j][4 - i] = 1; break; case 2: nmap[height][4 - i][4 - j] = 1; break; case 3: nmap[height][4 - j][i] = 1; break; case 4: nmap[height][i][j] = 1; break; } } } } Backtracking(height + 1, nmap, map); nmap[height] = new int[5][5]; } return; } //bfs를 이용해서 저장된 nmap을 가지고 정점가능횟수 찾는 횟수 public static int bfs(int[][][] nmap) { Queue<Point> q = new LinkedList<>(); visited = new boolean[5][5][5]; q.add(new Point(0, 0, 0, 0)); while (!q.isEmpty()) { Point p = q.poll(); if (p.height == 4 && p.x == 4 && p.y == 4) return p.cnt; if (!visited[p.height][p.x][p.y]) { visited[p.height][p.x][p.y] = true; for (int k = 0; k < 6; k++) { int nh = p.height + dh[k]; int nx = p.x + dx[k]; int ny = p.y + dy[k]; if (check(nh, nx, ny) && nmap[nh][nx][ny] == 1 && !visited[nh][nx][ny]) { q.add(new Point(nh, nx, ny, p.cnt + 1)); } } } } return -1; } public static boolean check(int h, int x, int y) { if (h >= 0 && h < 5 && x >= 0 && x < 5 && y >= 0 && y < 5) return true; return false; } public static class Point { int height, x, y, cnt; public Point(int height, int x, int y, int cnt) { this.height = height; this.x = x; this.y = y; this.cnt = cnt; } } } | cs |
'∙Algorithm' 카테고리의 다른 글
| [Algorithm] 백준/1946 :: 신입 사원 (0) | 2019.03.24 |
|---|---|
| [Algorithm] 백준/1931 :: 회의실배정 (0) | 2019.03.07 |
| [Algorithm] 백준/11057 :: 오르막 수 (0) | 2019.02.12 |
| [Algorithm] 백준/5557 :: 1학년 (0) | 2019.02.12 |