N

https://programmers.co.kr/learn/courses/30/lessons/86971?language=cpp 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr bfs를 활용한 문제 풀이. 우선 주어진 wires 벡터로 그래프를 그려 주도록 하자. 이후 한 노드를 선택해 연결 되어 있는 노드를 끊고 BFS 탐색을 진행하여 끊은 노드의 개수를 구하면 된다. 이때, n * n 크기의 visited 벡터를 만들어, 이미 끊었던 간선을 다시 끊는 일이 없도록 가지를 친다. bfs() 함수에 그려 놓았던 그래프와 n, 현..

그래프(Graph) 정점과 정점 사이를 연결하는 간선으로 이뤄진 비선형 자료구조. 정점 집합과 간선 집합으로 표현할 수 있다. 지하철 노선도나 인물 관계도를 떠올리면 쉽게 이해할 수 있다. 정점은 여러 개의 간선을 가질 수 있다. 방향 그래프와 무방향 그래프가 존재. 간선은 가중치를 가질 수 있다. 사이클이 발생할 수 있다. JS에서 인접 행렬, 인접 리스트로 그래프를 표현할 수 있다. 무방향 그래프 간선으로 이어진 정점끼리는 양방향으로 이동이 가능. ex) (A, B) == (B, A) 방향 그래프 간선에 방향성이 존재하는 그래프. 양방향으로 갈 수 있어도 와 는 다른 간선으로 취급된다. 코드 // 인접 행렬 const graph = Array.from(Array(5), () => Array(5).fi..