[백준 - 1325] 효율적인 해킹 .java

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

문제 분석

신뢰 관계 A ,B => A가 B를 신뢰한다

가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 = 신뢰를 가장 많이 받는 컴퓨터

즉, A라는 노드에서 방문하는 노드가 B, C이면 B, C는 A에게 신뢰받는 노드임

 

1. 모든 노드를 방문해야함
2. 노드를 방문할때 방문 배열을 초기화 하면서 탐색해야한다 -> 탐색 노드를 방문하면 해당 신뢰도 배열에 추가
3. 신뢰도 배열을 탐삭해 최댓값을 max로 저장
4. 이 max값을 가진 노드 번호(인덱스)를 오름차순으로 출력

최댓값을 가지는 노드가 여러개일 수 있기 때문에 max값으로 값만 찾고 이후 오름차순으로 다시 탐색하여 출력한다.

 

 

 

 

💡💡BFS

• 직접 예시를 풀어가면서 방문 배열의 초기화 여부를 알아야한다
• 탐색노드를 방문했을때 문제 조건에 맞춰서 답을 다른 배열에 저장하든가 방문배열을 갱신하는 등의 로직을 구성해야한다

 

첫번째 풀이 - 시간초과

실행했을 때 정답은 맞게 나왔지만 시간초과였다.

DFS로도 풀어 보았지만 시간 초과였다.

변수도 static으로도 해보고 많이 시도했지만 큰 틀은 아래 풀이와 다르지 않아 이 풀이만 작성하였다.

 

 

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

public class Main {
    static boolean[] visited;
    static int[] answer; //정답 배열
    static ArrayList<Integer>[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //띄어쓰기 입력
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        //초기화, 번호는 1부터 시작
        answer = new int[n+1];
        list = new ArrayList[n+1];
        for(int i = 1; i <= n; i++){
            list[i] = new ArrayList<>();
        }

        //에지 저장
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list[s].add(e);
        }
        //모든 노드에 대해 BFS 수행
        for(int i = 1; i <= n; i++){
            visited = new boolean[n+1];//방문배열 초기화
            BFS(i);
        }

        int max = Arrays.stream(answer).max().getAsInt();
        for (int i=1; i<n+1; i++) {
            if (max == answer[i]) {
                System.out.print(i+" ");}

        }
    }
    static void BFS(int com){
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(com);
        visited[com] = true;
        while(!q.isEmpty()){
            int now = q.poll();
            for(int i : list[now]){
                if(!visited[i]){
                    visited[i] = true;
                    answer[i]++;
                    q.add(i);
                }
            }
        }

    }

}

 

 

 

 

 

맞추기 위한 시도들..

 

두번째 풀이 - 정답

질문 게시판을 보니 함수로 BFS를 구현하지말고 직접 main함수에 넣어보라는 답변이 있어 그대로 했다.

결과는 성공..

 

이처럼 함수를 구현하는 자체가 시간에 큰 영향을 끼치는 문제였다.

이러한 문제를 처음 접하다보니 어떻게 고칠 수 있는지 감도 안와서 막막했었다.

여러 문제를 더 풀고 고민해야겠다.

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

public class Main {
    static int n, m;
    static boolean[] visited;
    static int[] answer; //정답 배열
    static ArrayList<Integer>[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //띄어쓰기 입력
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        //초기화, 번호는 1부터 시작
        answer = new int[n+1];
        list = new ArrayList[n+1];
        for(int i = 1; i <= n; i++){
            list[i] = new ArrayList<>();
        }

        //에지 저장
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            list[s].add(e);
        }
        //모든 노드에 대해 BFS 수행
        for(int i = 1; i <= n; i++){
            visited = new boolean[n+1];//방문배열 초기화
            Queue<Integer> q = new LinkedList<Integer>();
            q.add(i);
            visited[i] = true;
            while(!q.isEmpty()){
                int now = q.poll();
                for(int next : list[now]){
                    if(!visited[next]){
                        visited[next] = true;
                        answer[next]++;
                        q.add(next);
                    }
                }
            }
        }

        int max = Arrays.stream(answer).max().getAsInt();
        for (int i=1; i<n+1; i++) {
            if (max == answer[i]) {
                System.out.print(i+" ");}

        }
    }


}