[HackerRank]Journey to the Moon

HackerRank-Journey to the Moon

• 그래프 문제
• int의 범위가 아래와 같으므로 값을 long으로 반환해야 함
• visited를 queue에 넣을 때 체크를 해야 중복이 발생하지 않는다
• 누적합을 구할 때 (i) * (i + 1 ~ n) 의 합으로 구할 경우 메모리 이슈가 발생할 수 있으므로 다른 방식이 필요함

문제 풀이

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {
    
    
    public static long journeyToMoon(int n, List<List<Integer>> astronaut) {
    // Write your code here
        long answer = 0;
    
        List<List<Integer>> graph = new ArrayList<>();
        for(int i = 0; i < n; i ++) {
            graph.add(new ArrayList());
        }
    
        for(List<Integer> pair : astronaut) {
            int n1 = pair.get(0);
            int n2 = pair.get(1);
            
            graph.get(n1).add(n2);
            graph.get(n2).add(n1);
        }
        
        boolean[] visited = new boolean[n];
        List<Integer> graphCounts = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            if (visited[i] == false) {
                int count = bfs(visited, graph, i);
                graphCounts.add(count);
            }
        }

        long total = 0;
        for (int graphCount : graphCounts) {
            
            answer += graphCount * total;
            total += graphCount; 
        }
        
        return answer;
        
        
    }
    
    public static int bfs(boolean[] visited, List<List<Integer>> graph, int startNode) {
        
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode);
        visited[startNode] = true;
        
        while(!queue.isEmpty()) {
            int currentNode = queue.poll();
     
            count += 1; 
            List<Integer> nextNodes = graph.get(currentNode);
            for (Integer nextNode: nextNodes) {
                if (!visited[nextNode]) {
                    queue.add(nextNode);
                    visited[nextNode] = true;
                }
            }
        }
        
        return count;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int p = Integer.parseInt(firstMultipleInput[1]);

        List<List<Integer>> astronaut = new ArrayList<>();

        IntStream.range(0, p).forEach(i -> {
            try {
                astronaut.add(
                    Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
                        .map(Integer::parseInt)
                        .collect(toList())
                );
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        long result = Result.journeyToMoon(n, astronaut);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

테스트 케이스

case 1 
5 3
0 1
2 3
0 4
6

case 2 
100000 2
1 2
3 4
4999949998