[백준] 1325 효율적인 해킹

March 23, 2021 ( last updated : March 24, 2021 )
dfs 그래프 탐색 알고리즘 algorithm

https://github.com/sneakstarberry/

Abstract

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

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

백준 1325번

알고리즘 유형

문제 이해

풀이방법

dfs로 돌면서 해킹가능한 컴퓨터의 숫자를 카운팅하고 최대 수인지 확인한다. 해킹한 컴퓨터의 숫자가 최대이면 vector에 넣고 아니면 그냥 넘어간다.

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

#define MAX 10011

using namespace std;

int N, M, CNT;
vector<int> MOST_HACK_COMPUTER, computer_hack[MAX];
int is_visited[MAX];

void dfs(int current_computer);

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

  int max = -1;
  cin >> N >> M;
  int tmp[2];
  for (int i = 0; i < M; i++) {
    cin >> tmp[0] >> tmp[1];
    computer_hack[tmp[1]].push_back(tmp[0]);
  }

  for (int i = 1; i <= N; i++) {
    memset(is_visited, 0, sizeof(is_visited));
    CNT = 0;
    dfs(i);
    if (max < CNT) {
      max = CNT;
      MOST_HACK_COMPUTER.clear();
      MOST_HACK_COMPUTER.push_back(i);
    } else if (max == CNT) {
      MOST_HACK_COMPUTER.push_back(i);
    }
  }

  for (int i = 0; i < MOST_HACK_COMPUTER.size(); i++) {
    cout << MOST_HACK_COMPUTER[i] << ' ';
  }
  return 0;
}

void dfs(int current_computer) {
  is_visited[current_computer] = 1;
  CNT++;
  for (int i = 0; i < computer_hack[current_computer].size(); i++) {
    int next_computer = computer_hack[current_computer][i];
    if (!is_visited[next_computer]) {
      dfs(next_computer);
    }
  }
}

Originally published March 23, 2021
Latest update March 24, 2021

Related posts :

{# #}