Portfolio

문제

풀이

은찬


const solution = (n, wires) => {
    let answer = Infinity;
    
    const graph = Array.from({length: n + 1}, () => Array(n + 1).fill(false));
    const visited = Array.from({length: n + 1}, () => Array(n + 1).fill(false));
    
    const bfs = (currentNode) => {
        const visitedNode = Array(n + 1).fill(false);
        const queue = [];
        let count = 0;
        
        queue.push(currentNode);
        visitedNode[currentNode] = true;
        
        while(queue.length){
            const node = queue.shift();
            
            count++;
            
            for(let i = 1; i <= n; i++){
                if(!visitedNode[i] && graph[node][i]){
                    visitedNode[i] = true;
                    queue.push(i);
                }
            }
        }
        
        answer = answer < Math.abs(count - (n - count)) ? answer : Math.abs(count - (n - count));
    }
    
    for(let i = 0; i < wires.length; i++){
        const [start, end] = wires[i];
        
        graph[start][end] = true;
        graph[end][start] = true;
    }
    
    for(let i = 1; i <= n; i++){
        for(let j = 1; j <= n; j++){
            if(!visited[i][j] && graph[i][j]){
                visited[i][j] = true;
                visited[j][i] = true;
                
                graph[i][j] = false;
                bfs(i);
                graph[i][j] = true;
            }
        }
    }
    
    return answer;
}

재영


class Queue {
  constructor(val) {
    this.queue = val ? [val] : [];
    this.front = 0;
    this.rear = this.queue.length;
  }
  enqueue(...args) {
    this.queue.push(...args);
    this.rear += args.length;
  }
  dequeue() {
    const value = this.queue[this.front];
    this.front += 1;
    return value;
  }
  size() {
    return this.rear - this.front;
  }
}

const makeGraph = (wires) => {
  const graph = {};

  wires.forEach(([from, to]) => {
    graph[from] = graph[from] ? [...graph[from], to] : [to];
    graph[to] = graph[to] ? [...graph[to], from] : [from];
  });

  return graph;
};

const solution = (n, wires) => {
  let minValue = Infinity;
  const start = wires[0][0];
  const visited = new Array(n).fill(false);

  const graph = makeGraph(wires);

  wires.forEach(([from, to]) => {
    const nowGraph = { ...graph };
    nowGraph[to] = nowGraph[to].filter((val) => val !== from);
    nowGraph[from] = nowGraph[from].filter((val) => val !== to);

    const queue = new Queue(start);
    const nowVisited = [...visited];

    while (queue.size()) {
      const now = queue.dequeue();
      nowGraph[now].forEach((next) => {
        if (!nowVisited[next]) {
          queue.enqueue(next);
          nowVisited[next] = true;
        }
      });
    }

    const nowValue = nowVisited.filter((bool) => bool).length; // 그래서 방문한 전력망에 대한 배열 정보 (true / false)
    minValue = Math.min(minValue, Math.abs(n - nowValue * 2));
  });

  return minValue;
};

console.log(solution(n, wires));

효성

첫 번째 풀이 - `실패`

송전탑이 정렬되지 않다면 에러가 날 수 있는 풀이임.

컴퓨팅적인 사고 방식이 필요함!


function solution(n, wires) {
    let diff = [];
    for(let i=0; i<wires.length; i++) {
        let arr = [];
        arr.push(...wires.slice(0, i).concat(wires.slice(-(wires.length-i))));
        let diffNum = getNodeCnt(arr);
        diff.push(diffNum);
    }
    return Math.min(...diff);
}

function getNodeCnt(cutWires) {
    const wires1 = [], wires2 = [];

    wires1.push(...cutWires[0]);

    for(let i=1; i<cutWires.length; i++) {
        for(let j=0; j<2; j++) {
            if(wires1.includes(cutWires[i][j])) {
                wires1.push(...cutWires[i][j]);
            }
            else {
                wires2.push(...cutWires[i][j]);
            }
        }
    }
    return Math.abs(wires1.length - wires2.length);
}

전력망을 둘로 나누기

문제

풀이

첫 번째 풀이 - `실패`

참고한 풀이

전력망을 둘로 나누기

문제

풀이

첫 번째 풀이 - 실패

참고한 풀이

첫 번째 풀이 - `실패`