개발 R.I.P.

7.27 Dev.Feedback ( forEach)

편행 2021. 7. 27. 19:40
반응형

자료구조 및 알고리즘은 내가 개발자로 일하기 위해 그리고 정말 뛰어난 실력을 갖기 위한 컴퓨팅적 사고를 갖기 위해 꼭 이해해야만 하는 영역이라 생각한다. 그 중 인접행렬 생성하기 알고리즘을 풀며 forEach 메소드에 대해 다시 생각하는 계기가 생겨 포스팅해본다.

 

인접행렬 생성하기 알고리즘

먼저 인접행렬 생성하기 알고리즘은 Number 타입의 방향/무향인 간선들의 목록이 담긴 배열을 입력 받아

[
	[0, 3, "directed"],
	[0, 2, "directed"],
	[1, 3, "directed"],
	[2, 1, "directed"],
]


[
	[0, 2, "directed"],
	[2, 4, "undirected"],
	[1, 3, "undirected"],
	[2, 1, "directed"],
]

위의 간선들에 대한 정보가 담긴 새로운 이중 배열을 반환하는 알고리즘이다. Graph 자료구조 중에 하나인데

인접행렬을 구현하기 위해선 먼저 입력값으로 들어오는 배열 내부를 탐색하여 가장 큰 수를 찾고, 가장 큰 수를 배열의 길이로 정하여 모든 배열의 값이 0인 이중 배열을 먼저 생성해준다.

// 행렬의 크기를 구한다.
	let max = 0;
    // 먼저 max 변수를 0으로 할당하고, edges를 전부 순회하여 제일 큰 숫자(curMax)를 max에 할당한다.
    // max보다 크지 않을 경우엔 바꾸지 않는다.
	for (let i = 0; i < edges.length; i++) {
		// edges의 한 요소에는 숫자 이외에 방향성도 있으니, 숫자까지만 slice를 하여 비교한다.
		const curMax = Math.max(...edges[i].slice(0, 2));
		curMax > max ? (max = curMax) : null;
	}

  // matrix의 뼈대를 잡는다.
  // max로 구한 최대값에 1을 더하여 array를 만들고(0번째부터 있기 때문) 전부 0으로 채운 뒤
	// map을 사용해 각 요소마다 배열로 바꿔준다. 배열의 크기를 이번에도 최대값에 1을 더한 뒤, 0으로 채웁니다.
	const result = new Array(max + 1).fill(0).map((row) => new Array(max + 1).fill(0));
  
  //만일 위의 코드가 잘 작동하면, 아래의 메트릭스처럼 정 사각형의 이중 배열이 생성될 것이다.
  
  const matrix = [
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
];

그리고 이제 무방향(undirected), 방향(directed)의 여부를 판단하여 숫자를 변경해주어야 하는데 만일 위의 경우처럼 무방향은 양쪽에 간선이 이어지는 것이고 방향이면 한쪽 방향으로만 간선이 이어진 것이다.

[0,3, directed]라면 matrix[0][3]에 1을 입력해주면 되는데, [2,4,undirected]라면 matrix[2][4]에 1을 입력해주는 것 뿐 아니라 matrix[4][2]에도 1을 입력해줘야 하는 것이다. (연결이 되었기 때문에)

// edges를 순회하며 무향인 곳엔 각각의 간선에 1로 바꾸어 주고, 방향이 있는 간선엔 해당 간선에만 1로 바꾸어 준다.
	// 만약, [0, 3, "directed"]가 들어왔다면,
	// 만들어 둔 result의 0 번째 row에 3 번째 col에 1을 추가한다.
	// [ 0, 0, 0, 1 ] => 0번째 버텍스가 갈 수 있는 간선 중, 3 번으로 가는 간선만 갈 수 있다.
	edges.forEach((edge) => {
		const [row, col, direction] = edge;
		if (direction === "undirected") {
			result[col][row] = 1;
		}
		result[row][col] = 1;
	});

위 코드에서 갑작스럽게 이해가 안됐다. forEach를 정확히 이해하지 못했기 때문이다. 먼저 forEach 메소드는 어떤 배열의 모든 요소에 callback함수를 적용해주는 메소드이다. 그리고 반환하는 값은 undefined. Map 메소드와 동일하게 작동하지만, return값이 다른 것이 가장 큰 차이점이다.

여기서 내가 몰랐던 부분은 if문 부분이었다. 나는 당연하게도 if 조건문 내부에 있는 부분만 생각을 했기에 만일 무방향이라면 result[col][row]에 1을 넣어주고, 아닌 경우에는 result[row][col]만 해준다. 즉, directed인 경우에만 result[row][col] = 1 이 적용된다고 생각했다. 여기서 의문이 들었다. 분명히 undirected라면 양쪽에 간선이 이어진 것이니 그것을 해줘야할텐데? 왜 안하지???

 

forEach 다시 생각해보자.  forEach 메소드는 어떤 배열의 모든 요소에 callback함수를 적용해주는 메소드이다.

아주 당연하게도 생각했던 것을 제대로 적용도 시키지 못한 것이다. 즉 forEach 메소드에 의해 모든 요소에 result[row][col] =1은 적용이 되는 것이고, 따로 예외를 들어 무방향인 경우를 체크하여 그때에 result[col][row] =1 을 해준 것이다. 아주 미련하긴 했지만, 그냥 얼추 넘어가는 것보다 확실하게 이해를 하기 위해 그리고 내가 얼마나 어리석은지 항상 알고, 오만하게 판단하지 않기 위해 작성을 해놓는다.

모든 코드에 대해서 정확히 분석하고 뜯어보는 그리고 머릿속에서든지 손으로라든지 꼭 직접 어떤 코드가 어떻게 구현되는지 생각을 해야한다.

반응형