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

1. 문제

1325번: 효율적인 해킹

2. 개요

N개의 컴퓨터가 있다.

컴퓨터들은 신뢰하는 관계와 신뢰하지 않는 관계가 있는데, A가 B를 신뢰하는 경우 B가 해킹되면 A도 해킹을 당하게 된다.

컴퓨터들 간의 신뢰관계가 주어졌을 때, 어떤 컴퓨터를 해킹하여 가장 많은 컴퓨터를 해킹할 수 있는 지를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

컴퓨터간의 신뢰관계를 그래프로 만들어둔 후, 컴퓨터 하나하나마다 BFS를 행하여 접근 가능한 컴퓨터의 총 대수를 구해나가면 답을 찾을 수 있다.

3-2. Python

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

graph = [[] for i in range(N + 1)]

for i in range(M):
    A, B = map(int, sys.stdin.readline().split())

    graph[B].append(A)

def BFS(num):
    cnt = 0
    visited = [False for i in range(N + 1)]
    q = deque([num])
    visited[num] = True

    while q:
        now = q.popleft()

        for nxt in graph[now]:
            if visited[nxt] == True:
                continue

            visited[nxt] = True
            cnt += 1
            q.append(nxt)

    return cnt

maxValue = 0
answer = [[] for i in range(N + 1)]

for i in range(1, N+1):
    tmp = BFS(i)
    answer[tmp].append(i)

    if tmp > maxValue:
        maxValue = tmp

print(*answer[maxValue])

3-3. C#

namespace boj_1325
{
    internal class Program
    {
        static List<int>[] graph;
        static int N;
        static int M;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();

            N = int.Parse(input[0]);
            M = int.Parse(input[1]);

            graph = new List<int>[N + 1];

            for (int i = 0; i < N + 1; i++)
                graph[i] = new();

            for (int i = 0; i < M; i++)
            {
                input = sr.ReadLine().Split();

                int A = int.Parse(input[0]), B = int.Parse(input[1]);

                graph[B].Add(A);
            }

            int maxValue = 0;
            List<int> answer = new();

            for (int i = 1; i < N + 1; i++)
            {
                int tmp = BFS(i);

                if (tmp > maxValue)
                {
                    answer.Clear();
                    maxValue = tmp;
                    answer.Add(i);
                }

                else if (tmp == maxValue)
                    answer.Add(i);
            }

            foreach (int ans in answer)
                sw.Write($"{ans} ");

            sw.Close();
        }

        static int BFS (int num)
        {
            int cnt = 0;
            bool[] visited = new bool[N + 1];
            Queue<int> q = new Queue<int>();
            q.Enqueue(num);
            visited[num] = true;

            while (q.Count > 0)
            {
                int now = q.Dequeue();

                foreach (int nxt in graph[now])
                {
                    if (visited[nxt])
                        continue;

                    visited[nxt] = true;
                    cnt++;
                    q.Enqueue(nxt);
                }
            }

            return cnt;
        }
    }
}