백준 11724 - 연결요소의개수, 너비우선, 깊이우선, 프로그래머스, 알고리즘, Programmers, Stack, Queue, Hash, 코딩테스트, Algorithm, 풀이과정, Leetcode, 릿코드, 코딩테스트, Tech interview, search, greedy, baekjoo..

 

 금방 풀고 계속 시간초과가 나서 왜지왜지 하면서 이렇게 저렇게 계속 풀었는데..

Vertex 내에서 adjacents를 LinkedList로 해서 그랬던 거였고.. ArrayList로 해야 했던 것 같다.

인덱스 접근이 있어도 고작 1000개 노드라서 일반적으로 쓰는 연결리스트 쓴건데 이게 그렇게 차이가 있나 싶었지만

뭐 암튼.. 여러번 풀면서 bfs dfs 번갈아서 여러번 연습해서 나쁘지 않았다..

 

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

class Main {
    private static List<Vertex1> vertexes = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        int count = 0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] line = br.readLine().split(" ");
        int countVertex = Integer.parseInt(line[0]);
        int countEdge = Integer.parseInt(line[1]);
        
        for (int i = 0; i < countVertex; ++i) {
            vertexes.add(new Vertex1());
        }
        for (int i = 0; i < countEdge; ++i) {
            line = br.readLine().split(" ");
            int start = Integer.parseInt(line[0])-1;
            int end = Integer.parseInt(line[1])-1;
            vertexes.get(start).addAdjacent(vertexes.get(end));
        }
        
        for (int i = 0; i < vertexes.size(); ++i) {
            if (!vertexes.get(i).isVisited) {
                ++count;
                bfs(vertexes.get(i));
            }
        }

        System.out.println(count);
    }

    public static void bfs(Vertex1 root) {
        Queue<Vertex1> queue = new LinkedList<>();
        queue.add(root);
        root.isVisited = true;
        while(queue.size() > 0) {
            Vertex1 tempVertex = queue.poll();
            for (int j = 0; j < tempVertex.adjacents.size(); ++j) {
                if (!tempVertex.adjacents.get(j).isVisited) {
                    queue.add(tempVertex.adjacents.get(j));
                    tempVertex.adjacents.get(j).isVisited = true;
                }
            }
        }
    }
}

class Vertex1 {
    int value = 0;
    List<Vertex1> adjacents = new ArrayList<>();
    boolean isVisited = false;

    public void addAdjacent(Vertex1 vertex) {
        if (!adjacents.contains(vertex)) {
            adjacents.add(vertex);
            vertex.adjacents.add(this);
        }
    }
}

 

아.. 다시보니까 연결리스트 쓰려면 adjacents를 한번만 접근해서 미리 빼놓고

다시 여러번 접근하지 않도록 했어도 됐을랑가 싶음