[프로그래머스] 배달(JAVA)

Summer/Winter Coding(~2018) - 배달

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

문제 설명

마을의 개수가 N으로 주어지고

각 마을마다 이동에 필요한 시간이 주어진다.

배달원이 배달에 쓸수 있는시간 K가 주어진다.

K시간 내에 배달원이 배달을 할 수 있는 마을이 몇개인지 구하는 문제이다.

---

문제 풀이

생각 과정

새로운 클래스를 생성하지 않고 풀어보기로 했다.

우선 각 마을들이 연결된 정보를 담고있는 배열리스트를 생성한다.

크기는 마을의 인덱스를 1부터 그대로 사용하기 위해 N+1로 생성했다.

List<Integer>[] list = new ArrayList[N+1];

 

다음으로 마을이동에 필요한 시간을 이중배열로 선언한다.

int[][] times = new int[N+1][N+1] 

times[i][j] 는 i번째 마을에서 j번째 마을로 이동하는데 걸리는 시간이다.

 

큐를 이용하여 bfs를 구현했다.

큐에 첫 마을번호인 1을 입력하고

반복문 안에서 1번 마을과 연결된 마을들을 큐에 넣는다.

이 과정에서 중복방문체크를 해주고 시간을 갱신해준다.

 

정답배열을 따로 구현해주지 않고 남는 times[0]번 배열을 사용했다.

이런 과정에 따라 구현했는데 첫 시도는 실패했다.

---

구현

class Fail{
        public int solution(int N, int[][] road, int K) {
            int answer = 0;
            boolean[][] visit = new boolean[N+1][N+1];
            int[][] times = new int[N+1][N+1];
            List<Integer>[] list = new ArrayList[N+1];
            for(int i=0;i<=N;i++){
                list[i] = new ArrayList<>();
                Arrays.fill(times[i], 25000000);
            }
            for(int i =0;i<road.length;i++){
                int from = road[i][0];
                int to = road[i][1];
                int time = road[i][2];
                list[from].add(to);
                list[to].add(from);
                times[from][to] = Math.min(times[from][to], time);
                times[to][from] = Math.min(times[to][from], time);
            }
            Queue<Integer> q = new LinkedList<>();
            q.add(1);
            times[0][1] = 0;
            while(!q.isEmpty()){
                int cur = q.poll();
                for(int i=0; i<list[cur].size(); i++){
                    int next = list[cur].get(i);
                    if(visit[cur][next]) continue;
                    visit[cur][next] = true;
                    q.add(next);
                    times[0][next] = Math.min(times[0][next], times[0][cur] + times[cur][next]);
                }
            }
            for(int t : times[0]){
                System.out.println(t);
                if(t<=K) answer++;
            }
            return answer;
        }
    }

이렇게 풀었을 때 59점으로 절반의 테스트케이스를 틀렸다.

이유를 찾아봤는데 반례는 다음과 같았다.

이런 경우에 과정을 살펴보면

Queue = [1], 정답배열=[0,inf,inf,inf]

Queue = [2,3], 정답배열=[0,5,2,inf], visit[1][2] 와 visit[1][3] 체크

Queue = [3,4], 정답배열=[0,5,2,8], visit[2][4] 체크

Queue = [4,2], 정답배열=[0,3,2,8], visit[3][2] 체크

Queue = [2], 정답배열=[0,3,2,8]

이 다음이 문제였다. 2번 마을까지 가는 최소 시간이 갱신됐지만 visit[2][4]를 체크해버려서

2번마을에서 4번마을로 가는 최소시간을 새롭게 갱신할 수 없었다.

이를 해결하기 위해 i번 마을로 가는 최소시간이 갱신된 경우는 visit[i] 배열을 초기화 시켜서 해결했다.

    class Success {
        public int solution(int N, int[][] road, int K) {
            int answer = 0;
            boolean[][] visit = new boolean[N+1][N+1];  // visit[i][j] = i에서 j로가는 중복체크 배열
            int[][] times = new int[N+1][N+1];  // times[i][j] = i에서 j로 가는데 걸리는 시간
            List<Integer>[] list = new ArrayList[N+1];  // list.get(i) = i마을에 연결되어있는 마을 리스트
            for(int i=0;i<=N;i++){
                list[i] = new ArrayList<>();
                Arrays.fill(times[i], 25000000);    // 정답배열을 처음엔 큰값으로 입력
            }
            for(int i =0;i<road.length;i++){
                int from = road[i][0];
                int to = road[i][1];
                int time = road[i][2];
                list[from].add(to);     // 양방향 그래프이므로 양방향을 다 넣는다.
                list[to].add(from);
                times[from][to] = Math.min(times[from][to], time);
                times[to][from] = Math.min(times[to][from], time);
            }
            Queue<Integer> q = new LinkedList<>();
            q.add(1);
            times[0][1] = 0;
            while(!q.isEmpty()){
                int cur = q.poll();
                for(int i=0; i<list[cur].size(); i++){
                    int next = list[cur].get(i);
                    if(visit[cur][next]) continue;
                    visit[cur][next] = true;
                    q.add(next);
                    int newTime = times[0][cur] + times[cur][next];
                    if (newTime <times[0][next]){   // 새롭게 갱신된 경우 다시 해당 마을에 연결된 시간을 다시 구해야하므로 visit배열 초기화
                        times[0][next] = newTime;
                        Arrays.fill(visit[next],false);
                    }
                }
            }
            for(int t : times[0]){  // 정답배열을 돌면서 K보다 작으면 카운트
                System.out.println(t);
                if(t<=K) answer++;
            }
            return answer;
        }
    }

---

주의점

다른 풀이 방법으로는 모든 경우를 계산하는 플로이드 와샬알고리즘도 사용할 수 있을 것 같다.

양방향 그래프이므로 list와 times를 채울 때 [from][to] 와 [to][from]을 모두 채워줘야 한다.