Graph를 통한 인접 행렬 생성하기 Javascript

cptkuk91·2022년 8월 22일
1

Algorithm

목록 보기
75/161
post-custom-banner

문제

방향이 있는 간선과 방향이 없는 간선들의 목록들을 받아 2차원 배열의 인접행렬을 반환하는 함수를 작성하세요.

조건

각 간선은 3가지 정보를 담고 있습니다.
0번째: 간선의 시작 정점 (0 이상의 정수)
1번째: 간선의 도착 정점 (0 이상의 정수)
2번째: 방향성 ('undirected' 일시 무향, 'directed' 일시 방향)

주의 사항

  • 정점 0에서 정점 4로 이어주는 간선이 존재할 경우 정점 1, 2, 3도 존재합니다.
  • 반환하는 인접행렬은 2차원 배열이며, 행(row)는 바깥 배열, 열(column)은 안쪽 배열입니다.
    let matrix = [[0, 0], [0, 0]]
    matrix[0] === 0번째 행
    matrix[0][0] === 0번째 행의 0번째 열
  • 두 정점간의 간선의 유무는 0과 1로 표시합니다.
    0: 두 정점간에 간선이 존재하지 않을 경우
    1: 두 정점간에 간선이 존재할 경우
  • 아래의 2차원 배열에서 세로축은 시작 정점, 가로축은 도착 정점입니다.
  • 음수는 올 수 없습니다.
  • self loop 없습니다.

입출력 예시

const output1 = createMatrix([
	[0, 3, "directed"],
	[0, 2, "directed"],
	[1, 3, "directed"],
	[2, 1, "directed"],
]);

console.log(output1);
/**
 * [
 *  [0, 0, 1, 1],
 *  [0, 0, 0, 1],
 *  [0, 1, 0, 0],
 *  [0, 0, 0, 0]
 * ]
 */

const output2 = createMatrix([
	[0, 2, "directed"],
	[2, 4, "undirected"],
	[1, 3, "undirected"],
	[2, 1, "directed"],
]);

console.log(output2);
/**
 * [
 *  [0, 0, 1, 0, 0],
 *  [0, 0, 0, 1, 0],
 *  [0, 1, 0, 0, 1],
 *  [0, 1, 0, 0, 0],
 *  [0, 0, 1, 0, 0],
 * ]
 */

풀이

function createMatrix(edges){
	// 전부 0으로 채울 배열을 만들기 위해 최대 값을 구한다. (배열에서 Math.max, slice를 활용해 뽑아낼 것이다.
    let max = 0;
    for(let i = 0; i < edges.length; i++){
    	// 이렇게 하면 edges 숫자의 최대값을 뽑을 수 있다.
        let currentMax = Math.max(...edges[i].slice(0, 2));
        currentMax > max ? (max = currentMax) : null;
        // max에다가 최대값을 담아줄 수 있습니다.
    }

	// 우선 전부 0으로 채울 배열을 만들어 result에 잠시 담아준다.
	let result = new Array(max + 1).fill(0).map((el) => new Array(max + 1).fill(0));

	edges.forEach((edge) => {
    	const [row, col, location] = edge;
        if(location === "undirected"){
        	result[col][row] = 1;
        }
        result[row][col] = 1;
    });

    return result;
}

0으로 배열을 채우는 방법까지 갈 때도 많은 시간이 걸렸습니다.
생각보다 메소드를 자유롭게 사용할 수 없었기 때문에 메소드를 자유롭게 사용할 수 있는 레벨까지 끌어올리기 위해 노력중입니다.

map, Math.max, slice, forEach 등 이론적으로 어떤 느낌인지 알겠지만, 손에 익숙하지 않아서인지 쉽게 사용할 수 없었습니다.

profile
메일은 매일 확인하고 있습니다. 궁금하신 부분이나 틀린 부분에 대한 지적사항이 있으시다면 언제든 편하게 연락 부탁드려요 :)
post-custom-banner

0개의 댓글