백준 2206, 14442
------------------------- 사담 -------------------------
이 문제는 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;
}
}
}