[Gold V] 공주님을 구해라! - 17836 (Java)

문제 링크

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색

 

문제 설명

용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 무기로는 마법 벽을 통과할 수 없으며, 마법 벽을 피해 (N, M) 위치에 있는 공주님을 구출해야만 한다.

마왕은 용사를 괴롭히기 위해 공주에게 저주를 걸었다. 저주에 걸린 공주는 T시간 이내로 용사를 만나지 못한다면 영원히 돌로 변하게 된다. 공주님을 구출하고 프러포즈 하고 싶은 용사는 반드시 T시간 내에 공주님이 있는 곳에 도달해야 한다. 용사는 한 칸을 이동하는 데 한 시간이 걸린다. 공주님이 있는 곳에 정확히 T시간만에 도달한 경우에도 구출할 수 있다. 용사는 상하좌우로 이동할 수 있다.

성에는 이전 용사가 사용하던 전설의 명검 "그람"이 숨겨져 있다. 용사가 그람을 구하면 마법의 벽이 있는 칸일지라도, 단숨에 벽을 부수고 그 공간으로 갈 수 있다. "그람"은 성의 어딘가에 반드시 한 개 존재하고, 용사는 그람이 있는 곳에 도착하면 바로 사용할 수 있다. 그람이 부술 수 있는 벽의 개수는 제한이 없다.

우리 모두 용사가 공주님을 안전하게 구출 할 수 있는지, 있다면 얼마나 빨리 구할 수 있는지 알아보자.

 

입력

첫 번째 줄에는 성의 크기인 N, M 그리고 공주에게 걸린 저주의 제한 시간인 정수 T가 주어진다. 첫 줄의 세 개의 수는 띄어쓰기로 구분된다. (3 ≤ N, M ≤ 100, 1 ≤ T ≤ 10000)

두 번째 줄부터 N+1번째 줄까지 성의 구조를 나타내는 M개의 수가 띄어쓰기로 구분되어 주어진다. 0은 빈 공간, 1은 마법의 벽, 2는 그람이 놓여있는 공간을 의미한다. (1,1)과 (N,M)은 0이다.

 

출력

용사가 제한 시간 T시간 이내에 공주에게 도달할 수 있다면, 공주에게 도달할 수 있는 최단 시간을 출력한다.

만약 용사가 공주를 T시간 이내에 구출할 수 없다면, "Fail"을 출력한다.

 

풀이 (BFS)

시간 복잡도: O(N*M) 공간 복잡도 O(N*M)

아이디어: 성검 그람에 도착시 탐색을 종료하고 공주님의 방과의 거리를 (N-1-y)+(M-1-x)+time+1을 통해 한번에 계산하고

HashSet과 방문한 곳을 1로 바꾸어서 처리하는 방식을 통해 visited[][] 공간을 사용하지 않고도 중복된 공간을 들어가지 않도록 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Pos {
        int x, y;

        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pos pos = (Pos) o;
            return x == pos.x && y == pos.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }

    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());
        int T = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][M];
        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
               int n = Integer.parseInt(st.nextToken());
                map[i][j] = n;
            }
        }

        int[][] ways = {{1,0},{-1,0},{0,1},{0,-1}};
        int time = -1;
        Queue<HashSet<Pos>> queue = new LinkedList<>();
        HashSet<Pos> node = new HashSet<>();
        node.add(new Pos(0,0));
        queue.add(node);
        while(!queue.isEmpty()){
            HashSet<Pos> curs = queue.poll();
            node = new HashSet<>();
            time++;
            for (Pos cur : curs) {
                map[cur.y][cur.x] = 1;
                for (int[] way : ways) {
                    int y = cur.y+way[0];
                    int x = cur.x+way[1];
                    if(y==N-1&&x==M-1)
                        ans = Math.min(ans,time+1);
                    if(x<0||x>=M||y<0||y>=N||map[y][x]==1)
                        continue;
                    // 성검 사용
                    if(map[y][x] == 2)
                        ans = Math.min(M-1-x+N-1-y+time+1,ans);
                    node.add(new Pos(x,y));
                }
            }
            if(node.size()>=1)
                queue.add(node);

        }

        if(ans<=T)
            System.out.println(ans);
        else
            System.out.println("Fail");
    }
}

답은 맞았지만 해당 방식의 문제점 

즉 HashSet에 데이터 추가, 조회에는 시간복잡도 상으로 O(1)이 소요되지만 생각보다 느릴 수 가 있어 시간적으로 비효율적이며

HashSet은 내부적으로 해시 테이블을 사용하기에, 이는 각 요소를 저장할 때 추가적인 메타데이터(예: 해시 코드, 연결 리스트 노드 등)를 필요로 한다. 따라서 boolean 배열보다 공간적으로 비효율적일 수 있다.

 

개선된 풀이

import javax.print.DocFlavor;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Pos{
    int x,y,t;
    Pos(int x,int y, int t){
       this.x = x; this.y = y; this.t=t;
    }
}

public class Main {
    static int ans = Integer.MAX_VALUE;
    public static int sti(StringTokenizer st){
        return Integer.parseInt(st.nextToken());
    }
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = sti(st), M = sti(st), T = sti(st);
        int[][] map = new int[N][M];
        boolean[][] visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = sti(st);
            }
        }

        int[] dy = {1,-1,0,0};
        int[] dx = {0,0,1,-1};
        // Queue<Pos> q = new LinkedList<>();
        // 유의미한 차이는 없지만 메모리 오버헤드가 더 적음
        ArrayDeque<Pos> q = new ArrayDeque<>();
        q.add(new Pos(0,0,0));
        while(!q.isEmpty()){
            Pos cur = q.pollFirst();
            int x = cur.x, y = cur.y, t = cur.t;
            if(map[y][x]==2)
                ans = Math.min((N-1-y)+(M-1-x)+t,ans);
            if(y==N-1&&x==M-1)
                ans = Math.min(ans,t);
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx < 0 || nx >= M || ny < 0 || ny >= N ||
                        map[ny][nx] == 1 || visited[ny][nx])
                    continue;
                visited[ny][nx] = true;
                q.add(new Pos(nx, ny, t + 1));
            }
        }
        System.out.println(ans>T ? "Fail":ans);
    }
}