[백준] 1325번 효율적인 해킹 - Java, 자바

난이도

실버 1

문제

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

풀이

문제 접근

• 이 문제는 DFS와 BFS로 풀 수 있는 그래프 탐색 문제로, 나는 BFS로 풀었다.
• 처음에 인접행렬을 활용해 문제를 풀었는데 메모리 초과가 나왔다.
  N은 10,000보다 작거나 같으므로 시간복잡도를 어림 잡아 계산했을 때 O(N*N = 10억정도)가 나와 이것을 줄여주려고 인접리스트(V+E)로 바꿔 풀었다.
• 시간초과가 나왔는데 곰곰히 생각해보니 방문한 노드를 또 방문하는 잘못된 로직을 짰다. visit 배열을 적용해 방문한 노드를 재방문하지 않도록 수정했다.
• 기본적인 BFS 문제와 동일하게 풀면 된다.

문제 풀이
result = 해킹한 컴퓨터수를 저장하는 배열
visit = 방문 여부 배열
list = 입력값 저장하는 인접리스트

1. 인접리스트를 먼저 초기화하고 입력값을 넣는다.

2. 각 노드마다 BFS를 수행하며 노드별 해킹 컴퓨터 수를 저장하고, max값을 찾는다.
   들어온 값을 큐에 넣고, 방문처리
   큐가 비어있지 않을 때
   큐에서 값을 하나 빼준다.
   그 값에 해당하는 리스트를 반복문 돌려준다.
   방문하지 않는 요소라면 방문처리, 큐에 요소 넣기, count++

3. max 값과 값이 동일한 노드를 출력한다.

코드

package 그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ1325 {
    static boolean[] visit;
    static int max = Integer.MIN_VALUE;
    static int n, m;
    static int count;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for(int i=0;i<=n;i++){
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            list.get(b).add(a);
        }
        int[] result = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            visit = new boolean[n + 1];
            count = 0;
            bfs(i);
            result[i] = count;
            max = Math.max(count, max);

        }
        for (int i = 1; i <= n; i++) {
            if (result[i] == max)
                sb.append(i+" ");
        }
        System.out.println(sb);

    }

    public static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        visit[x] = true;
        while (!q.isEmpty()) {
            int v = q.poll();
            for(int i : list.get(v)){
                if(!visit[i]){
                    q.add(i);
                    visit[i] = true;
                    count++;
                }
            }

        }
    }


}