그래프 최단거리 구하기 (BFS) - Java

 

1번에서 2번으로 간다고했을때 

1 -> 3 -> 4 -> 6 -> 2  // 4번 이동

1 -> 4 -> 6 -> 2 // 3번 이동

위 두 가지의 방법으로 2에 도달할 수 있다. 최소 이동 간선수는 3이 될 것이다.

입력:

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연 결정보가 주어진다.

해를 구하는 과정에서 인접행렬을 사용할 수 있지만 

출력:

1번 정점에서 각 정점으로 가는 최소 간선수를 2번 정점부터 차례대로 출력하세요.

 

풀이:

해를 구하는 과정에서 인접행렬을 사용할 수도 있지만 n이 커지면 2차원 배열 크기가 너무 커지기 때문에 메모리 낭비가 

있을 수 있어서 인접 리스트 방식으로 풀었다.

graph라는 이름의 리스트를 여러개를 사용해야 하기때문에 초기화 하는 코드부분에서 낯설었고 다음날 다시 풀어보려고 하니 

생각이 잘 나지 않았다.

static ArrayList<ArrayList <Integer>> graph = new ArrayList<ArrayList<Integer>>();

 

위와 같이 선언 및 초기화를 해줘야 하며,  만약 정점이 6개면 1~6 까지 리스트를 만들어줘야한다

for(int i=0;i<=6;i++){
	graph.add(new ArrayList<Integer>());
}

 

입력이 다 끝나면 루트 정점이 1 이기 때문에 

BFS(1); 을 메인에서 호출한다

ch[] : 방문한 노드 체크하는 배열

dis[] : 각 노드의 최소 이동 간선 수를 담는 배열

public void BFS(int v){
    //1에서 각 정점으로 가는 최소 간선 수를 구해라
    ch[v]=1;// 방문한걸로 처리
    dis[v]=0; // 거리 초기화
    //BFS이기 때문에 큐를 사용
    Queue<Integer>Q = new LinkedList<>();
    Q.offer(v);
    while (!Q.isEmpty()){
        int cv = Q.poll();
        for(int nv : graph.get(cv)){
            if(ch[nv]==0){
                ch[nv]=1;
                Q.offer(nv);
                dis[nv]= dis[cv]+1; //핵심
            }
        }
    }
}

 

위 코드에서

dis[nv]= dis[cv]+1;  

이 코드가 핵심인거 같다. 결국 노드가 이어져있기 때문에

1 -> 4 -> 6 노드로 이동한다고 했을때

1 -> 4 는 1만큼 이동되고 4 - > 6 이 이어져있기 때문에 1 -> 4 -> 6 으로 이동하는데에도

아래와 같이 이해하면 되는것이다.

1 -> 4 -> 6 의 이동거리 = 1 (1->4) + 1

 

 

 

 

 

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 김태원