✅문제
✅문제 풀이
시간 복잡도
시간제한이 2초 이기 때문에 어림 잡아 코드가 2억 번 안에 프로그램이 끝나야합니다.
최단 경로를 구하는 문제이기 때문에 BFS를 사용하기 때문에 약 1000 * 1000 = 1,000,000번 코드가 실행되고
벽을 부시냐 안 부시냐를 나눠서 계산하기 때문에 총 약 2,000,000번 실행되기 때문에 BFS 알고리즘을 사용하면 충분히 시간 안에 문제를 처리할 수 있습니다.
공간복잡도
192mb가 공간 제한입니다. 1.2억개의 배열을 생성할 때 512mb가 사용되기 때문에 러프하게 잡아 30,000,000개의 배열을 사용할 수 있습니다. 저희는 BFS와 벽을 안부시냐 부시냐를 체크해야되기 때문에 최대 1000 * 1000 * 2 = 2,000,000개의 배열을 사용하므로 공간 제한 안에 충분히 배열을 사용할 수 있습니다.
풀이
BFS에서 벽을 부시냐 안부시냐를 체크해야 되기 때문에 3차원 배열을 가지고 움직인 count를 기록해 나가면됩니다.
✅Code
package graphbfs;
import java.io.*;
import java.util.*;
public class Baek2206 {
public static class Pair {
int x;
int y;
int z;
public Pair(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
}
public static int[] dx = {1, 0, -1, 0};
public static int[] dy = {0, 1, 0, -1};
public static List<List<Integer>> arrays = new ArrayList<>();
public static List<List<List<Integer>>> counts = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
for (int i = 0; i < n; i++) {
List<Integer> array = new ArrayList<>();
String line = br.readLine();
for (int j = 0; j < m; j++) {
array.add(Integer.parseInt(String.valueOf(line.charAt(j))));
}
arrays.add(array);
}
for (int k = 0; k < 2; k++) {
List<List<Integer>> count = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<Integer> c = new ArrayList<>();
for (int j = 0; j < m; j++) {
c.add(-1);
}
count.add(c);
}
counts.add(count);
}
doBfs(n, m);
int val1 = counts.get(1).get(n - 1).get(m - 1);
int val2 = counts.get(0).get(n - 1).get(m - 1);
if ( val1 == -1 && val2 == -1) {
System.out.println(-1);
} else {
if (val1 == -1) {
System.out.println(val2);
} else if(val2 == -1) {
System.out.println(val1);
} else {
System.out.println(Math.min(val1, val2));
}
}
}
public static void doBfs(int n, int m){
Queue<Pair> queue = new LinkedList<>();
queue.add(new Pair(0, 0, 0));
counts.get(0).get(0).set(0, 1);
while (!queue.isEmpty()) {
Pair pair = queue.remove();
for (int i = 0; i < 4; i++) {
int nx = pair.x + dx[i];
int ny = pair.y + dy[i];
int nz = pair.z;
if ( 0 <= nx && nx < m
&& 0 <= ny && ny < n
&& arrays.get(ny).get(nx) == 0
&& counts.get(nz).get(ny).get(nx) == -1) {
queue.add(new Pair(nx, ny, nz));
counts.get(nz).get(ny).set(nx, counts.get(pair.z).get(pair.y).get(pair.x) + 1);
}
}
if (pair.z == 0) {
for (int i = 0; i < 4; i++) {
int nx = pair.x + dx[i];
int ny = pair.y + dy[i];
int nz = pair.z + 1;
if (0 <= nx && nx < m
&& 0 <= ny && ny < n
&& arrays.get(ny).get(nx) == 1
&& counts.get(nz).get(ny).get(nx) == -1) {
queue.add(new Pair(nx, ny, nz));
counts.get(nz).get(ny).set(nx, counts.get(pair.z).get(pair.y).get(pair.x) + 1);
}
}
}
}
}
}
'알고리즘 > BFS, DFS' 카테고리의 다른 글
[Java] 백준 2638번 치즈 풀이 (0) | 2024.08.05 |
---|---|
[Java] 백준 1167 트리의 지름 풀이 (0) | 2024.08.02 |
[Java] 백준 2667번 단지번호붙이기 풀이 (0) | 2024.07.31 |
[Java] 백준 1707번 이분 그래프 풀이 (0) | 2024.07.30 |
[Java] 백준11724번 연결요소의 개수 풀이 (0) | 2024.07.30 |