https://www.acmicpc.net/problem/2206
지난번에 스터디에서 한번 시도해봤을 때 실패했었는데,
이번에 다시 풀어봤지만 아이디어가 시간초과 뜨는 방법만 생각나서 또 실패했다..!!
조만간 또 풀어보겠습니다,,
풀이 참고한 자료들
이 문제에서는, 벽을 하나씩 부술 수 있는 경우의 수를 어떻게 관리할지가 관건이다.
🌱 1) 시간복잡도 계산하기
내 머릿속에서는 벽 위치 정보들를 ArrayList에 담고, 해당 벽을 하나씩 부숴보면서 일일이 BFS를 돌리는 방법밖에 생각이 나지 않았는데,,
이러면, 시간초과가 뜬다.
왜냐하면!
BFS 한 번 돌 때마다 전체 맵을 탐색해야 하므로 O(n * m)의 시간이 소요되는데,
벽 또한 최대 O(n * m)개가 존재할 수 있기 때문에
최대 시간복잡도는 O((nm)^2) 가 되어버린다.
n <= 1000, m <= 1000 이니까
O((nm)^2) = 1000000 * 1000000 >= 1억 이어서,
이 문제에서 제한된 시간 2초 안에 해결이 불가능하다..
그러면! 더 시간이 안 걸리는 새로운 방법을 찾아야 한다.
🌱 2) 이 문제를 해결하는 키 포인트
이 문제에서는,
- 큐에서 하나씩 꺼내면서 지금 현재 위치의 벽을 부술지/안 부술지 여부를 결정해야 하고,
- 지금 위치까지 오면서 벽을 하나 부쉈었는지 / 안 부쉈었는지 여부를 알아야 한다.
이를 위해서는 한 위치에 대해 x, y 정보 외에도 지금까지 벽을 하나 부쉈는지 여부 정보도 같이 함께 담아야 한다.
따라서 3차원 배열이 필요해진다.
그래서 int[][][] dist = new int[n][m][2]로 진행한다.
이때
dist[x][y][0]: 벽을 하나도 부수지 않고 (x,y)까지 오는데 걸리는 비용dist[x][y][1]: 벽을 하나 부수고 (x,y)까지 오는데 걸리는 비용
을 의미한다.
그리고 큐에 담을 노드 값도 아래와 같이 3가지 정보를 모두 담도록 설정해주었다.
class Node {
int x;
int y;
int broken;
Node (int x, int y, int broken) {
this.x = x;
this.y = y;
this.broken = broken;
}
}BFS를 진행하면서 큐에서 하나 꺼냈을 때,
[x][y][0]인 경우에는,
상하좌우 다음 위치 (nx,ny)의 벽을 부수는 경우(즉, [nx][ny][1]의 경우)에 대해서도 큐에 새로 담아주면 된다.
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
// (nx, ny)로 이동 가능하고 아직 방문 x 인 경우
if (map[nx][ny] == 0 && dist[nx][ny][now.broken] == 0) {
dist[nx][ny][now.broken] = nextDist;
q.offer(new Node(nx, ny, now.broken));
}
// (nx, ny)를 부수는 경우
if (now.broken == 0 && map[nx][ny] == 1 && dist[nx][ny][1] == 0) {
dist[nx][ny][1] = nextDist;
q.offer(new Node(nx, ny, 1));
}
}그리고 만약 큐에서 하나 꺼냈을 때, 그 위치가 (n-1, m-1)이라면 그냥 그게 빨리 도착한 경우의 수이기 때문에,
return dist[now.x][now.y][now.broken];을 해주면 된다.
위의 코드에서 볼 수 있듯이, now.broken == 1인 경우(이미 하나 부수고 온 경우)에 대해서는 처리를 하지 않기 때문에 딱 벽 하나만 부순다는 구현이 가능하다.
🌱 3) 헷갈리는 부분 정리..
실은 근데 코드 진행을 보면 납득이 가는데,
이걸 내가 떠올리기가 쉽지 않은 것 같아서,, 헷갈리는 부분을 조금 정리해보자면,,
[x][y][1]에 대해 내가 헷갈린 점 정리
[x][y][1]인 경우는, 어느 위치에서 부수고 온건지는 상관 없고 그냥 내가 (x,y)자리까지 오기까지 한번 부수고 온상태라는 부쉈는지 아닌지 여부 정보가 더 중요한 것이다!!- BFS를 진행할 때
(0,0)부터 상하좌우 가까운 순으로 하나씩 진행하면서 오니까,
큐에서 꺼냈을 때가 바로 이 자리에 도착하기까지 가장 적은 비용으로 온 것을 의미한다!
그래서[x][y][1]이 의미하는 것은
"
(x,y)자리로 오기까지 벽을 하나 부수고 와서,
너는 앞으로 벽을 부술 수 없는 상태이고,
가장 빠른 비용이dist[x][y][1]이다!
"
라는 뜻이다!!
[][][0]이든 [][][1] 이든 상관 없이(즉, 벽을 부수고 왔는지 상관 없이)
큐에서 꺼냈을 때 (n-1, m-1) 위치라면?
-> 그게 바로 가장 빠르게 도착하는 거리로 왔다는 뜻이다!
그래서 dist[n-1][m-1][큐에서 꺼낸 노드 값의 broken값] 을 리턴해주면 된다!
큐에서 꺼내는 현재 이 노드 값이 현재 자리로 오기까지 가장 빠르게 오는 비용임을 잊지 말자!!
🌱 전체 코드
import java.util.*;
import java.io.*;
public class Main {
static int n, m;
static int[][] map;
static int[][][] dist;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {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());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
map = new int[n][m];
dist = new int[n][m][2];
// dist[x][y][0] : 벽을 하나도 부수지 않고 (x,y)까지 오는 데 걸리는 비용
// dist[x][y][1] : 벽을 하나만 부수고 (x,y)까지 오는 데 걸리는 비용 - ((x,y)가 벽이라서 부수는 경우 포함)
String line;
for (int i = 0; i < n; i++) {
line = br.readLine();
for (int j = 0; j < m; j++) {
map[i][j] = line.charAt(j) - '0';
}
}
System.out.println(bfs());
}
static int bfs() {
Queue<Node> q = new LinkedList<>();
q.add(new Node(0, 0, 0));
dist[0][0][0] = dist[0][0][1] = 1;
while (!q.isEmpty()) {
Node now = q.poll();
if (now.x == n-1 && now.y == m-1) return dist[now.x][now.y][now.broken];
int nextDist = dist[now.x][now.y][now.broken] + 1;
for (int i = 0; i < 4; i++) {
int nx = now.x + dx[i];
int ny = now.y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (map[nx][ny] == 0 && dist[nx][ny][now.broken] == 0) {
dist[nx][ny][now.broken] = nextDist;
q.offer(new Node(nx, ny, now.broken));
}
// (nx, ny)를 부수는 경우
if (now.broken == 0 && map[nx][ny] == 1 && dist[nx][ny][1] == 0) {
dist[nx][ny][1] = nextDist;
q.offer(new Node(nx, ny, 1));
}
}
}
return -1;
}
}
class Node {
int x;
int y;
int broken;
Node (int x, int y, int broken) {
this.x = x;
this.y = y;
this.broken = broken;
}
}