[백준-자바] N_6593 상범 빌딩

0woy·2024년 2월 20일
0

코딩테스트

목록 보기
10/40

📜 문제

  • 상, 하, 좌, 우, 위층, 아래층 이동 가능한 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차원 배열로 짰을 때, 나도 계산하기 어려웠다.


0개의 댓글