[TIL] 자료구조 보충 학습

어려웠던 자료구조 문제 풀이 하나하나 뜯어보기

인접 행렬 길찾기

주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환
matrix, from, to가 주어짐

초기세팅

• 방문했던 정점을 기록해둘 방법 : checkList라는 false들이 담긴 배열을 만들어준다. false는 행렬의 행 수 만큼 담겨져 있다.
• 앞으로 검사해야 할 정점들을 담을 배열 : queue라는 배열을 만들어준다. queue는 계속해서 to인지 확인해야할 정점들이 들어온다. 앞에서부터 차례로 삭제해가며 판별하고, 더 이상 검사할 정점이 없을 때 반복문(while)이 끝이 난다.
• 첫 시작점인 from은 항상 맨 처음으로 방문할 정점이므로 queue에 담아주고, 방문했던 정점이라고 checkList에 표시해주어야 함.

반복문 내부에서 할 일

• queue의 맨 앞에서 정점을 제거하고, 정점을 검사한다. (to 정점이라면 바로 true를 리턴)
• 검사한 정점이 to 정점이 아니라면 다른 정점으로 가는 길이 있는지 확인하고, 그 정점이 방문하지 않은 정점이라면 queue에 추가해준다. (추가해주면서 해당 정점을 방문했다고 표시해준다)
• 반복문이 끝나면 false를 리턴한다. (중간에 true로 리턴되지 않았으면 도달할 수 없음을 의미한다)

 function getDirections(matrix, from, to) {

   //정점을 방문했는지 체크할 변수인 checkList를 만든다 
   let checkList = new Array(matrix.length).fill(false);

   //앞으로 검사해야 할 정점을 담은 queue 만든다
   let queue = [];

   //첫 시작점을 queue에 담는다
   queue =[from];
   //첫 시작점을 방문한 정점이라고 표시해준다.
   checkList[from] = true;

   //queue가 빌 때까지 반복문을 돌린다 
   while(queue.length > 0){
     //queue에서 맨 처음의 정점을 제거하고, 아래에서 제거한 정점을 검사한다. 
     let deq = queue.shift();

      //제거한 정점이 to이면 from에서 to로 가는 길이 존재하는 것이니까 true를 반환.
     if(deq === to){
       return true;
     }

      //to가 아닌 경우 해당 정점에서 to로 가는 길이 있는지 검사해야 한다. 
      //matrix[deq]의 0번째부터 to번째까지 검사하면서 간선이 있는지(해당 인덱스의 값이 1인지 && 이미 방문했던 곳이 아닌지) 검사함.
     for(let i=0; i<matrix[deq].length;i++){
       if(matrix[deq][i]===1 && checkList[i]===false){
         //만약 간선이 존재하며, 아직 방문하지 않았다면 queue에 넣어준다.
         //반복문(while문)이 돌아가면서 해당 queue에 든 정점이 to인지 확인하는 과정을 거칠 것임. 
         queue.push(i);//위에서 deq를 만들었듯이, enq라는 queue.push()하는 매서드를 만들어 사용할 수도 있다. 

          //체크리스트에 해당 정점을 방문했다고 표시해준다 
         checkList[i] = true;

       }
     }
   }

   return false;
 }

연결된 정점의 그룹이 몇 개인가?

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

인자로는 edges라는 2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록이 들어온다. (2차원 배열, 정수 요소) ex) [[0, 1], [1, 2], [3, 4]]

위 예시의 경우에 정점 0에서 1로 1에서 2로 연결되는 그룹 하나와, 정점 3에서 4로 연결되는 그룹 하나로 총 2개의 그룹이 존재한다.

이 문제는 래퍼런스에서는 함수 하나만 가지고 푸는 건 아니고, 너비 우선 탐색이나 깊이 우선 탐색을 하는 함수를 하나 만들어서 해결했지만, 세션에서 설명을 들을 때는 다른 방식으로도 풀 수 있었다.

초기세팅

• 방문했던 정점들 기록해둘 배열 : edges의 길이만큼 false를 담는다.
• 검사할 정점들을 담은 배열 queue를 만든다.
• 그룹 개수를 기록할 변수 count를 만든다.

반복문 내부에서 할 일

• edges 배열의 처음 요소부터 마지막 요소까지 배열을 탐색함.
• 해당 요소에 방문했던 적이 없다면 그 요소와 연결된 모든 요소들을 방문하고, 배열에 해당 요소를 방문했었다고 표시한다.
• 이어진 정점을 모두 검사하고 나서 count 변수를 1씩 증가시켜준다.
• edges 배열의 탐색이 끝난 뒤 count를 리턴한다.

function connectedVertices(edges) {
  let checkArr = new Array(edges.length).fill(false);
  let queue = [];
  let count = 0;

  for(let i=0;i<edges.length;i++){
    if(checkArr[i] === false){
      queue.push(edges[i]);

      while(queue.length>0){
        let deq = queue.shift();

        for(let j=0;j<edges.length;j++){
          if(checkArr[j] === false){
            if(edges[j][0] === deq[1] || edges[j][1] === deq[1] || edges[j][0] === deq[0]||edges[j][1] === deq[0]){
              queue.push(edges[j]);

              checkArr[j] = true;
            }
          }
        }
      }
      count+= 1
    }
  }
  return count;
}

위 코드를 뜯어보면서 왜 checkArr를 정점의 개수만큼 만드는 게 아니라 edges의 길이만큼 false를 담아두는지 궁금했는데, 이 풀이에서 중요한 건 정점과 간선이 표시된 행렬을 직접 만드는 게 아니라 그냥 저 edges들이 담긴 배열만을 이용해서 풀기 때문인 것 같았다.
checkArr의 용도도 결국 해당 요소(연결관계)를 한 번 확인했냐 안 했냐를 확인하는 것이다.

반대로 만약 정점과 간선을 표시한 행렬을 직접 만들어서 풀게 된다면 그 정점을 방문했냐 안 했냐를 표시해야 하기 때문에 checkArr를 만들 때 우선 edges에서 언급된 정점들 중 가장 큰 수를 구하고, 그 수(정점의 수)만큼의 false를 담은 배열을 할당해주어야 한다.

인접 행렬을 만들어 풀 수도 있지만, 인접 리스트를 만들어서 풀 수도 있는데,
인접 리스트와 너비 우선 탐색, 깊이 우선 탐색을 사용해 푸는 방식은 아래와 같다.

//래퍼런스 

function connectedVertices(edges) {
 // 최대 정점을 찾는다.
	const maxVertex = edges.reduce((a, c) => {
		const bigger = Math.max(...c);
		if (bigger > a) return bigger;
		return a;
	}, 0);

	// 인접 리스트는 객체로 만든다. 
	const adjList = {};

  // 인접 리스트에 최대 정점 크기만큼 반복해 정점을 만들어 줍니다.
	for (let i = 0; i <= maxVertex; i++) {
		adjList[i] = [];
	}

  // edges를 순회하며, (무향 그래프이므로 쌍방으로) 간선을 연결함.
// adjList 그래프 완성.
	for (let i = 0; i < edges.length; i++) {
		adjList[edges[i][0]].push(edges[i][1]);
		adjList[edges[i][1]].push(edges[i][0]);
	}

  // 방문한 버텍스를 담을 객체를 선언.
	const visited = {};
	// 그룹이 몇 개인지 카운트할 변수를 선언.
	let count = 0;

  // 그래프에 있는 정점을 전부 순회합니다.
	for (let vertex = 0; vertex <= maxVertex; vertex++) {
		//bfs를 아래에 함수로 만들어 놓았음. 
		// 만약 i 번째 정점을 방문하지 않았다면 bfs로 해당 정점과, 정점과 연결된(간선) 모든 버텍스를 방문함.
		// BFS로 갈 수 있는 모든 정점들을 방문하며 visited에 담기 때문에, 방문한 정점들은 visited에 들어 있어서 bfs를 돌지 않음.
		// 이렇게 그룹을 확인함.
		if (!visited[vertex]) {
			// 인접리스트와 정점, 방문했는지 확인할 visited를 변수에 담는다.
			bfs(adjList, vertex, visited);

			// 카운트를 센다.
			count++;
		}
	}

  // 모든 과정을 마치면 카운트를 반환.
	return count;
}



// bfs 너비 우선 탐색 
function bfs(adjList, vertex, visited) {

	// bfs는 가장 가까운 정점부터 탐색하기 때문에 queue를 사용한다.
	// queue에 vertex로 받아온 정점을 담는다.
	const queue = [vertex];
	// 해당 버텍스를 방문했기 때문에 visited에 담아 주고, 방문했다는 표시인 true를 할당합니다.
	visited[vertex] = true;

  // queue의 길이가 0일 때까지 순환.
	while (queue.length > 0) {

		// cur 변수에 정점을 할당.
		// queue는 선입선출이기 때문에 shift 메소드를 사용하여 버텍스를 가져옴.
		const cur = queue.shift();

		// 그래프의 cur 정점에 있는 간선들을 전부 순회한다.
		for (let i = 0; i < adjList[cur].length; i++) {

			// 만약, 해당 버텍스를 방문하지 않았다면 queue에 삽입.
			// 방문했다는 표시로 visited에 해당 버텍스를 삽입하고 true를 할당.
			if (!visited[adjList[cur][i]]) {
				queue.push(adjList[cur][i]);
				visited[adjList[cur][i]] = true;
			}

			// queue에 다음으로 방문할 버텍스가 있기 때문에 while은 멈추지 않음.
			// 만약, queue가 비어 있다면 더 이상 갈 곳이 없는 것이기 때문에 bfs 함수를 종료하고 카운트를 센다.
		}
	}
}