[프로그래머스 / Java] 부대복귀

문제

https://school.programmers.co.kr/learn/courses/30/lessons/132266?language=java

프로그래머스

 

---

 

문제 개요

 강철부대의 부대원들이 여러 지역에 흩어져 특수 임무를 수행하고 있으며, 각 부대원은 주어진 지도 정보를 활용해 부대로 복귀해야 합니다. 각 지역은 번호로 구분되며, 두 지역을 연결하는 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 하지만 임무가 끝난 후 일부 경로가 사라져 특정 지역에서는 부대로 돌아올 수 없는 경우도 발생할 수 있습니다. 주어진 지역 정보와 길 정보를 바탕으로, 각 부대원이 최단시간 내에 강철부대로 복귀할 수 있는 시간을 구해야 합니다. 복귀가 불가능한 경우에는 -1을 반환합니다.

 

 

접근 방법

처음에는 간단한 dfs/bfs 문제로 생각해서 bfs로 풀었다.

 

처음에 푼 코드

import java.util.*;
class Solution {
    static boolean[][] map;
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        init(n, roads);
        
        for(int i=0; i<sources.length; i++) {
            answer[i] = bfs(sources[i], n, destination);
        }
        
        return answer;
    }
    
    public void init(int n, int[][] roads) {
        map = new boolean[n+1][n+1];
        
        for(int[] arr : roads) {
            map[arr[0]][arr[1]] = true;
            map[arr[1]][arr[0]] = true;
        }
    }
    
    public int bfs(int start, int n, int destination) {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(start, 0));
        
        boolean[] v = new boolean[n+1];
        
        while(!q.isEmpty()) {
            Pos cur = q.poll();
            if(cur.num == destination) return cur.cnt;
            
            for(int i=0; i<map[cur.num].length; i++) {
                if(map[cur.num][i] && !v[i]) {
                    q.add(new Pos(i, cur.cnt + 1));
                    v[i] = true;
                }
            }
        }
        
        return -1;
    }
    
    class Pos {
        int num, cnt;
        public Pos(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}

 

시간 초과랑 메모리 초가 발생

 

❌문제점

2차원 배열 map을 n+1로 선언했는데, n <= 100,000 이기 때문에 100,000 X 100,000 = 10,000,000,000 이라서 문제가 생긴거 같다.

 

두 번째 푼 코드

import java.util.*;
class Solution {
    static List<Integer>[] map;
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        init(n, roads);
        
        for(int i=0; i<sources.length; i++) {
            answer[i] = bfs(sources[i], n, destination);
        }
        
        return answer;
    }
    
    public void init(int n, int[][] roads) {
        map = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            map[i] = new ArrayList<>();
        }
        
        for(int[] r : roads) {
            map[r[0]].add(r[1]);
            map[r[1]].add(r[0]);
        }
    }
    
    public int bfs(int start, int n, int destination) {
        Queue<Pos> q = new LinkedList<>();
        q.add(new Pos(start, 0));
        
        boolean[] v = new boolean[n+1];
        
        while(!q.isEmpty()) {
            Pos cur = q.poll();
            if(cur.num == destination) return cur.cnt;
            
            for(int i=0; i<map[cur.num].size(); i++) {
                if(!v[map[cur.num].get(i)]) {
                    q.add(new Pos(map[cur.num].get(i), cur.cnt + 1));
                    v[i] = true;
                }
            }
        }
        
        return -1;
    }
    
    class Pos {
        int num, cnt;
        public Pos(int num, int cnt) {
            this.num = num;
            this.cnt = cnt;
        }
    }
}

 

2차원 배열이 아닌 인접 행렬로 접근한 결과 메모리 초과는 발생하지 않았지만, 시간 초과가 발생했다.

 

❌문제점

두 번째 코드는 sources배열의 길이 만큼 bfs를 수행한다. 그러면 sources * bfs(O(n+m)) 만큼 시간이 걸리게 된다. sources(500) X (n (노드의 수 100,000)  + m(간선의 수 500,000)) = 300,000,000이기 때문에 시간 초과 발생

 

최종 코드

import java.util.*;
class Solution {
    static List<Integer>[] map;
    static int[] dist;
    
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];
        init(n, roads);
        
        for(int i=0; i<sources.length; i++) {
            bfs(n, destination);
        }
        getAns(answer, sources);
        return answer;
    }
    
    public void init(int n, int[][] roads) {
        map = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            map[i] = new ArrayList<>();
        }
        
        for(int[] r : roads) {
            map[r[0]].add(r[1]);
            map[r[1]].add(r[0]);
        }
        
        dist = new int[n + 1];
        Arrays.fill(dist, -1);
    }
    
    public void bfs(int n, int destination) {
        Queue<Integer> q = new LinkedList<>();
        q.add(destination);
        
        dist[destination] = 0;
        
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(int next : map[cur]) {
                if(dist[next] == -1) {
                    dist[next] = dist[cur] + 1;
                    q.add(next);
                }
            }
        }
    }
    
    public void getAns(int[] answer, int[] sources) {
        for(int i=0; i<sources.length; i++) {
            answer[i] = dist[sources[i]];
        }
    }
    
}

 

 

destination에서 시작하는 BFS 한 번으로 모든 최단 거리를 구할 수 있다. dist[i] 배열을 만들어 모든 노드의 최단 거리를 한 번에 구하면 된다.