[알고리즘] 인접 행렬(adjacency matrix) 길찾기

지난 목요일부터 4일째 자료구조(스택, 큐, 트리, 그래프)를 배우면서 아침부터 밤까지 내내 알고리즘 문제만 들여보고 있으니 머리가 과포화 상태다 ㅋㅋㅋ 금요일 정규 시간에 못 푼 문제들(태반...)을 주말 동안 붙잡고 늘어지느라 주말에 해야 할 다른 일들을 하나도 못했다. 😭 아직 열어보지도 못한 advanced 문제들이 남아있다는 것이 함정... 지금 본다고 알 것 같지도 않은 게 더 함정... 

 

이번 포스팅에서는 그래프를 이용한 알고리즘 문제 중 하나였던 길찾기 문제를 셀프 크리틱해보려 한다. 알고리즘 문제에서 많이 등장하는 길찾기 패턴 문제를 처음으로 어떻게 다뤄야 하는지 알게 된 것이 이번 자료구조/알고리즘 유닛의 최대 성과였다. 

 

💡 그래프의 각 정점을 순회할 수 있는 DFS, BFS 두 가지 방식 중 Breadth First Search(BFS)를 사용하면 최단 경로를 찾을 수 있다. 

 

문제: 주어진 인접 행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 여부를 반환한다. 

입력
- 인자 1 (matrix): Array 타입을 요소로 갖는 인접 행렬이 담긴 2차원 배열
- 인자 2 (from): Number 타입의 시작 정점
- 인자 3  (to): Number 타입의 도착 정점

출력 : boolean 타입 리턴

 

입출력 예시: 

const result = getDirections(
	[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	2
);
console.log(result); // true
// 정점 0에서 2로 가는 길이 존재하는지 확인합니다.
// 0 --> 1 로 가는 간선이 존재하고, 1 --> 2 로 가는 간선이 존재하기 때문에 true를 반환합니다.

const result2 = getDirections(
	[
		[0, 1, 0, 0, 0],
		[0, 0, 0, 1, 0],
		[0, 1, 0, 0, 0],
		[0, 1, 1, 0, 0],
		[1, 1, 1, 1, 0],
	],
	1,
	4
);
console.log(result2); // false

// 정점 1에서 4로 가는 길이 존재하는지 확인합니다.
// 1 --> 3,
// 3 --> 1 (정점 1을 다녀왔으니 다시 돌아가지 않습니다),
// 3 --> 2,
// 2 --> 1 (정점 1을 다녀왔으니 다시 돌아가지 않습니다)
// ...으로, 4에 도달할 수 없습니다.

 

내가 푼 코드는 다음과 같다. 

 

레퍼런스 코드를 보니 기본적인 논리 흐름은 거의 똑같았다. 차이점은 while loop 안에서 간선들을 확인하고 순회하는 과정에서 나는 불필요하게 forEach를 두 번 돌렸다는 점이었다. 사실 시간복잡도 측면에서는 2O(N)이나 O(N)이나 똑같긴 하지만.. 인접 행렬을 한 번만 순회하면서도 그 안에서 조건문 분기를 적절하게 추가해줘서 필요한 작업을 하고 for loop를 빠져나오면 되는건데, 아직 조건문 분기 추가, 특히 두 가지 이상의 조건이 필요할 때 논리곱이나 논리합을 사용해서 적절한 조건문 분기를 설정하는 게 어려운 것 같다. 

 

내 코드와 레퍼런스 코드에서 달랐던 부분만 따로 떼어내서 보면 아래와 같다. 

// 내가 작성한 코드
const allNeighbors = [];
matrix[currentVertex].forEach((el, idx) => {
  if (el === 1) allNeighbors.push(idx);
});

allNeighbors.forEach((neighbor) => {
  if (!visited[neighbor]) {
    visited[neighbor] = true;
    queue.push(neighbor);
  }
});

// 레퍼런스 코드
matrix[currentVertex].forEach((el, idx) => {
  const neighbor = idx;
  if (matrix[currentVertex][neighbor] && !visited[neighbor]){
    visited[neighbor] = true;
    queue.push(neighbor);
  }
})

 

레퍼런스 코드에는 for loop로 작성되어 있지만, 내가 작성한 코드와 똑같이 맞춰보기 위해서 forEach로 수정했다. 

 

1) 간선이 있는지 확인하고, 2) 방문한 적이 없는 정점이라면 방문했다고 표시해주고, 그 정점을 enqueue(queue에 push)하는 작업을 수행하기 위해서 나는 먼저 간선이 있는 정점들을 뽑아내서 allNeighbors라는 배열에 담아준 다음, 해당 배열을 다시 한 번 순회하면서 2)의 작업을 해준 반면, 레퍼런스에서는 순회를 한 번만 하면서 1)과 2)를 동시에 논리곱(&&)으로 체크한 후에 2)의 작업을 수행함으로써 불필요한 변수(allNeighbors) 선언을 하지 않는 간결한 코드를 작성했다. 

 

중요한 점은 결국 조건문의 분기 설정으로, 어제 괄호쌍 문제에서도 이에 대해 언급했었다. 앞으로 알고리즘 문제를 풀거나 기능 구현을 할 때 항상 이 부분을 염두에 두어야겠다.

 

💡 리팩토링을 할 때:
논리곱이나 논리합을 조건에 추가함으로써 불필요한 작업을 줄일 수 있지 않은지 확인해 보자.

 

 

+)

번외로 코드를 짤 때 findIndexAll 메소드가 있을 줄 알았는데 없어서(!) 한 차례 당황했다가 forEach로 배열을 순회하는 방법을 택했다. 그런데 찾아보니 stackoverflow에 아래처럼 reduce로 findIndexAll을 구현한 코드가 있더라. reduce는 정말 만능 메소드구나. 나도 reduce 잘 쓰는 사람이 되고 싶다. 🙄

 

    const allNeighbors = matrix[currentVertex].reduce((acc, el, idx) => {
      if (el === 1) acc.push(idx);
      return acc;
    }, [])
    
// 내가 작성한 코드
    const allNeighbors = [];
    matrix[currentVertex].forEach((el, idx) => {
      if (el === 1) allNeighbors.push(idx);
    });