글 읽기 - 리스트로 저장되어 있는 노드들을 통해서 BFS로 돌려 값을 구하려고 하는데요

leeyh2006 5년 전 0

해당 노드들을 기억 하는 리스트를 만들긴 했는데 ... (배열로 안하고 리스트로 한번 해보려고 합니다)

여기서 어떤 방식으로 촌수를 계산해야 할지 방법이 잘 안떠오르네요 ㅠ

혹시 팁좀 주실 분 있나요 ?

import java.util.*;

public class Ex2644 {

    public static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         n = sc.nextInt();
        List<Integer>[] list = (ArrayList<Integer>[]) new ArrayList[n+1];
        boolean visit[] = new boolean[n+1];
        for (int i = 1; i<=n; i++)
            list[i] = new ArrayList<>();

        int nx = sc.nextInt(), ny=sc.nextInt();

        int link = sc.nextInt();
        for (int i = 0; i <link; i++){
            int v1 =sc.nextInt();
            int v2 =sc.nextInt();

            list[v1].add(v2); // 촌수들이 연결되어 있는 관계 지정
        }


        Arrays.stream(list).forEach(i-> System.out.println(i));
     /**
       0 null
       1 [2, 3]
       2 [7, 8, 9]
       3 []
       4 [5, 6]
       5 []
       6 []
       7 []
       8 []
       9 []
      **/
    
        System.out.println("count" + bfs(list,visit,1,ny));
    }

    public static int bfs(List<Integer>[] a, boolean[] c,int v, int ny )
    {
        Queue<Integer> q = new LinkedList<>();

        q.add(v);
        c[v] = true;
        int count =0;

        
        // 예제로 7과 3의 최단거리를 구하려고 하는데요 ..
        while (!q.isEmpty()){
            v=q.poll();
            for(int vv: a[v]){
                q.add(vv);
                c[vv]=true;
                count++;
            }
        }
        return count;

    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

리스트로 저장되어 있는 노드들을 통해서 BFS로 돌려 값을 구하려고 하는데요

leeyh2006 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말