📜 문제
- 상, 하, 좌, 우, 위층, 아래층 이동 가능한 3차원 빌딩
- S에서 출발하여 E까지 도달하는 최단 시간 구하기
- 도달할 수 없는 경우
Trapped!메시지 출력
최단 시간을 구하는 문제이므로 BFS를 사용하면 된다.
S에서 출발하여 인접한 모든 정점을 방문하므로 최단시간을 구할 수 있다.
그리고 더이상 방문할 정점이 없는 경우 E까지 도달할 수 있는 길이 없음을 의미한다.
✍ 부분 코드 설명
이동 가능한 위치를 저장하는 Point 클래스 선언
static public class Point{
private int x,y,z;
Point(){this.x=-1;this.y=-1;this.z=-1;}
Point(int z, int x, int y){
this.x=x;
this.y=y;
this.z=z;
}
public void setPoint(int z, int x, int y){
this.x = x;
this.y = y;
this.z = z;
}
}Point 클래스를 이용해 시작위치, 도달위치, 그리고 인접한 칸의 위치를 저장한다.
빌딩 구조 저장하기
for(int h=0;h<height;h++){
for(int r=0;r<row;r++){
String str = br.readLine();
if(str.equals("")){
r-=1;
continue;
}
for(int c=0;c<column;c++){
switch (str.charAt(c)){
case '.':
map[h][r][c] = 1; break;
case '#':
map[h][r][c] = -1; break;
case 'S':
start.setPoint(h,r,c);
map[h][r][c] = 0; break;
case 'E':
end.setPoint(h,r,c);
map[h][r][c] = 1; break;
}
}
}
}이동 가능한 정점은 . 으로 표시하며, map 배열에서 1로 저장한다.
이동 불가한 정점은 # 으로 표시하며, map 배열에서 -1로 저장한다.
시작 위치의 경우 S로 표시하며, map 배열에서 0으로 저장하고 start 변수에 저장한다.
출구의 경우 E로 표시하며, map 배열에서 1로 저장하고 end 변수에 저장한다.
BFS 코드 작성하기
static int bfs(int [][][]map, boolean visited[][][], Point start, Point goal){
Queue<Point> que = new ArrayDeque<>();
int [] dz = {0,0,0,0,1,-1};
int [] dx = {1,-1,0,0,0,0}; // 우, 좌, 하, 상, 위층, 아래층
int [] dy = {0,0,1,-1,0,0};
visited[start.z][start.x][start.y] = true;
que.offer(start);
while(!que.isEmpty()){
Point tmp = que.poll();
for(int d=0;d<6;d++){
int nx = tmp.x+dx[d];
int ny = tmp.y+dy[d];
int nz = tmp.z+dz[d];
if(nx>=0&&ny>=0&&nz>=0&&
nx<map[0].length&&
ny<map[0][0].length&&
nz<map.length){
if(!visited[nz][nx][ny] && map[nz][nx][ny]==1){
visited[nz][nx][ny] = true;
map[nz][nx][ny] = map[tmp.z][tmp.x][tmp.y]+1;
if(nz==goal.z&&nx==goal.x&&ny==goal.y){
return map[goal.z][goal.x][goal.y];
}
que.offer(new Point(nz,nx,ny));
}
}
}
}
return -1;
}- Start 에서 시작하여 이동 가능하며 인접한 상, 하, 좌, 우, 위층, 아래층을
dx,dy,dz를 이용해 이동한다. - 탐색 중 출구의 정점을 방문한 경우, 반복문을 중단하고 출구 위치의 값을 반환한다.
- -1이 반환된 경우, 시작 위치에서 출구까지 도달할 방법이 없는 것이다.
🍳 전체 소스 코드
public class N_6593 {
static public class Point{
private int x,y,z;
Point(){this.x=-1;this.y=-1;this.z=-1;}
Point(int z, int x, int y){
this.x=x;
this.y=y;
this.z=z;
}
public void setPoint(int z, int x, int y){
this.x = x;
this.y = y;
this.z = z;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
if (!st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
int height = Integer.parseInt(st.nextToken());
int row = Integer.parseInt(st.nextToken());
int column = Integer.parseInt(st.nextToken());
if(height==0 && row==0&& column==0) break;
int [][][] map = new int[height][row][column];
boolean [][][] visited = new boolean[height][row][column];
Point start = new Point();
Point end = new Point();
for(int h=0;h<height;h++){
for(int r=0;r<row;r++){
String str = br.readLine();
if(str.equals("")){
r-=1;
continue;
}
for(int c=0;c<column;c++){
switch (str.charAt(c)){
case '.':
map[h][r][c] = 1; break;
case '#':
map[h][r][c] = -1; break;
case 'S':
start.setPoint(h,r,c);
map[h][r][c] = 0; break;
case 'E':
end.setPoint(h,r,c);
map[h][r][c] = 1; break;
}
}
}
}
int res = bfs(map,visited,start,end);
if(res!=-1) sb.append("Escaped in ").append(res).append(" minute(s).\n");
else sb.append("Trapped!\n");
}
System.out.print(sb);
}
static int bfs(int [][][]map, boolean visited[][][], Point start, Point goal){
Queue<Point> que = new ArrayDeque<>();
int [] dz = {0,0,0,0,1,-1};
int [] dx = {1,-1,0,0,0,0}; // 우, 좌, 하, 상, 위층, 아래층
int [] dy = {0,0,1,-1,0,0};
visited[start.z][start.x][start.y] = true;
que.offer(start);
while(!que.isEmpty()){
Point tmp = que.poll();
for(int d=0;d<6;d++){
int nx = tmp.x+dx[d];
int ny = tmp.y+dy[d];
int nz = tmp.z+dz[d];
if(nx>=0&&ny>=0&&nz>=0&&nx<map[0].length&&ny<map[0][0].length&&nz<map.length){
if(!visited[nz][nx][ny] && map[nz][nx][ny]==1){
visited[nz][nx][ny] = true;
map[nz][nx][ny] = map[tmp.z][tmp.x][tmp.y]+1;
if(nz==goal.z&&nx==goal.x&&ny==goal.y){
return map[goal.z][goal.x][goal.y];
}
que.offer(new Point(nz,nx,ny));
}
}
}
}
return -1;
}
}
✨ 결과
처음엔 삼중 배열이 아닌 이차원 배열을 선언하고, Point 클래스를 사용하지 않고 풀었다.
로직은 거의 똑같다고 해도 무방한데 16%에서 틀린 결과를 도출해 내어서
3차원 배열로 변경하고 Point 클래스를 사용해서 풀었더니 맞았다.
나만의 코드에 빠지지 말고 타인이 봤을 때 이해하기 쉽도록 코드를 짜야겠다.
2차원 배열로 짰을 때, 나도 계산하기 어려웠다.
