백준 6593번 상범 빌딩
https://www.acmicpc.net/problem/6593
문제설명
- 빌딩의 정보가 주어진다. ( .(점)은 이동가능 / #은 이동불가능 )
- L층 R행 C열의 크기로 이루어진 빌딩
- 시작점과 도착점은 하나만 존재 - 여기서 탈출할 수 있는 최단거리를 찾는 문제.
접근
BFS로 접근
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static char map[][][];
static int dist[][][];
// static int z, x, y;
static int[] dx = {0, 0, -1, 0, 1, 0};
static int[] dy = {0, 0, 0, 1, 0, -1};
static int[] dz = {-1, 1, 0, 0, 0, 0};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start_x = 0;
int start_y = 0;
int start_z = 0;
int end_x = 0;
int end_y = 0;
int end_z = 0;
int l = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
if(l==0 && r==0 && c==0)
break;
map = new char[l][r][c];
dist = new int[l][r][c];
for (int i = 0; i < l; i++) {
for (int j = 0; j < r; j++) {
String temp = br.readLine();
for (int k = 0; k < c; k++) {
if (temp.charAt(k) == 'S') {
start_z = i;
start_x = j;
start_y = k;
}
if (temp.charAt(k) == 'E') {
end_z = i;
end_x = j;
end_y = k;
}
map[i][j][k] = temp.charAt(k);
}
}
String space = br.readLine();
}
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{start_z, start_x, start_y});
while (!q.isEmpty()) {
int[] temp = q.poll();
int z = temp[0];
int x = temp[1];
int y = temp[2];
for (int i = 0; i < 6; i++) {
int nz = z + dz[i];
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nz < 0 || nx >= r || ny >= c || nz >= l) continue;
if (map[nz][nx][ny] == '#' || dist[nz][nx][ny] != 0) continue;
q.offer(new int[]{nz, nx, ny});
dist[nz][nx][ny] = dist[z][x][y] + 1;
}
}
int ans = dist[end_z][end_x][end_y];
if(ans== 0)
System.out.println("Trapped!");
else{
System.out.println("Escaped in " + ans + " minute(s).");
}
}
}
}
풀이
1. x,y,z축 좌표를 움직일 dx,dy,dz선언
2. 빌딩의 정보를 받을 map, 시작점으로부터 해당 좌표까지의 거리를 담을 dist선언
3. 행과열 크기 받고 빌딩의 정보를 입력받는다.
4. 입력받으며 S(시작점), E(도착점)의 좌표를 담아둔다. (start_x,start_y,start_z / end_x,end_y,end_z)
5. 다른 최단거리 BFS와 같이 거리를 1씩 추가하면서 이동
6. while이 끝나고 도착지점이 거리가 0이아니라면(탈출가능하다면) 해당 값, 0이면 불가능 처리
'알고리즘 > 백준 Baekjoon' 카테고리의 다른 글
백준 2573번 빙산(JAVA) - BFS/DFS (0) | 2023.05.02 |
---|---|
백준 3184번 양(JAVA) - DFS (0) | 2023.05.01 |
백준 5014번 스타트링크(JAVA) - BFS (0) | 2023.05.01 |
백준 4963번 섬의 개수(JAVA) - DFS (1) | 2023.05.01 |
백준 11659 구간 합 구하기 4(JAVA) - DP(Dynamic Programming) (0) | 2023.04.01 |