[1325] 효율적인 해킹

✔ 효율적인 해킹

[백준 1325]

문제 분석하기

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

BFS 탐색을 수행해 신뢰도가 가장 높은 컴퓨터를 출력

손으로 풀어보기

1. 인접 리스트로 컴퓨터와 신뢰 관계 데이터의 그래프를 표현
2. 모든 노드로 각각 BFS 탐색 알고리즘을 적용해 탐색을 수행
   탐색을 수행하면서 탐색되는 노드들의 신뢰도를 증가시켜 줌
3. 탐색 종료 후 신뢰도 배열을 탐색해 신뢰도의 최댓값은 Max 값으로 지정하고,
   신뢰도 배열을 다시 탐색하면서 Max 값을 지니고 있는 노드를 오름차순 출력

슈도코드 작성하기

N(노드 개수) M(엣지 개수)
answer(정답 배열)
A(그래프 데이터 저장 인접 리스트) visited(방문 유무 저장 배열)
for(N의 개수만큼 반복하기) {
    A 인접 리스트의 각 ArrayList 초기화하기
}
for(M의 개수만큼 반복하기) {
    A 인접 리스트에 그래프 데이터 저장하기
}
for(i -> N의 개수만큼 반복하기) {
    visited 배열 초기화하기
    BFS(i) 실행하기
}
for(N의 개수만큼 반복하기) {
    answer 배열에서 가장 큰 수 찾기 -> maxVal
}
for(N의 개수만큼 반복하기) {
    answer 배열에서 maxVal와 같은 값을 가진 index를 정답으로 출력하기
}

BFS {
    큐 자료구조에 출발 노드 더하기(add 연산)
    visited 배열에 현재 노드 방문 기록하기
    while(큐가 빌 때까지) {
        큐에서 노드 데이터를 가져오기(poll 연산)
        현재 노드의 연결 노드 중 방문하지 않은 노드로
        큐에 데이터 삽입(add 연산)하고 visited 배열에 방문 기록하기
        신규 노드 인덱스의 정답 배열 값을 증가시키기
    }
}

코드 구현하기

/**
 * 1325) 효율적인_해킹
 */
public class D047_1325 {
    static int N, M;
    static boolean visited[];
    static int answer[];
    static ArrayList<Integer> A[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // N(노드 개수)
        N = Integer.parseInt(st.nextToken());
        // M(엣지 개수)
        M = Integer.parseInt(st.nextToken());
        // A(그래프 데이터 저장 인접 리스트)
        A = new ArrayList[N + 1];
        // answer(정답 배열)
        answer = new int[N + 1];
        // A 인접 리스트의 각 ArrayList 초기화하기
        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<>();
        }
        // A 인접 리스트에 그래프 데이터 저장하기
        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);
        }
        for (int i = 1; i <= N; i++) {
            // visited(방문 유무 저장 배열) 초기화하기
            visited = new boolean[N + 1];
            // BFS(i) 실행하기
            BFS(i);
        }
        // answer 배열에서 가장 큰 수 찾기
        int maxVal = 0;
        for (int i = 1; i <= N; i++) {
            maxVal = Math.max(maxVal, answer[i]);
        }
        // answer 배열에서 maxVal와 같은 값을 가진 index를 정답으로 출력하기
        for (int i = 1; i <= N; i++) {
            if (answer[i] == maxVal) {
                System.out.print(i + " ");
            }
        }
    }

    // BFS 구현하기
    public static void BFS(int index) {
        // 큐 자료구조에 출발 노드 더하기
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(index);
        // visited 배열에 현재 노드 방문 기록하기
        visited[index] = true;
        while (!queue.isEmpty()) {
            // 큐에서 노드 데이터를 가져오기
            int now = queue.poll();
            // 현재 노드의 연결 노드 중 방문하지 않은 노드로
            for (int i : A[now]) {
                if (visited[i] == false) {
                    // visited 배열에 방문 기록하기
                    visited[i] = true;
                    // 신규 노드 인덱스의 정답 배열 값을 증가시키기
                    answer[i]++;
                    // 큐에 데이터 삽입
                    queue.add(i);
                }
            }
        }
    }
}