[문제풀이] 07-13. 그래프 최단 거리(BFS)

인프런, 자바(Java) 알고리즘 문제풀이

Recursive, Tree, Graph - 0713. 그래프 최단 거리(BFS)

🗒️ 문제

🎈 나의 풀이

	private static int[] solution(List<ArrayList<Integer>> graph) {
        int[] answer = new int[graph.size()];
        int[] ch = new int[graph.size()];
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(1);

        int level = 0;

        while(!Q.isEmpty()) {
            int len = Q.size();

            for(int i=0; i<len; i++) {
                int v = Q.poll();
                if(ch[v] == 0) {
                    answer[v] = level;
                    ch[v] = 1;
                    for(int nv : graph.get(v)) Q.add(nv);
                }
            }
            level++;
        }

        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<ArrayList<Integer>> graph = new ArrayList<>();

        for(int i=0; i<=n; i++) graph.add(new ArrayList<>());

        for(int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }

        int[] answer = solution(graph);

        for(int i=2; i<answer.length; i++) System.out.println(i + ":" + answer[i]);
    }

🖍️ 강의 풀이

  	static int n, m, answer=0;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] ch, dis;
	public void BFS(int v){
		ch[v]=1;
		dis[v]=0;
		Queue<Integer> queue=new LinkedList<>();
		queue.offer(v);
		while(!queue.isEmpty()){
			int cv=queue.poll();
			for(int nv : graph.get(cv)){
				if(ch[nv]==0){
					ch[nv]=1;
					queue.offer(nv);
					dis[nv]=dis[cv]+1;
				}
			}
		}
	}
	
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n=kb.nextInt();
		m=kb.nextInt();
		graph=new ArrayList<ArrayList<Integer>>();
		for(int i=0; i<=n; i++){
			graph.add(new ArrayList<Integer>());
		}
		ch=new int[n+1];
		dis=new int[n+1];
		for(int i=0; i<m; i++){
			int a=kb.nextInt();
			int b=kb.nextInt();
			graph.get(a).add(b);
		}
		T.BFS(1);
		for(int i=2; i<=n; i++){
			System.out.println(i+" : "+dis[i]);
		}
	}	

💬 짚어가기

해당 문제는 BFS를 이용하여 풀 수 있다. 나의 풀이에서는 너비 우선 탐색을 수행하며,
정점까지의 최단 거리를 보관할 수 있는 int배열을 하나 생성하였다. 해당 배열의 인덱스가
정점의 번호이고, 배열에 담길 자료가 최단 거리이다.

다음 해당 정점을 방문 여부를 판별할 수 있는 배열을 생성했다. 최단 거리를 보관하는 배열과
마찬가지로 이용한다. (지금 보니 두 배열을 하나로 사용해도 될 것 같다.)

BFS를 수행하며, 정점이 등장하는 순간 탐색 Level을 배열에 보관하여 문제를 해결한다.

강의에서는 동일한 로직으로 방문 여부와 최단 거리를 보관하는 배열을 두고 BFS를 수행한다.
단, 최단 거리를 현재 정점까지의 거리에 1을 더하여 보관하는 방식으로 문제를 해결하였다.