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

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

해당 문제는 시간초과로 마무리 지은 문제입니다.

처음접근

간선이 주어지고 A가 B를 신뢰한다 이면 B를 해킹하면 A도 해킹할 수 있음, 하지만 A를 해킹하면 B를 해킹할수는 없다.
인접리스트를 생성할때 양쪽을 생성하는게 아닌 주어진 간선에 대한 인접 리스트만 생성하고 BFS로 풀면 되겠다 !

const fs =require('fs')
const input = fs.readFileSync('../text.txt').toString().trim().split('\n').map(item=>item.split(' ').map(item=>+item))
// const input = fs.readFileSync('dev/stdin').toString().trim().split('\n').map(item=>item.split(' ').map(item=>+item))
const [N,M] = input.shift()
const adjList = {}

//인접리스트 객체 key : value(배열) 로 초기화
for(let i = 1; i<=N;i++)
{
    adjList[i] = []
}

for(let i = 0; i<M;i++)
{
    let edge = input[i]
    adjList[edge[1]].push(edge[0]) //A가 B를 신뢰한다 -> B를 해킹하면 A를 해킹할 수 있다 -> B에 A가 연결된 구조
    // adjList[edge[0]] = edge[1] -> 기존의 인접리스트와는 다르게 주어진 간선만을 할당해줌
}


function bfs(startVertex)
{
    //방문했는지 확인하는 visited 객체
    let visited = {}
    //방문이 필요한 노드를 확인하는 queue 선언
    let needVisit = []

    //start vertex를 방문할 노드에 추가
    needVisit.push(startVertex)
    //start vertex를 방문했다고 추가
    visited[startVertex] = true
    //방문할 노드가 없을때까지
    while(needVisit.length)
    {
        //bfs이니까 맨 앞에있는것부터 너비 탐색 shift로 빼주기
        let currentVertex = needVisit.shift()
        //탐색하는 노드에 연결되어있는 인접리스트를 탐색
            adjList[currentVertex].forEach(vertex=>{
                //연결되어있는 인접리스트가 방문하지 않았다면
                if(visited[vertex] != true) {
                    //방문했다고 변경하고
                    visited[vertex] = true
                    //탐색할 노드에 추가
                    needVisit.push(vertex)
                }
            })
    }
    //startvertex에서부터 bfs로 탐색하면 몇개의 노드를 탐색하는지에 대한 개수를 반환
    return Object.keys(visited).length
}

let max = 0;
let result = []
//startvertex를 하나씩 모두 확인
for(let i = 1;i<=M;i++)
{
    //bfs로 탐색했을때 노드의 개수가 최대인지 확인
    if(max < bfs(i))
    {
        result = []
        max = bfs(i)
        result.push(i)
    }
    else if(max === bfs(i))
    {
        result.push(i)
    }
}
console.log(result.join(' '))

이렇게 코드를 작성했는데 1%에서 시간초과가 떴다..
시간을 많이 잡아먹는 부분은 어떤 부분일까?
아무래도 입력값이 N은 10,000 이고 M은 100,000 이니까 배열을 push한다면 꽤 시간을 잡아먹겠다는 생각이 들었다.
-> 시도했지만 실패..

인접 리스트를 만드는 부분이 문제가 아니었고 dfs로 구현을 해야한다는데 이 문제를 dfs로 풀어야 하는 명확한 이유를 찾을수가 없었다. 맞기 위해 이것저것 이유도 모르고 구현하는건 시간낭비일 것 같다는 생각이 들었기에 그냥 이 문제는 생각한 아이디어로 구현한 걸로 만족하고 넘어가기로 했다

정리
인접리스트를 구현할때 주어진 간선만 단방향으로 구현하기
노드의 개수가 몇번 탐색되었는지 구현하는 로직을 작성하기
시간초과로 오류가 나왔지만 다른 방법으로 구현해야 하는 명확한 이유를 납득하지 못해서 백준이니까.. 과감하게 스킵했다

문제를 풀진 못했지만 점점 구현하는 속도도 빠르고 비슷한 결의 풀이방향이 떠올라서 실력이 늘고있는듯한 느낌을 받았다

끝!