백준 5567 - 결혼식(그래프) 자바 JAVA

https://www.acmicpc.net/problem/5567

5567번: 결혼식

 

문제분석

이 문제는 간단하게 말하면 상근이의 친구와 친구의 친구 수를 세면 되는 문제이다.

따라서 상근이로부터 최단거리가 2 이하인 친구의 개수를 구하면 되기 때문에 BFS를 사용해서 최단거리를 구하는 문제라고 볼  수 있다.

 

BFS란

https://3eeunn.tistory.com/21

BFS - 자바(JAVA)

 

풀이

1. 인접 리스트로 상근이 동기들의 친구관계 리스트를 구현한다.

2. BFS로 탐색하면서 각 친구들까지의 최단거리를 방문 배열에 저장한다. 

3. 방문 배열에 값이 2 이하인 친구들의 수를 출력한다.

 

 

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P6657_결혼식 {
    static int[] visted;   //방문 배열
    static ArrayList<Integer>[] A;
    static int n;  //동기 수
    static int m;  //리스트 길이
    static int result;  //출력값

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        n = scan.nextInt();
        m = scan.nextInt();
        A = new ArrayList[n+1];

        for(int i = 1; i <= n; i++){    //리스트 초기화
            A[i] = new ArrayList<>();
        }

        for(int i = 0; i < m; i++){     //리스트에 데이터 저장
            int S = scan.nextInt();
            int E = scan.nextInt();
            A[S].add(E);
            A[E].add(S);
        }

        visted = new int[n+1];
        for(int i = 1; i <= n; i++){    //방문 배열 초기화
            visted[i] = -1;
        }

        BFS(1);

        for(int i = 2; i <= n; i++){   
            System.out.println(visted[i]);
            if(visted[i] <= 2 && visted[i] > -1){
                result++;
            }
        }

        System.out.println(result);
    }

    private static void BFS(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visted[node]++;
        while(!queue.isEmpty()) {
            int now_node = queue.poll();
            for(int i : A[now_node]){
                if(visted[i] == -1) {
                    queue.add(i);
                    visted[i] = visted[now_node]+1;
                }
            }
        }
    }
}

 

 

주의할 점

리스트에 데이터를 저장할 때 양방향으로 저장해야 한다. 

친구 관계 ai bi는  ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이기 때문이다.

이거에 관한 입력 예시는

3

2

2 1

3 1

이다.

 

한방향으로만 입력하면 (1)처럼 그래프가 그려져서 1의 친구는 0이라고 나온다.

양방향으로 입력해야 (2)처럼 그래프가 그려져서 출력값이 2로 잘 나오게 된다.