SK_MOUSE 개발일기

그래프의 가장 긴 깊이를 찾는 그래프 깊이 문제이다. 그래프 문제라고 해서 별 다른것이 아니라, BFS를 통해서 가장 깊이있는 경우를 마지막에 출력하면 그 깊이를 알 수 있다. check와 connect를 boolean으로 배열로 형성하여 방문했는지, 연결됐는지를 체크하는 용도로 사용한다. 이때 n이 아니라 n+1로 할당하는 이유는, 노드의 번호가 1부터 시작하기 때문이다. import java.util.LinkedList; import java.util.Queue; class Solution { public int solution(int n, int[][] edge) { boolean[] check = new boolean[n+1]; boolean[][] connect = new boolean[n+1]..

先요약 일반적인 그래프를 구성할때는 싸이클이 있는지를 확인한다 : findParent 메소드 이용 두개의 노드를 간선으로 잇는 작업은 unionParent 메소드를 이용한다. 신장트리는 싸이클이 없어야하며, 모든 노드가 연결되어있어야한다 : 크루스칼 알고리즘으로 만든다. 위상정렬은 싸이클이 없고 방향그래프(DAG)인 상황에, 방향성에 거스르지 않도록 순서대로 나열하는 것. 그래프의 기본적인 이론에 대하여 알아보겠다. 아래의 메소드는 그래프 문제를 풀때 구현해놓으면 좋은 메소드이다. 1. findParent(int x) 메소드 : 루트노드가 아니라면, 해당 루트 노드를 찾을때까지 재귀적으로 findParent메소드 재귀호출. ex) findParent(3번노드) -> 재귀 findParent(2번노드) -..