[90] 코딩테스트: 부대복귀 자바 풀이 | Graph + visited 배열

코딩테스트 준비 90일차

 

오늘 풀 문제는 부대복귀이다.

 

그래프로 우선 값을 저장하고,

BFS로 길이를 탐색했다.

 

제일 마지막에 참고하면 좋을 풀이도 함께 작성해두었다.

 

▼ 내일 풀 문제 ▼

현재 고민중..

https://school.programmers.co.kr/learn/courses/30/lessons/42627

프로그래머스

 

 

부대복귀

• Graph, BFS

출처: 프로그래머스 부대복귀 자바 풀이 그래프

 

프로그래머스

 

실패

 

• BFS 도중 목적지를 찾았을 때 루프를 제대로 종료하지 않음
  • if(i==end)에서 answer[idx] = len+1; 하고 그냥 continue 처리
    • 최단 거리라고 보장할 수 없음
• 목적지를 찾지 못한 경우 처리 없음
  • 목적지를 찾지 못한 경우는 answer[idx] = -1 처리
    • list[s].size() == 0일 때만 실행
  • 노드가 연결은 돼 있지만, 목적지로 가는 경로가 없을 때 -1 처리를 하지 못함!!

private void check(int str, int end, int idx) {
    Queue<int[]> q = new LinkedList<>();
    visited[str] = true;
    q.add(new int[]{str, 0});

    while(!q.isEmpty()) {
        int[] a = q.poll();
        int s = a[0];
        int len = a[1];

        if(list[s].size() == 0) { //해당 조건은 while문 밖으로..
            answer[idx] = -1;
            break;
        }

        for(int i : list[s]) {
            if(!visited[i]) {
                if(i==end) { //for문 들어오기 전 예외 처리로..
                    answer[idx] = len+1;
                    break;
                } else {
                    visited[i] = true;
                    q.add(new int[]{i, len+1});
                }
            }
        }
    }
}

 

수정 코드 → 시간 초과

private void check(int str, int end, int idx) {
    Queue<int[]> q = new LinkedList<>();
    visited[str] = true;
    q.add(new int[]{str, 0});

    while(!q.isEmpty()) {
        int[] a = q.poll();
        int s = a[0];
        int len = a[1];

        if(s == end) {
            answer[idx] = len;
            return;
        }

        for(int i : list[s]) {
            if(!visited[i]) {
                visited[i] = true;
                q.add(new int[]{i, len+1});
            }
        }
    }

    answer[idx] = -1;
}

 

정답 코드

• visited 배열을 방문 처리 + 길이 2가지 저장으로 사용
  • 단순히 boolean으로 선언한다는 생각은.. 접어두기..

import java.util.*;

class Solution {
    ArrayList<Integer>[] list;

    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        int[] answer = new int[sources.length];

        list = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        for(int[] road : roads) {
            list[road[0]].add(road[1]);
            list[road[1]].add(road[0]);
        }

        // destination 기준으로 모든 노드까지의 거리 계산
        int[] distance = new int[n+1];
        Arrays.fill(distance, -1); // -1은 도달할 수 없음을 의미
        bfs(destination, distance);

        // 각 source에 대해 거리 기록
        for(int i = 0; i < sources.length; i++) {
            answer[i] = distance[sources[i]];
        }

        return answer;
    }

    private void bfs(int start, int[] distance) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        distance[start] = 0;

        while(!queue.isEmpty()) {
            int now = queue.poll();

            for(int next : list[now]) {
                if(distance[next] == -1) {
                    distance[next] = distance[now] + 1;
                    queue.add(next);
                }
            }
        }
    }
}