[Baekjoon(백준)][1325번] 효율적인 해킹(C++)

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "효율적인 해킹" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제에서는 컴퓨터의 신뢰 관계를 바탕으로 한 번의 해킹으로 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 찾는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

1325번: 효율적인 해킹

문제 개요

"효율적인 해킹" 문제는 컴퓨터의 신뢰 관계를 바탕으로 한 번의 해킹으로 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 찾는 문제입니다.

문제 해결

이 문제를 해결하기 위해서는 각 컴퓨터가 다른 컴퓨터를 해킹할 때 해킹할 수 있는 컴퓨터의 총 수를 구한 뒤, 가장 많이 해킹할 수 있는 컴퓨터의 번호를 찾아야 합니다. 이를 위해 깊이 우선 탐색(DFS) 알고리즘을 사용하여 각 컴퓨터를 시작점으로 해킹할 수 있는 컴퓨터의 수를 계산합니다.

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m; // n: 컴퓨터의 개수, m: 신뢰 관계의 개수
vector<int> tables[100002]; // 각 컴퓨터가 해킹할 수 있는 컴퓨터의 목록
bool visit[10002]; // 방문한 컴퓨터를 체크하는 배열

// 깊이 우선 탐색 함수, start: 현재 탐색하는 컴퓨터의 번호
int dfs(int start) {
    visit[start] = true; // 현재 컴퓨터를 방문했다고 체크
    int ret = 1; // 현재 컴퓨터도 해킹할 수 있으므로 1부터 시작
    for (int i = 0; i < tables[start].size(); i++) { // 현재 컴퓨터가 해킹할 수 있는 모든 컴퓨터에 대해
        if (visit[tables[start][i]]) continue; // 이미 방문한 컴퓨터는 스킵
        ret += dfs(tables[start][i]); // 재귀적으로 탐색
    }
    return ret; // 해킹할 수 있는 컴퓨터의 총 수 반환
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int temp1, temp2;
        cin >> temp1 >> temp2; // temp2 컴퓨터를 해킹하면 temp1도 해킹할 수 있음
        tables[temp2].push_back(temp1); // 신뢰 관계 설정
    }

    int maxvalue = 0; // 가장 많이 해킹할 수 있는 컴퓨터의 해킹 수
    int ret[10002]; // 각 컴퓨터가 해킹할 수 있는 컴퓨터의 수를 저장하는 배열
    for (int i = 1; i <= n; i++) {
        fill(&visit[0], &visit[0] + 10002, false); // 방문 배열 초기화
        int temp = dfs(i); // i번 컴퓨터부터 시작하는 DFS 결과
        ret[i] = temp; // 결과 저장
        maxvalue = max(temp, maxvalue); // 최대 해킹 수 업데이트
    }

    for (int i = 1; i <= n; i++) {
        if (ret[i] == maxvalue) cout << i << " "; // 가장 많이 해킹할 수 있는 컴퓨터 출력
    }
    return 0;
}

코드 설명

위 코드는 각 컴퓨터가 다른 컴퓨터를 해킹할 수 있는 관계를 tables 배열에 저장하고, 각 컴퓨터를 시작점으로 하는 깊이 우선 탐색을 통해 해당 컴퓨터가 해킹할 수 있는 컴퓨터의 총 수를 계산합니다. 최종적으로 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력합니다.

결론

이 문제의 핵심은 각 컴퓨터를 시작점으로 하는 깊이 우선 탐색을 통해 해킹할 수 있는 컴퓨터의 수를 계산하는 것입니다. 모든 컴퓨터에 대해 이 작업을 수행한 후, 가장 많이 해킹할 수 있는 컴퓨터를 찾아 출력합니다.