[백준]탈옥/9376 풀이 JAVA
문제
상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다.
이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다.
평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다.
감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다.
문은 중앙 제어실에서만 열 수 있다.
상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다.
하지만, 문을 열려면 시간이 매우 많이 걸린다.
두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.
첫째 줄에는 평면도의 높이 h와 너비 w가 주어진다. (2 ≤ h, w ≤ 100)
다음 h개 줄에는 감옥의 평면도 정보가 주어지며, 빈 공간은 '.', 지나갈 수 없는 벽은 '*', 문은 '#', 죄수의 위치는 '$'이다.
상근이는 감옥 밖을 자유롭게 이동할 수 있고, 평면도에 표시된 죄수의 수는 항상 두 명이다.
각 죄수와 감옥의 바깥을 연결하는 경로가 항상 존재하는 경우만 입력으로 주어진다.
출력
각 테스트 케이스마다 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 최솟값을 출력한다.
풀이
| package August; | |
| import java.awt.Point; | |
| import java.io.*; | |
| import java.util.*; | |
| public class Ex9376 { | |
| static final int BLANK = 0; // 반 공간 . | |
| static final int WALL = -1; // 벽 * | |
| static final int PRISON = 1;// 죄수 $ | |
| static final int DOOR = 2; // 문 # | |
| // 4방향 이동 | |
| static final int[] moveR = {0, -1, 0, 1}; | |
| static final int[] moveL = {-1, 0, 1, 0}; | |
| // 평면도 | |
| // (2 ≤ h, w ≤ 100) => (4 ≤ h+2, w+2 ≤ 104) | |
| static int[][] map = new int[105][105]; | |
| static int h, w; | |
| static final int INF = 10000; | |
| public static void main(String[] args) throws IOException { | |
| // T 입력 | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| int T = Integer.parseInt(br.readLine()); | |
| // T만큼 반복 | |
| while (T-- > 0) { | |
| // h, w 입력 | |
| StringTokenizer st = new StringTokenizer(br.readLine()); | |
| h = Integer.parseInt(st.nextToken()) + 2; | |
| w = Integer.parseInt(st.nextToken()) + 2; | |
| // 상근이, 죄수1, 죄수2 위치 초기화 | |
| Point sang = new Point(0, 0); | |
| Point prison1 = new Point(-1, -1); | |
| Point prison2 = new Point(-1, -1); | |
| // 평면도 입력 | |
| for (int i = 1; i < h-1; i++) { | |
| // 한줄 입력 | |
| String str = "." + br.readLine() + "."; | |
| for (int j = 0; j < w; j++) { | |
| char c = str.charAt(j); | |
| switch (c) { | |
| case '.' : // 빈 공간 | |
| map[i][j] = BLANK; | |
| break; | |
| case '*' : // 벽 | |
| map[i][j] = WALL; | |
| break; | |
| case '#' : // 문 | |
| map[i][j] = DOOR; | |
| break; | |
| case '$' : // 죄수 | |
| map[i][j] = BLANK; // PRISON 아니고 BLANK야도 똑같음 | |
| // 죄수 위치 설정하기 | |
| if (prison1.x == -1) prison1 = new Point(i, j); | |
| else prison2 = new Point(i, j); | |
| break; | |
| } | |
| } | |
| } | |
| // 평면도 맨 위와 아래도 빈 공간으로 만들어주기 | |
| for (int j = 0; j < h; j++) | |
| map[0][j] = map[h-1][j] = BLANK; | |
| // 평면도 입력 끝 | |
| // 문제 풀기 | |
| // 각 칸마다 각 사람들이 문을 열고 이동한 횟수 저장 | |
| int[][] dist1 = bfs(sang); | |
| int[][] dist2 = bfs(prison1); | |
| int[][] dist3 = bfs(prison2); | |
| int result = h*w; // 최댓값 담아두기 | |
| int tempSum = 0; // 각 사람들이 이동한 합을 담을 변수 | |
| for (int i = 0; i < h; i++) { | |
| for (int j = 0; j < w; j++) { | |
| // 벽이면 다음으로 | |
| if (map[i][j] == WALL) continue; | |
| // 벽이 아니면, 사람들이 각 칸에서 문을 몇 번 열고 갔는지 합하기 | |
| tempSum = dist1[i][j] + dist2[i][j] + dist3[i][j]; | |
| // 문이라면, 문은 1번만 열어도 되니까 -2해주기 | |
| if (map[i][j] == DOOR) tempSum -= 2; | |
| // result와 tempSum 중 더 작은 값을 result에 저장 | |
| result = result > tempSum ? tempSum : result; | |
| } | |
| } | |
| // 출력하기 | |
| System.out.println(result); | |
| } // T만큼 반복 끝 | |
| } | |
| // 문제 풀기 | |
| // 모든 경우 검사 bfs | |
| static int[][] bfs(Point p) { | |
| // p가 문을 연 횟수를 저장하기 위한 배열 생성 | |
| int[][] dist = new int[h][w]; | |
| // 아직 문을 연 적 없으니 INF로 초기화 | |
| for (int i = 0; i < h; i++) | |
| Arrays.fill(dist[i], INF); | |
| Queue<Point> queue = new LinkedList<Point>(); | |
| queue.add(p); // p의 현재 위치 넣기 | |
| dist[p.x][p.y] = 0; | |
| // queue가 빌 때까지 반복 | |
| while (!queue.isEmpty()) { | |
| // 이동할 곳 꺼내기 | |
| Point point = queue.poll(); | |
| // point 위치에서 4방향으로 이동하기 | |
| for (int i = 0; i < 4; i++) { | |
| int nextRow = point.x + moveR[i]; | |
| int nextCol = point.y + moveL[i]; | |
| // 이동할 위치로 이동할 수 있는지 검사(벽이 아닌지, 설계도 밖은 아닌지) | |
| if (isMove(nextRow, nextCol)) continue; | |
| // 이동할 위치가 빈 공간이라면 | |
| else if (map[nextRow][nextCol] == BLANK) { | |
| // 힌 번도 간 적 없거나 더 적은 문을 열고 갈 수 있는 곳이라면 | |
| if (dist[nextRow][nextCol] == INF || dist[nextRow][nextCol] > dist[point.x][point.y]) { | |
| dist[nextRow][nextCol] = dist[point.x][point.y]; | |
| queue.add(new Point(nextRow, nextCol)); // 다음에 갈 곳 큐에 저장하기 | |
| } | |
| } | |
| // 이동할 위치에 문이 있다면 | |
| else if (map[nextRow][nextCol] == DOOR) { | |
| // 힌 번도 간 적 없거나 더 적은 문을 열고 갈 수 있는 곳이라면 | |
| if (dist[nextRow][nextCol] == INF || dist[nextRow][nextCol] > dist[point.x][point.y] + 1) { | |
| dist[nextRow][nextCol] = dist[point.x][point.y] + 1; | |
| queue.add(new Point(nextRow, nextCol)); // 다음에 갈 곳 큐에 저장하기 | |
| } | |
| } | |
| } // 4방향 이동 끝 | |
| } // queue가 빌 때까지 반복 끝 | |
| return dist; | |
| } | |
| // x, y로 이동할 수 있는지 검사 | |
| static boolean isMove(int x, int y) { | |
| // (x, y)가 벽이거나 설계도 밖이면 이동할 수 없음 | |
| if (x < 0 || x >= h || y < 0 || y >= w) return true; | |
| else if (map[x][y] == WALL) return true; | |
| return false; | |
| } | |
| } |
털썩.......................
이 문제 최근에 재채점된 문젠가?
풀이 방법을 생각해내는 게 넘 어려워서 다른 사람들 풀이 봤는데
그대로 풀면 틀렸다고 나오는 거다?
뭐가 틀린지 모르겠어서 뭐가 틀렸나 하나하나 없애고 추가하고 해보니까
map 초기화를 -1로 한 게 문제였다.
-1아니라 10000(=INF)으로 하니까 문제가 바로 풀렸다.
근데 꼭 10000일 필요는 없는듯 하다. 넉넉하게 h*w 정도면 되는듯
왜냐면
// 힌 번도 간 적 없거나 더 적은 문을 열고 갈 수 있는 곳이라면
if (dist[nextRow][nextCol] == INF || dist[nextRow][nextCol] > dist[point.x][point.y])
위 코드에서 INF가 -1일 때,
dist[nextRow][nextCol]가 -1이 아니고 dist[point.x][point.y]이 -1일때 오류가 날 수 있기 때문이다.
(한 번도 간 적 없는 검사를 제대로 수행하지 못하는 문제 발생)
이것보다 메모리 적게 들고 시간도 적게 걸리는 풀이도 있긴 한데
이건 좀 더 이해를 해야할듯하다.
이거,,, 너무 어려워서 찔끔찔끔 하다보니 일주일 걸림ㄷ
그래도 해결해서 기분이 너무 좋다!!!!!!!