[알고리즘 / 백준] 1325 - 효율적인 해킹

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

문제는 위와 같으며, 모든 컴퓨터를 확인하며 연결된 컴퓨터 개수의 최대 값을 구하면 해결할 수 있습니다. 이때 dfs 보다는 좀 더 효율적이라고 하는 bfs 사용하여 문제를 해결하였습니다.

 

파이썬 코드는 다음과 같습니다. 이 문제의 경우 Pypy3 로 제출하여야 통과할 수 있습니다.

from sys import stdin
from collections import deque


def bfs(v):
    q = deque([v])
    visited = [False] * (n + 1)  # 이미 이전에 방문한 노드인지 확인
    visited[v] = True
    count = 1
    while q:
        v = q.popleft()  # 큐의 앞에서부터 노드를 꺼내서
        for e in adj[v]:  # 해당 노드와 연결된 노드를 순서대로 확인
            if not visited[e]:  # 연결된 노드를 아직 방문하지 않은 경우
                q.append(e)  # 큐에 추가 후
                visited[e] = True  # 방문한 것으로 처리
                count += 1  # 방문한 노드 수 + 1

    return count  # 주어진 노드와 연결된 노드 개수 반환


n, m = map(int, stdin.readline().split())
adj = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, stdin.readline().split())
    adj[b].append(a)  # 컴퓨터 번호의 인덱스에 연결된 컴퓨터 번호를 리스트로 저장

result = []
max_value = -1

for i in range(1, n + 1):  # 모든 컴퓨터 번호 확인
    c = bfs(i)  # 연결된 컴퓨터 수 확인
    if c > max_value:  # 현재 연결된 컴퓨터 수가 기존 최대 연결 컴퓨터 수보다 큰 경우
        max_value = c  # 현재 연결된 컴퓨터 수로 최대값 수정
        result = [i]  # 해당 컴퓨터 번호도 수정
    elif c == max_value:  # 현재 연결된 컴퓨터 수가 기존 최대 연결 컴퓨터 수와 같은 경우
        result.append(i)  # 해당 컴퓨터 번호 추가

for r in result:
    print(r, end=" ")

 

자바 코드는 다음과 같습니다. 파이썬과 같은 로직이지만, 시간 초과 문제를 해결하지 못하였습니다... ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static List<ArrayList<Integer>> adj = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int[] nm = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        for (int i = 0; i < nm[0] + 1; i++) {
            adj.add(i, new ArrayList<>());
        }

        for (int i = 0; i < nm[1]; i++) {
            int[] ab = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            adj.get(ab[1]).add(ab[0]);
        }

        ArrayList<Integer> result = new ArrayList<>();
        int max_value = -1;

        for (int i = 1; i < adj.size(); i++) {
            int c = bfs(i);
            if (c > max_value) {
                result.clear();
                result.add(i);
                max_value = c;
            } else if (c == max_value) {
                result.add(i);
            }
        }

        for (int r : result) {
            sb.append(r).append(" ");
        }

        System.out.println(sb);
    }

    private static int bfs(int v) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(v);

        boolean[] visited = new boolean[adj.size() + 1];
        int count = 1;

        while (!deque.isEmpty()) {
            int n = deque.pollFirst();
            for (int e : adj.get(n)) {
                if (!visited[e]) {
                    deque.add(e);
                    visited[e] = true;
                    count += 1;
                }
            }
        }

        return count;
    }
}

 

추후에 더 나은 방법으로 해결하게 되면 수정하겠습니다!