[DFS / BFS] 연결된 정점들

iberis2·2023년 3월 23일
0

알고리즘 문제

목록 보기
15/27

문제 - [DFS / BFS] 연결된 정점들

방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.

주의사항

주어진 간선은 무향입니다.
[1, 2] 는 정점 1에서 정점 2로도 갈 수 있으며, 정점 2에서 정점 1로도 갈 수 있습니다.

입출력

  • 입력

    • 파라미터 1: edges
      2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록 (2차원 배열, 정수 요소)
      ex) [[0, 1], [1, 2], [3, 4]]

  • 출력

    • Number 타입을 리턴해야 합니다.
    • 연결된 정점의 컴포넌트의 수를 숫자로 반환합니다.

입출력 예시

예시 1

const result = connectedVertices([
	[0, 1],
	[2, 3],
	[4, 5],
]);
console.log(result); // 3

해당 정점들은 아래와 같은 모양을 하고 있습니다.

예시2

const result = connectedVertices([
	[0, 1],
	[2, 3],
	[3, 4],
	[3, 5],
]);
console.log(result); // 2

해당 정점들은 아래와 같은 모양을 하고 있습니다.

풀이

todo 1. 매개변수로 받은 연결된 정점을 2차원 배열을 가지고 → 전체 그래프로 만들기

  • 그래프를 만드는 방법 : 1. 인접행렬, 2. 인접 리스트

todo 2. 만든 그래프를 전체 탐색하면서 연결된 정점 그룹이 전체에서 총 몇 개 있는지 반환하기

  • 그래프를 탐색하는 방법 : 1. DFS, 2. BFS

풀이 1. 인접 행렬 + DFS


// 정점의 수를 구하기 위해 가장 큰 정점의 숫자를 구하는 함수
const getMaxVertex = (edges) =>
  edges.reduce((acc, edge) => {
    const max = Math.max(...edge);
    if (max > acc) return max;
    return acc;
  }, 0);

// 정점들을 연결해 주어진 그래프를 만드는 함수
const makeGraph = (edges, graph) => {
  for (let i = 0; i < edges.length; i++) {
    const vertex1 = edges[i][0];
    const vertex2 = edges[i][1];

    graph[vertex1][vertex2] = 1;
    graph[vertex2][vertex1] = 1;
  }
};

const dfs = (graph, vertex, visited) => {
  visited[vertex] = true;
  for (let next = 0; next < graph[vertex].length; next++) {
    if (graph[vertex][next] === 1 && !visited[next]) {
      dfs(graph, next, visited);
    }
  }
};

// 문제 풀이 함수
function connectedVertices(edges) {
  let count = 0; // 그래프 뭉탱이 개수

  const verticesCount = getMaxVertex(edges) + 1; // 총 정점의 개수 (가장 큰 정점 + 1)

  const visited = new Array(verticesCount).fill(false); // 방문 여부 확인
  const graph = new Array(verticesCount)
    .fill(0)
    .map(() => new Array(verticesCount).fill(0));

  makeGraph(edges, graph);

  for (let vertex = 0; vertex < verticesCount; ++vertex) {
    if (!visited[vertex]) {
      dfs(graph, vertex, visited);
      count++;
    }
  }

  return count;
}

코드를 뜯어보자 !

Todo 1. 매개변수로 받은 연결된 정점을 2차원 배열을 가지고 → 전체 그래프로 만들기

  • 그래프를 만드는 방법 : 인접행렬

  1. 먼저, 주어진 edges 를 가지고 그래프를 인접 행렬(2차원 행렬)로 만들어 주어야 한다.

  2. 2차원 인접 행렬은 이어지지 않은 곳은 0, 이어진 곳은 1로 이루어진 행렬이다.

  • 따라서 먼저, 0으로 이루어진 2차원 배열을 먼저 만들고,
  • makeGraph() 함수를 만들어 이어져 있는 곳은 1로 채워야 한다.
    • 이를 위해 정점이 모두 몇개 인지도 알아야 하는데, 우선 정점의 개수를 구하는 함수가 있다고 가정하고, 정점의 개수를 verticesCount 변수에 담았다고 가정한다.
  1. 그리고 탐색할 때, 이미 방문한 정점인지도 표시해주기 위해, 정점의 개수와 같은 길이의 false로 채워진 1차원 배열도 만든다. 
// 문제 풀이 함수
function connectedVertices(edges) {
  // 정답이 될 그래프 뭉탱이 개수
  let count = 0; 

  
  const verticesCount = // 총 정점의 개수(가장 큰 정점의 숫자 + 1)

   // 정점의 방문 여부 확인      
  const visited = new Array(verticesCount).fill(false);
  
  // 0으로 채워진 2차원 배열
  const graph = new Array(verticesCount)
    .fill(0).map(() => new Array(verticesCount).fill(0));

  makeGraph(edges, graph); // 이어진 정점들은 1로 채워주는 함수

  
  // 정답 그래프 뭉탱이 개수 리턴
  return count;
}
// verticesCount 정점의 개수가 4개(A, B, C D) 라고 가정한다면 
  const verticesCount = 4

  const graph = new Array(verticesCount)
    .fill(0).map(() => new Array(verticesCount).fill(0));

/* 이와 같은 빈 그래프가 만들어 진다.
      A  B  C  D
A [ [ 0, 0, 0, 0 ]  
B   [ 0, 0, 0, 0 ],  
C   [ 0, 0, 0, 0 ],  
D   [ 0, 0, 0, 0 ] ] 
*/

그래프의 이어져 있는 곳은 1로 채워주는 함수를 정의하자
문제에서 주어진 2차원 배열 edges에 이어진 정점들이 표시되어 있다.

  • edges를 돌면서 해당 정점들에 대한 값이 0인 빈 그래프를 1로 채운다.
// 그래프의 이어져 있는 곳을 1로 채우는 함수
const makeGraph = (edges, graph) => {
  for (let i = 0; i < edges.length; i++) {
    const vertex1 = edges[i][0];
    const vertex2 = edges[i][1];

    graph[vertex1][vertex2] = 1;
    graph[vertex2][vertex1] = 1;
  }
};


/* 만약 아래와 같이 이어진 그래프가 있다면 */
const edges = [
  [0, 1], // A - B
  [1, 2], //    B - C
  [2, 3], //        C - D
];

const graph = new Array(4).fill(0).map(() => new Array(4).fill(0));

let fillGraph = makeGraph(edges, graph);
console.log(graph);
/*    A  B  C  D
A [ [ 0, 1, 0, 0 ], 
B   [ 1, 0, 1, 0 ], 
C   [ 0, 1, 0, 1 ], 
D   [ 0, 0, 1, 0 ] ]
*/

todo1. 이 끝났다. 본격적으로 todo2로 넘어가자

Todo 2. 만든 그래프를 전체 탐색하면서 연결된 정점 그룹이 전체에서 총 몇 개 있는지 반환하기

  • 그래프를 탐색하는 방법 : DFS

  1. 그래의 각 정점을 돌면서 방문하지 않았으면 dfs() 탐색 함수로 그래프의 연결된 모든 정점을 탐색한다.

  2. 더 이상 연결된 곳이 없으면 dfs()를 빠져나오고 count를 1개 늘린다.

  • dfs()를 만들기 위해 필요한 것 : graph, vretex(현재 정점), 방문 여부
  1. 시작 정점에서 연결된 정점을 다 돌았는데도 남아있는 정점이 있다면 연결되어 있지 않았던 다음 정점으로 넘어가서 반복한다.
// 문제 풀이 함수
function connectedVertices(edges) {
  // 정답이 될 그래프 뭉탱이 개수
  let count = 0; 

  
  const verticesCount = // 총 정점의 개수(가장 큰 정점의 숫자 + 1)

   // 정점의 방문 여부 확인      
  const visited = new Array(verticesCount).fill(false);
  
  // 0으로 채워진 2차원 배열
  const graph = new Array(verticesCount)
    .fill(0).map(() => new Array(verticesCount).fill(0));

  makeGraph(edges, graph); // 이어진 정점들은 1로 채워주는 함수

/* 그래의 각 정점을 돌면서 방문하지 않았으면 dfs로 탐색 */
  for (let vertex = 0; vertex < verticesCount; ++vertex) {
    if (!visited[vertex]) {
      dfs(graph, vertex, visited);
      count++;
    }
  }

// 정답 그래프 뭉탱이 개수 리턴
  return count;
}

dfs 탐색 함수를 만들면, todo2도 끝이 난다.
1. 우선 방문한 정점을 true로 바꿔준다.
2. 해당 정점의 행을 돌면서, 연결된 곳(1인 곳, 즉 0이 아니므로 true)이면서 아직 방문하지 않은 정점이면 그 정점으로 가서 다시 탐색을 한다(재귀)

const dfs = (graph, vertex, visited) => {
  // 방문한 정점을 표시해준다.
  visited[vertex] = true;
  
  for (let next = 0; next < graph[vertex].length; next++) {
    if (!visited[vertex] && graph[vertex][next]) {
      dfs(graph, next, visited);
    }
  }
};

마지막으로 미뤄뒀던, 총 정점의 개수를 구하는 함수를 만들어 보자

총 정점의 개수는 주어진 edges 배열에서 가장 큰 수 + (번호가 0부터 시작하므로) 1개 이다.

// 총 정점의 개수(가장 큰 정점의 숫자 + 1)
const verticesCount = getMaxVertex(edges) + 1;

edges에서 가장 큰 수를 구하는 함수는 다음과 같다.

  1. edges는 2차원 배열이다.
    따라서 배열의 요소인 inner배열(= 변수 edge)들을 돌면서,

  2. inner배열(= edge)의 요소인 숫자 중 큰 수(=변수 max)를 저장하고,
    (= 변수 acc에 담고,)

  3. 다음 inner배열(= edge)의 큰 수(= max)와 acc를 비교해서, acc를 다시 할당한다.

const getMaxVertex = (edges) => {
  return edges.reduce((acc, edge) => {
    // edge = 배열의 요소 안에 들어있는 배열
    // max = edge에 담긴 정점 2개 중 큰 수
    let max = Math.max(...edge);

    // 현재의 max가 acc(이전까지의 max)보다 크면 max가 acc가 된다.
    if (max > acc) return max;
    return acc;
  }, 0);
};

만약 edges 가 다음과 같다면, verticesCount 는 4가 된다.

const edges = [
 [0, 1], // A - B
 [1, 2], //    B - C
 [2, 3], //        C - D
];
profile
iberis2
React, Next.js, TypeScript 로 개발 중인 프론트엔드 개발자
이전 포스트

[프로그래머스-JS] 삼총사 - 재귀함수

다음 포스트

[Binary Search 이진탐색] getItemFromTwoSortedArrays

0개의 댓글

관련 채용 정보