[Algorithm] 백준 - 효율적인 해킹 (1325번)

문제

[백준] 효율적인 해킹
Contest > Internet Problem Solving Contest > IPSC 2008 B번

1325번: 효율적인 해킹

 

사용 알고리즘

- 그래프 탐색 | DFS (깊이 우선 탐색)

해결방법

• 컴퓨터간의 연결성을 인접리스트를 활용해 표현한다.
  • 문제 예제 1을 예시로 보면 다음과 같다
    [1] : 3
    [2] : 3
    [3] : 4 - 5
    [4] : 
    [5] :
• dfs 함수를 만들어 현재 컴퓨터에 연결된 다른 컴퓨터가 존재하고(==해킹가능한 컴퓨터) 그 컴퓨터를 아직 탐색하지 않은 경우 (visited가 0) dfs를 호출한다.
  • 호출 전, 해당 노드(컴퓨터)를 방문 예정이므로 visited를 1로 바꾸어준다.
  • com_num을 증가시켜줌으로서 해킹가능한 컴퓨터 수를 증가시킨다.
  • 결국 dfs를 통해 연결된(해킹가능한) 컴퓨터 수를 구해야 하므로 com_num을 return 한다
• 존재하는 전체 컴퓨터를 하나씩 dfs를 돌려서 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터를 res_com에 저장한다
  • dfs 결과값이 이전 최대 해킹컴수보다 큰 경우, res_com을 비우고 현재 컴퓨터만 저장한다
  • 이전 최대 해킹컴수와 같은 경우, res_com에 추가해준다

소스코드

사용언어 : c++

#include <iostream>
#include <vector>
#include <algorithm> // fill 사용

using namespace std;

int N, M;
vector<vector<int>> graph; // 인접 리스트 사용
int visited[10001]; // 방문한 컴터인지 체크

int dfs(int n, int com_num)
{
    for (int c : graph[n]) {
        if (!visited[c]) {
            visited[c] = 1;
            com_num = dfs(c, ++com_num);
        }
    }

    return com_num;
}

int main()
{
    cin >> N >> M;
    graph.resize(N+1);

    int from, to;
    for (int i=0; i<M; i++) {
        cin >> to >> from;
        graph[from].push_back(to);
    }

    int max_pc = 0; // 해킹 가능 최대 컴퓨터 수
    vector<int> res_com; // 컴터 번호 저장
    for (int i=1; i<=N; i++) {
        visited[i] = 1;
        int possible_com = dfs(i, 0);

        if (possible_com >= max_pc) {
            if (possible_com > max_pc) {
                max_pc = possible_com;
                res_com.clear();
            }
            res_com.push_back(i);
        } 
        fill(visited, visited+N+1, 0);  // visited 0으로 초기화
    }

    sort(res_com.begin(), res_com.end()); // 오름차순 정렬

    for (int v : res_com) {
        cout << v << " ";
    }

    return 0;
}

인접행렬 / 인접리스트

* 인접행렬

- graph[MAX_N][MAX_N] << 2차원 배열로 그래프를 표현하는 방식

- 두 정점 사이의 연결 여부를 상수 시간(O(1))에 확인할 수 있다. 

- But, 정점이 많고 간선이 적은 경우, 많은 공간을 차지할 수 있다

- 위 문제에선 인접행렬로 풀었더니 메모리 초과가 발생하였다.

 

* 인접리스트

- vector<vector<int>> graph;

- graph.resize(N);

- 각 정점마다 인접한 정점들의 리스트를 저장하는 방식 >> 정점의 차수에 비례하는 공간만 사용하므로 메모리를 절약할 수 있다

- But, 두 정점 사이의 연결 여부 확인에는 선형 시간(O(V))이 필요하다

 

한줄평

첨에 인접행렬로 풀어서 1차로 메모리 초과를 받고, 인접리스트로 바꿨는데 사이즈 재할당을 제대로 안해줘서 출력초과를 받았다.

두 부분을 모두 해결했더니 정답~

그래프 문제 코드 짤 때, 항상 다른 코드(남의 것 or 내가 예전에 짠 것)를 참고해서 짰더니, 막상 혼자 짜볼라니까 막막하더라. . 근데 위 코드는 혼자 생각해서 짰음 (뿌듯)