요즘시대에 바이러스 파이프

Об этом предложении

마찬가지로 제대 날짜가 다가오기때문에 알고리즘을 풀어 보고자 한다. 앞으로는 풀이에 앞서 핵심 아이디어, 시간복잡도, 알고리즘과 자료구조를 먼저 정리할 것이다. 그리고 마지막에 해당 문제의 유형을 스스로 생각해서 정의해볼것이다. 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/468373 문제 설명 edge는 A,B,C 타입이 존재하고 매 행동마다 A,B,C 중 하나를 선택하는 것을 K번 반복해서 최대한 많은 배양체를 감염시킬 수를 구하는 문제다. 아이디어 처음 해야할 일은 주어진 edges를 바탕으로 그래프를 만들어내야한다. 각 노드가 어떤 타입의 edge로 연결되어있는지로 데이터를 구성하고, DFS로 A,B,C 중 하나의 타입을 선택하면서 K의 길이를 가지는 중복순열을 만들어내면된다. 순서는 다음과 같다. 타입을 정한다. 감염된 모든 배양체를 기준으로 인근에 같은 타입을 가진 Node를 그래프 순회하면서 감염시킨다. 이걸 K번 반복한다. 여기서 오픈할 edge 타입을 중복순열 배열로 먼저 만들어두고, 각각 그래프를 순회해서 완전 탐색해도 되지만 DFS를 이용해 하나씩 선택하면서 완전탐색 할 수도있다. 단, 여기서 중요한건 한번 열때 시작으로부터 감염된 노드의 인근에 같은 타입을 가지는 노드가 있다면 그것도 한번에 감염시켜줘야 한다는것이다. 시간복잡도 여기서 K의 길이는 최대 10이므로 각 순열의 최대 수는 3^k 엄밀히 따지면 특정 타입이 연달아 나올수는 없으므로 3*2^(k-1)가 된다. DFS의 비용은 O(V) + O(E)이 므로 시간복잡도는 3* 2^(k-1) * (V+ E)가 된다. 문제 유형 그래프 탐색과 DFS 구현하면 쉽게 풀릴 문제이다. 문제의 유형은 그래프 탐색 + DFS 기반 완전탐색 문제가 되겠다. 전체 코드 const TYPE_A = 1; const TYPE_B = 2; const TYPE_C = 3; const buildGraph = (edges,n) => { const nodes = Array.from({ length : n+1 }, () => []); for (const [parent,child,type] of edges) { nodes[parent] = { ...nodes[parent], [type] : [ ...nodes[parent][type] ?? [], child ] } // 쌍방향이기때문에 그래프를 제대로 완성시켜줘야 nodes[child] = { ...nodes[child], [type] : [ ...nodes[child][type] ?? [], parent ] } } return nodes; } function solution(n, infection, edges, k) { let answer =0; const nodes = buildGraph(edges,n); const infected = Array(n+1).fill(false); const spread = (infected,type) => { const newInfected = [...infected]; const queue = []; // 1~부터 n까지 값이 들어가기때문에 부등호처리 제대로 해야한다. 이걸로 1시간날렸다 for(let i=1; i<=n; i++){ if(newInfected[i] && nodes[i][type]){ for(const nIndex of nodes[i][type]){ if(!newInfected[nIndex]){ newInfected[nIndex]= true queue.push(nIndex); } } } } while(queue.length){ const nextNode = queue.pop(); if(nextNode && nodes[nextNode][type]){ for(const nIndex of nodes[nextNode][type]){ if(!newInfected[nIndex]){ newInfected[nIndex] = true; queue.push(nIndex); } } } } return newInfected; } const dfs = (depth,infected,prevType,logType) => { let count = 0; // 1~부터 n까지 값이 들어가기때문에 부등호처리 제대로 해야한다. 이걸로 1시간날렸다 for(let i =1; i<=n; i++){ if(infected[i]){ count++; } } answer= Math.max(answer,count); if(depth === k){ return } for(const type of [TYPE_A,TYPE_B,TYPE_C]){ if(type === prevType) continue const nextInfected = spread(infected,type) dfs(depth+1,nextInfected,type) } } infected[infection]= true; dfs(0,infected,null) return answer ; }

Детали предложения

Провайдер

velog

Источник

velog-rss