-
백준 2206, 14442Java/코딩테스트 2023. 8. 13. 22:44
------------------------- 사담 -------------------------
이 문제는 CS 스터디에서 스터디원분이 추천해준 문제이다. 왜 추천해줬었는지 기억은 안 나지만...추천해준 것만 기억하고 일단 풀었다...
벽 부수고 이동하기 문제가 시리즈로 3인가 4까지 있었던거 같은데 일단 2까지는 풀었다.
처음 2206을 풀고 이해했다면 14442는 변수만 살짝 바꿔서 쉽게 풀수 있을 것이다.
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
가장 먼저 떠올릴 수 있는 풀이법은 모든 벽 정보를 다 넣고 하나하나 탐색해보는 완전 탐색... 방식이다.
하지만 골드 3 난이도.... 그렇게 풀면 당연히 시간초과 나게 만들었다.
일단 총 칸이 최대 1000 * 1000 이고, 벽의 최대 개수도 1000 * 1000 - 2이다.
BFS를 벽 하나 없앨 때마다 돌리는 방식으로는 2%인가 거기서 바로 시간초과 난다 ㅋㅋ
따라서... BFS 밖에서 벽을 선택해서 뚫고 돌리는 방식이 아닌, 진행하면서 벽을 뚫고 왔는지 / 안 뚫고 왔는지 케이스별로 구하는 방식으로 진행해야 한다.
기존 방법대로라면 방문 배열을 2차원 배열로 하고, 마지막 칸 값을 출력했었다.
이 방문 배열을 3차원 배열로 int[row][col][2] 로 정의하여 마지막 3번째 값이 0이면 안 뚫은 상태, 1이면 이미 하나 뚫은 상태로 해서 계산하면 된다.
코드가 설명이 더 빠를 것 같아서 코드로 설명 첨부.
Pos 클래스에 isBroken이라는 변수를 담았다. 해당 Pos를 큐에서 꺼낼 때 isBroken = true라면 앞 어딘가에서 하나 부수고 진행해왔다는 뜻이 된다.
private static class Pos { int x; int y; boolean isBroken; public Pos(int x, int y, boolean isBroken) { this.x = x; this.y = y; this.isBroken = isBroken; } }만약 지도 상에서 벽을 만났다면, 이전 상태가 벽을 부순 적이 없어야 한다.
즉, poll.isBroken 값이 false여야 한다.
벽이 아닌 경우라면, 이전에 부쉈든 안 부쉈든 갈 수 있다. 대신 3차원 방문 배열의 3번째 원소값이 달라지므로, 분기를 나눠서 isBroken이 참인 경우와 거짓인 경우로 나눠 계산하고, 큐에 더해줘야 한다.
if (map[nextX][nextY] == 1) { // 벽을 만났다 // 아직 벽을 부순 적이 없고, 방문한 적이 없는 경우에만 지나가기 if (!isBroken && visited[nextX][nextY][0] == 0){ visited[nextX][nextY][1] = visited[poll.x][poll.y][0] + 1; queue.add(new Pos(nextX, nextY, true)); } } else { if (isBroken && visited[nextX][nextY][1] == 0) { visited[nextX][nextY][1] = visited[poll.x][poll.y][1] + 1; queue.add(new Pos(nextX, nextY, true)); } if (!isBroken && visited[nextX][nextY][0] == 0) { visited[nextX][nextY][0] = visited[poll.x][poll.y][0] + 1; queue.add(new Pos(nextX, nextY, false)); } }그리고 마지막에 정답을 산출하는 부분도 주의가 필요하다.
단순이 뚫는 경우 안뚫는 경우 중 최솟값으로 정답을 처리하면 아래 예시에서 틀린 답이 출력된다.
- 벽이 하나도 없는 경우 (이 경우 visited[row-1][col-1][1] = 0일 것이다.
- 벽을 무조건 뚫어야만 진행 가능한 경우 ( visited[row-1][col-1][0] = 0)
따라서 3가지 케이스 다 나눠줘야한다.
벽 뚫고도, 안 뚫고도 도달하는 경우 / 벽 하나도 없는 경우 / 벽을 안 뚫고서는 못 도달하는 경우
이렇게 케이스 다 나눠서 답안을 각각 찾아주면 된다.
// 위치에 도달했을 때 if (poll.x == row-1 && poll.y == col-1) { // 벽을 뚫는 방법 & 안 뚫는 방법 모두 도달 가능했다면 if (visited[poll.x][poll.y][0] != 0 && visited[poll.x][poll.y][1] != 0) { answer = Math.min(visited[poll.x][poll.y][0], visited[poll.x][poll.y][1]); } // 벽이 하나도 없는 경우 else if (visited[poll.x][poll.y][1] == 0){ answer = visited[poll.x][poll.y][0]; } // 벽을 안 뚫고서는 못 도달하는 경우 else if (visited[poll.x][poll.y][0] == 0){ answer = visited[poll.x][poll.y][1]; } break; }전체 코드는 아래와 같다.
answer = -1이므로 아예 도달 못했다면 -1이 출력될 것이다.
import java.util.*; import java.io.*; public class p2206 { private static int[] dirX = { -1, 1, 0, 0 }; private static int[] dirY = { 0, 0, -1, 1 }; private static int[][] map; private static int[][][] visited; private static int row, col, answer = -1; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); row = Integer.parseInt(st.nextToken()); col = Integer.parseInt(st.nextToken()); map = new int[row][col]; visited = new int[row][col][2]; for (int i = 0; i < row; i++) { String line = br.readLine(); for (int j = 0; j < col; j++) { map[i][j] = Integer.parseInt(line.substring(j, j + 1)); } } BFS(); System.out.println(answer); } private static void BFS() { Queue<Pos> queue = new LinkedList<>(); queue.add(new Pos(0,0 , false)); visited[0][0][0] = 1; while (!queue.isEmpty()) { Pos poll = queue.poll(); // 위치에 도달했을 때 if (poll.x == row-1 && poll.y == col-1) { // 벽을 뚫는 방법 & 안 뚫는 방법 모두 도달 가능했다면 if (visited[poll.x][poll.y][0] != 0 && visited[poll.x][poll.y][1] != 0) { answer = Math.min(visited[poll.x][poll.y][0], visited[poll.x][poll.y][1]); } // 벽이 하나도 없는 경우 else if (visited[poll.x][poll.y][1] == 0){ answer = visited[poll.x][poll.y][0]; } // 벽을 안 뚫고서는 못 도달하는 경우 else if (visited[poll.x][poll.y][0] == 0){ answer = visited[poll.x][poll.y][1]; } break; } for (int i = 0; i < 4; i++) { int nextX = poll.x + dirX[i]; int nextY = poll.y + dirY[i]; boolean isBroken = poll.isBroken; if (!isValid(nextX, nextY)) { continue; } if (map[nextX][nextY] == 1) { // 벽을 만났다 // 아직 벽을 부순 적이 없고, 방문한 적이 없는 경우에만 지나가기 if (!isBroken && visited[nextX][nextY][0] == 0){ visited[nextX][nextY][1] = visited[poll.x][poll.y][0] + 1; queue.add(new Pos(nextX, nextY, true)); } } else { if (isBroken && visited[nextX][nextY][1] == 0) { visited[nextX][nextY][1] = visited[poll.x][poll.y][1] + 1; queue.add(new Pos(nextX, nextY, true)); } if (!isBroken && visited[nextX][nextY][0] == 0) { visited[nextX][nextY][0] = visited[poll.x][poll.y][0] + 1; queue.add(new Pos(nextX, nextY, false)); } } } } } private static boolean isValid(int nextX, int nextY) { if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) { return false; } return true; } private static class Pos { int x; int y; boolean isBroken; public Pos(int x, int y, boolean isBroken) { this.x = x; this.y = y; this.isBroken = isBroken; } } }
https://www.acmicpc.net/problem/14442
14442번: 벽 부수고 이동하기 2
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
위의 응용버전이지만 별로 차이가 없다.
2206번과 달리, 얘는 K개까지 벽을 뚫을 수 있다.
따라서 위에선 방문배열 사이즈가 [row][col][2] 였다면, 애는 [row][col][k+1]로 해주면 된다.
아예 안 뚫는 경우부터 k개 다 뚫은 경우까지 모두를 계산하기 위해서이다.
얘도 거의 비슷한데 위에서 따로 설명한 큐에 넣는 부분 / 정답 산출하는 부분만 약간 변경하면 된다. 그리고 Pos 클래스에 boolean이 아닌 int 타입으로 부순 횟수를 기록한다.
private static class Pos { int x; int y; int broken; }똑같이 벽인 경우와 아닌 경우를 나눈다.
벽이 아닌 경우는 그냥 방문만 안 한 경우면 다 지나갈 수 있으므로 broken 변수는 그대로 두고, 방문 처리후 큐에 넣어준다.
벽인 경우라면 먼저 여태까지 부순 벽의 개수에서 한 번 더 부숴도 괜찮은지 검사 후, 아직 방문하지 않은 경우에만 방문 처리 후 큐에 넣어주면 된다.
if (map[nextX][nextY] == 0) { if (visited[nextX][nextY][broken] == 0) { visited[nextX][nextY][broken] = visited[poll.x][poll.y][broken] + 1; queue.add(new Pos(nextX, nextY, broken)); } } else { if (broken + 1 <= k) { if (visited[nextX][nextY][broken+1] == 0) { visited[nextX][nextY][broken+1] = visited[poll.x][poll.y][broken] + 1; queue.add(new Pos(nextX, nextY, broken+1)); } } }정답 출력 부분은 0~k까지 반복문을 돌려가며 가장 작은 값을 찾으면 된다.
이 때 0이라면 해당 개수만큼 뚫었을 땐 도달 못했다는 이야기니까 skip하면 된다.
if (poll.x == row-1 && poll.y == col-1) { int temp = Integer.MAX_VALUE; for (int i = 0; i <= k; i++) { if (visited[poll.x][poll.y][i] != 0) { temp = Math.min(temp, visited[poll.x][poll.y][i]); } } if (temp != Integer.MAX_VALUE) { answer = temp; } break; }전체 코드는 아래와 같다.
import java.util.*; import java.io.*; public class p14442 { private static int row, col, k, answer = -1; private static int[][] map; private static int[][][] visited; private static int[] dirX = { -1, 1, 0, 0 }; private static int[] dirY = { 0, 0, -1, 1 }; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); row = Integer.parseInt(st.nextToken()); col = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken()); map = new int[row][col]; visited = new int[row][col][k+1]; for (int i = 0; i < row; i++) { String line = br.readLine(); for (int j = 0; j < col; j++) { map[i][j] = Integer.parseInt(line.substring(j, j+1)); } } BFS(); System.out.println(answer); } private static void BFS() { Queue<Pos> queue = new LinkedList<>(); queue.add(new Pos(0, 0, 0)); visited[0][0][0] = 1; while (!queue.isEmpty()) { Pos poll = queue.poll(); if (poll.x == row-1 && poll.y == col-1) { int temp = Integer.MAX_VALUE; for (int i = 0; i <= k; i++) { if (visited[poll.x][poll.y][i] != 0) { temp = Math.min(temp, visited[poll.x][poll.y][i]); } } if (temp != Integer.MAX_VALUE) { answer = temp; } break; } for (int i = 0; i < 4; i++) { int nextX = poll.x + dirX[i]; int nextY = poll.y + dirY[i]; int broken = poll.broken; if (!isValid(nextX, nextY)) { continue; } if (map[nextX][nextY] == 0) { if (visited[nextX][nextY][broken] == 0) { visited[nextX][nextY][broken] = visited[poll.x][poll.y][broken] + 1; queue.add(new Pos(nextX, nextY, broken)); } } else { if (broken + 1 <= k) { if (visited[nextX][nextY][broken+1] == 0) { visited[nextX][nextY][broken+1] = visited[poll.x][poll.y][broken] + 1; queue.add(new Pos(nextX, nextY, broken+1)); } } } } } } private static boolean isValid(int nextX, int nextY) { if (nextX < 0 || nextX >= row || nextY < 0 || nextY >= col) { return false; } return true; } private static class Pos { int x; int y; int broken; public Pos(int x, int y, int broken) { this.x = x; this.y = y; this.broken= broken; } } }