<Algorithm> 74. 5567번 결혼식

1. 5567번 결혼식

• 처음 접근을 find로 했는데 문제는 들어올때마다 부모 노드가 바뀔 수 있다는 것을 간과 했던것 같다

• BFS로 처리하고 싸이클이 발생할 경우 무한루프가 발생하는 부분만 처리했다.

public class Main {
    static int count = 0;
/*
 * 4-10 7-10 3-7 6-8 1-7 1-6 1-5 1-9 2-4 3-8
 *  7 6 5 9 
 *  3 8 10  
 */
    static ArrayList<Node>[] aLists;
    static Queue<Integer> queue = new LinkedList<>();
    static boolean[] visited;
public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()) + 1;
        int M = Integer.parseInt(br.readLine());
        aLists = new ArrayList[N];
        visited = new boolean[N];
        for(int i = 1; i < N; i++) {
            aLists[i] = new ArrayList<>();
        }
        
        
        for(int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            aLists[x].add(new Node(y));
            aLists[y].add(new Node(x));
            if(x==1) {
                queue.add(y);
                visited[y] = true;
                count++;
            }
            if(y==1) {
                queue.add(x);
                visited[x] = true;
                count++;
            }
        }
        visited[1]=true;
        // 최초 시작 양방향이기 때문에 시작은 체크 아니면 오버플로우발생
         bfs();
        System.out.println(count);
    }
    public static void bfs() {
        
        while (!queue.isEmpty()) {
            int x = queue.remove();        
            visited[x] = true;
            for(Node no : aLists[x]) {
                if(!visited[no.adj]) {
                    count++;
                    visited[no.adj] = true;
                    // 친구의 친구까지 
                }
            }
        }
    }
 
}
class Node{
    int adj;
 
    public Node(int adj) {
        super();
        this.adj = adj;
    }
    
}

참고 & 출처