백준 1325 효율적인 해킹 C++/PyPy

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

1325번: 효율적인 해킹

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1325_bfs.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ1325_bfs
//
//  Created by Hwayeon on 2021/08/18.
//

#include <iostream>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

int N, M;
int counts[10001] = {0, };
int visit[10001] = {0, };
vector<int> graph[10001];
int max_cnt = 0;

void bfs(int s){
    queue<int> q;
    q.push(s);
    visit[s] = 1;
    counts[s]++;
    while(!q.empty()){
        int nv = q.front();
        q.pop();
        for(int i=0; i<graph[nv].size(); i++){
            if(!visit[graph[nv][i]]){
                counts[s]++;
                visit[graph[nv][i]] = 1;
                q.push(graph[nv][i]);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int v1, v2;
        cin >> v1 >> v2;
        graph[v2].push_back(v1);
    }
    for(int i=1; i<=N; i++){
        memset(visit, 0, sizeof(visit));
        bfs(i);
        if(counts[i] > max_cnt) max_cnt = counts[i];
    }
    for(int i=1; i<=N; i++){
        if(counts[i] == max_cnt) cout << i << " ";
    }
    
    return 0;
}

---

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1325_bfs.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque, defaultdict

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

for _ in range(M):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v2].append(v1)

def bfs(s):
    q = deque()
    q.append(s)
    visit = [0] * (N+1)
    visit[s] = 1
    counts[s] = 1
    while q:
        now_v = q.popleft()
        for nv in graph[now_v]:
            if not visit[nv]:
                visit[nv] = 1
                counts[s] += 1
                q.append(nv)

max_cnt = 0
counts = [0]*(N+1)
for i in range(1, N+1):
    bfs(i)
    if counts[i] > max_cnt: max_cnt = counts[i]

for i, cnt in enumerate(counts):
    if cnt == max_cnt:
        print(i, end=' ')

---

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1325_dfs.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ1325
//
//  Created by Hwayeon on 2021/08/18.
//

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

int N, M;
vector<int> graph[10001];
int counts[10001] = {0, };
int visit[10001] = {0, };
int max_cnt = 0;

void dfs(int v, int s){
    for(int i=0; i<graph[v].size(); i++){
        if(!visit[graph[v][i]]){
            visit[graph[v][i]] = 1;
            counts[s]++;
            dfs(graph[v][i], s);
        }
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int v1, v2;
        cin >> v1 >> v2;
        graph[v2].push_back(v1);
    }
    for(int i=1; i<=N; i++){
        memset(visit, 0, sizeof(visit));
        visit[i] = 1;
        dfs(i, i);
        if(counts[i] > max_cnt) max_cnt = counts[i];
    }
    for(int i=1; i<=N; i++){
        if(counts[i] == max_cnt) cout << i << " ";
    }
    cout << endl;
    return 0;
}

---

풀이 과정

풀이 시간 23분

 방향 그래프의 탐색 문제이다. 인접 리스트 방식으로 방향 그래프를 표현한 다음, 각 컴퓨터 번호를 시작 노드로 하여 깊이 우선 탐색 DFS 또는 너비 우선 탐색 BFS을 하면 된다.

 

Python3로 채점을 하면 DFS와 BFS 구현 모두 시간초과가 났다.

이론상 DFS와 BFS의 시간복잡도는 O(V+E)이다.

각각의 컴퓨터로부터 완전 탐색을 진행해야 하니 시간복잡도는 O(V(V+E))이다.

문제에서 N은 최대 10,000이고, M은 100,000이니, 총 1,100,000,000번의 연산이 소요되니 10초 이상이 걸린다.

따라서, 시간초과가 날 것이라 생각한다.

실제로 Pypy로 돌리니 재귀를 사용한 DFS는 메모리 초과가 나고 BFS는 16200ms로 통과가 됐다.

하지만 문제의 제한 시간은 5초이고 사실상16200ms는 16초가 넘은 시간인데 시간초과가  나야하는데 왜 통과가 되었는지는 의문이다.

또한, DFS에서 메모리 초과가 나길래 visit 배열을 전역변수로 선언하고 초기화하는 방법으로 수정해 봤는데도 여전히 메모리 초과가 난다.

왜일까..?

#메모리초과 코드
import sys
from collections import defaultdict
sys.setrecursionlimit(500000000)
global m_cnt

def dfs(v, s):
    for nv in graph[v]:
        if visit[nv] == 0:
            visit[nv] = 1
            counts[s]  += 1
            dfs(nv, s)
            
N, M = map(int, sys.stdin.readline().split())
graph = defaultdict(list)

for _ in range(M):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v2].append(v1)


counts = [0]*(N+1)
visit = [0]*(N+1)
max_cnt = 0

for i in range(1, N+1):
    visit = [0]*(N+1)
    visit[i] = 1
    dfs(i, i)
    if counts[i] > max_cnt:
        max_cnt = counts[i]

for i, cnt in enumerate(counts):
    if cnt == max_cnt:
        print(i, end=" ")

 

 C++의 속도가 궁금해서 C++로도 문제를 풀어봤다.

C++로는 DFS와 BFS 코드 모두 통과가 되었다.

BFS 코드는 2920ms, DFS 코드는 3520ms의 시간이 소요되었다.

확실히 C++이 파이썬보다 속도측에서 빠르다는 것을 실감했다.