[java] 문제 023 (백준 11724)

문제

연결 요소 개수

 

교재 풀이

import java.io.*;
import java.util.*;
public class P11724_연결요소의개수 {
  static ArrayList<Integer>[] A;
  static boolean visited[];
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    A = new ArrayList[n + 1];
    visited = new boolean[n + 1];
    for (int i = 1; i < n + 1; i++) { // 인접 리스트 초기화
      A[i] = new ArrayList<Integer>();
    }
    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int s = Integer.parseInt(st.nextToken());
      int e = Integer.parseInt(st.nextToken());
      A[s].add(e); // 양 방향 간선이므로 양쪽으로 간선을 더 해준다
      A[e].add(s);
    }
    int count = 0;
    for (int i = 1; i < n + 1; i++) {
      if (!visited[i]) { // 미 방문한 정점이 없을 때까지 반복
        count++;
        DFS(i);
      }
    }
    System.out.println(count);
  }
  static void DFS(int v) {
    if (visited[v]) {
      return;
    }
    visited[v] = true;
    for (int i : A[v]) {
      if (visited[i] == false) { // 연결 정점 중 방문하지 않았던 정점만 탐색함
        DFS(i);
      }
    }
  }
}

 

내 풀이) 6.12에 풀고 에러 뜬 틀린 풀이

import java.util.*;
import java.io.*;

public class Main
{
    static boolean[] visited;
    static ArrayList<Integer>[] a;
    static long ans=0;
    
	public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken()); // 정점 개수 
        int m=Integer.parseInt(st.nextToken()); // 간선 개수 
        
        visited=new boolean[n]; // 노드 개수만큼 
        a=new ArrayList[n];
        for(int i=0;i<n;i++){
            a[i]=new ArrayList<>();
        }
        
        for(int i=0;i<m;i++){
            st=new StringTokenizer(br.readLine()); // u, v 읽고 
            int u=Integer.parseInt(st.nextToken());
            int v=Integer.parseInt(st.nextToken());
            
            a[u].add(v);
            a[v].add(u);
        }
                    
        for(int i=0;i<n;i++){
            if(visited[i]==true){
                continue;
            }
            
            dfs(i);
            ans++;
        }
            
        System.out.println(ans);
	}
                        
	public static void dfs(int node){
	    if(visited[node]==true){
	        return;
	    }
	    
	    visited[node]=true;
	    
	    while(!a[node].isEmpty()){
	        int now=a[node].poll();
	        if(!visited[now]){
	            dfs(now);
	        }
	    }
	}
}

//방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하ㄱ
//		
//		첫째 줄에 정점의 개수 N과 간선의 개수 M
//		    (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
//		    m은 대략 오십만 
//	    둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.
//	        (1 ≤ u, v ≤ N, u ≠ v)
//	        같은 간선은 한 번만 주어진다.
//        
//        접근법 
//            입력 
//                6 5
//                1 2
//                2 5
//                5 1
//                3 4
//                4 6
//                    6이 n, 5가 m이고
//            출력 2
//            일단은 구현이 목적이기에 아이디어는 훔쳐서 보자면 
//            dfs가 한 번 완료될 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단할 수 있다
//            즉 dfs가 몇 번 실행됐는지로 알 수 있다
//                즉 각 노드에 대해 dfs를 수행하면,
//                시간복잡도는 노드 수+ 에지 수고, 그럼 1000+50만? 정도인데
//                각 dfs를 최대 1000번 실행하면 10의 3제곱 곱하기 10의 5제곱 곱하기 5니까 
//                시간 제한 3초를 넘기는데. 
//                이건 방문 배열로 한 건 넘기는 식으로 하면 줄어들지 않을까 
//        슈도코드 
//            n과 m을 입력받음
//                n은 정점 개수, m은 간선 개수 
//            
//            방문 배열 visited를 만들고 
//            인접 리스트 a를 만들기 
//                ArrayList<Integer>[] a=new ArrayList<>[n개];
//                인접리스트 a를 for문 n번 돌리면서 
//                new ArrayList<>()를 해줌 
//                
//            for n번 반복해서 
//                u, v: 간선의 양 끝점 
//                이를 입력한다. 
//                어디에? 인접 리스트에. 
//                    양방향 그래프므로 예로 1 3이 입력되면 
//                    a[1].add(3)을 a[3].add(1)를 해 줘야 함 
//            
//            ans 변수를 만들기 
//            for 돌려서 n번 반복함
//                각 노드 대해서 하기 전에 탐색하려는 노드가 visited 했다면
//                    continue;를 해줌
//                각 노드에 대해서 dfs를 수행해줌
//                
//                그럼 이 dfs가 몇 번 수행되었는지는 어떻게 알까
//                    dfs를 수행할 때 반복문에서 하는데 
//                    한 번 반복할 때마다 ans 변수를 +=해주는 거지 
//                
//            
//            dfs가 몇 번 실행되었는지 출력함 
//                ans 변수를 출력함 
//            
//            dfs 구현은 
//                인접 리스트, 방문 배열 가지고 하며 
//                만약 1을 인수로 받았어. 
//                그럼 1부터 시작하는 거지. 
//                
//                재귀로 구현하는 걸로 알고 있어 
//                먼저 받은 인수 노드와 연결된 다른 노드에 대해 
//                각각 dfs 수행해야 하지 않을까?
//                
//                해당 노드 now가 방문하지 않았다면 
//                    방문 배열 visited[now]를 체크하고 
//                    다시 now와 연결된 다른 노드에 대해 dfs를 수행해 
//                
//                다시 정리하면 
//                    먼저 조건을 체크해 
//                        지금 탐색하려는 노드가 방문했는지
//                        했으면 return해주는 거고 
//                    
//                    visited[node]를 체크해주고 
//                    while인가? 
//                        a[node]에서 연결된 노드 하나를 뽑아 
//                            뽑은 걸 now 변수에 저장해 
//                        그 노드가 아직 방문 안 했으면 
//                        dfs(now)를 실행해

 

설명

Main.java:51: error: cannot find symbol int now=a[node].poll();

또한 이 풀이 로직이 맞은 건지도 모름.

다시 풀어야지