문제노트_자료구조(stack/queue/graph)

stack

후입선출(LIFO)

웹 브라우저 방문기록 (뒤로 가기,현재 페이지, 앞으로 가기) : 두개의 stack(뒤, 앞 페이지)과 하나의 단일 변수 사용, push, pop등으로 주고 받음
역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력
후위 표기법 계산
수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

queue

선입선출(FIFO, First in first out)

주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용

우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
은행 업무
콜센터 고객 대기시간
프로세스 관리
너비 우선 탐색(BFS, Breadth-First Search) 구현
캐시(Cache) 구현

Graph

인접행렬

가장 빠른 경로를 찾고자 할 때 주로 사용

지하철 노선도, 네비게이션

const 도시들 = ['서울', '부산', '청주']; // 요소들은 정점
const 인접행렬 =
[[0,0,1],
 [1,0,1],
 [1,0,0]] 
------------------------------------------------
[[0][2],
 [1][0],
 [1][2], 
 [2][0]] // 간선 (ex- 인접행렬 [0][2] 지점에 1이 있다  )

const 경로 =
[['서울', '청주'],
 ['부산', '서울'],
 ['부산', '청주'],
 ['청주', '서울' ]]  //이것도 간선

인접행렬의 틀 생성:
받은 간선 배열(edges.length) 길이만큼 돌면서(for 등)
받은 간선들 목록 중 큰 숫자 구함 (ex) (Math.max(...edges[i])))
틀 만드는 간단 방법 :

new Array(max + 1).fill(0).map((row) => new Array(max + 1).fill(0));
new Array(도시들.length).fill(0).map((row) => new Array(도시들.length).fill(0));
// 만약 간선목록이 숫자로 주어지지 않았을경우(위)

받은 배열을 순회하며 만든 인접행렬 틀- 간선의 위치에 1을 넣어줌
양방향, 단방향

---

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

<조건>
각 간선은 3가지 정보를 담고 있습니다.

0번째: 간선의 시작 정점 (0 이상의 정수)
1번째: 간선의 도착 정점 (0 이상의 정수)
2번째: 방향성 ('undirected' 일시 무향, 'directed' 일시 방향)

<입력>
인자 1: edges
Number 타입의 방향/무향인 간선들의 목록이 담긴 배열

<출력>
Array 타입을 리턴해야 합니다.
2차원 배열의 인접 행렬

<주의사항>
정점 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차원 배열에서 세로축은 시작 정점, 가로축은 도착 정점입니다.

const matrix = [
	[0, 0, 0],
	[0, 0, 0],
	[0, 0, 0],
];

<입출력 예시>

let 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) {

	// 행렬의 크기를 구합니다.
	// max 변수를 0으로 할당하고, edges를 전부 순회해 제일 큰 숫자를 max에 할당합니다.
	// max보다 크지 않을 경우엔 바꾸지 않습니다.
	let max = 0;
	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));

  // 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;
	});

  // result를 반환합니다.
	return result;
}

인접리스트

메모리를 효율적으로 사용하고 싶을 때

빈 객체를 만들어 넣는 형식으로 접근 가능
정점 배열을 순회하며 만든 인접리스트 빈 객체에 키값으로 배열의 요소를, 값으로 빈 배열을 넣어줌
경로(간선)배열 순회하며 객체의 키를 각각 간선의 첫번째 요소로, 객체의 값(배열)에 간선의 두번째 요소를 push해준다.

const 도시들 = ['서울', '부산', '청주']; // 요소들은 정점
const 인접행렬 =
[[0,0,1],
 [1,0,1],
 [1,0,0]] 
------------------------------------------------
[[0][2],
 [1][0],
 [1][2], 
 [2][0]] // 간선 (ex- 인접행렬 [0][2] 지점에 1이 있다  )

const 경로 =
[['서울', '청주'],
 ['부산', '서울'],
 ['부산', '청주'],
 ['청주', '서울' ]]  //이것도 간선

const 인접리스트 = {};
for (let i = 0; i < 도시들.length; i++) {
  인접리스트[도시들[i]] = [];
}
for (let i = 0; i < 경로.length; i++) {
  인접리스트[경로[i][0]].push(경로[i][1]);
  // 인접리스트[경로[i][1]].push(경로[i][0]); 
  // -> 무향(양방향)일때 포함
}

console.log(인접리스트); 
{ '서울': [ '청주' ], '부산': [ '서울', '청주' ], '청주': [ '서울' ] }

DFS

깊이우선탐색 -

자신부터 자식까지 밑으로 쭉 다 탐색 후 다른 분기로 넘어감(자기 자신과 연결되었던 노드들 먼저 탐색)
모든 노드 방문할때 이용

구현 방법 2가지

• 재귀 사용(자기 자신 계속 호출)

• stack 이용 정점을 저장했다가 꺼내며 진행(자기자신과 연결되었던 노드)

  추가적으로 하나의 queue 더 이용하기도
  시작정점(노드)를 stack에 넣고
  visitQueue (queue) 선언 - (while문 로직 후 방문한 노드들을 넣을)

  while(needVisitStack이 빈배열이 아닐 때) - stack.pop한것을 노드에 할당시키며 방문했는지 검사-
  방문한queue에 노드 push/ 현재 탐색한 노드의 자식들을 방문해야할 stack에 추가(다음 순서로 pop을 할 것이므로 자식들부터 방문하게 됨)

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"],
};

// (graph, 시작 정점)
const dfs = (graph, startNode) => {
  let needVisitStack = []; // 탐색을 해야 할 노드들
  let visitedQueue = []; // 탐색을 마친 노드들

  needVisitStack.push(startNode);

  // 탐색을 해야 할 노드가 남아 있다면
  while (needVisitStack.length !== 0) {
    const node = needVisitStack.pop();
    if (!visitedQueue.includes(node)) {
      visitedQueue.push(node);
      needVisitStack = [...needVisitStack, ...graph[node]];
    }
  }

  return visitedQueue;
};

console.log(dfs(graph, "A"));

// ["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]

BFS

이전 노드와 연결된(루트로부터 시작 인접한) 노드들 먼저 탐색

가장 가까운 정점 탐색 - queue 사용

visited 등 으로 방문여부 표시 boolean 값 할당

now 등 현재 정점 조회할 변수 선언 할당

push, shift로 선입선출

주로 현재 탐색할 vertex를 queue에 담고
visited로 현재 vertex 방문여부 표시한 다음
while(queue.length > 0) 일 동안 now 변수에 queue.shift() 할당
for문으로 matrix의 해당 정점의 간선들 확인(해당정점의 길이를 돌아야한다)
조회한 곳에는 방문여부 true로 체크

function getDirections(matrix, from, to) {
  
   // queue를 간단하게 생성하고, 첫 시작점으로 from을 할당합니다.
 let queue = [from]
 let enqueue = (n) => queue.push(n)  
 let dequeue = (n) => queue.shift()

  // 방문했다는 것을 표시하기 위해 1차원 행렬을 생성합니다.
 const isVisited = new Array(matrix.length).fill(false)
  // 첫 정점 방문 여부를 표시합니다.
 isVisited[from] = true;
  // queue(방문할 곳)의 사이즈가 0이 될 때까지 반복합니다.
  while(queue.length >0){
    // queue에서 정점을 하나 빼서 now에 할당합니다.
   let now = dequeue();
    // 목적지인지 검사하고, 목적지라면 true를 반환합니다.
    if(now === to){ //-----------------------------------> 결국 여기까지 오기위한 큰 그림!!next가 now가 되고 to와 비교
      return true;
    }                                             
    // 해당 정점의 간선들을 확인합니다.
    for(let next=0; next<matrix.length; next++){
      // 만약, 간선이 있고 방문하지 않았다면
       if(matrix[now][next] === 1 && !isVisited[next]){
        // queue에 next를 넣습니다. (다음 정점으로 가기 위해)
        enqueue(next)
        // 해당 정점을 방문했다는 것을 표시합니다.
       isVisited[next] = true; 
       }
     }
  }
 return false;
  // 길이 없다면 false를 반환합니다.
 
}