DFS

🔒 Problem 🔑 BFS approach Create two queue with bread-first search to all nodes. To handle null case, if null, don't add left & right nodes to queue BFS Code (Kotlin) import java.util.LinkedList import java.util.Queue class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null } class SameTree { fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean { // 1. queue 2개 초기화 및..

🔒 문제 Detect cycle in an undirected graph | Practice | GeeksforGeeks practice.geeksforgeeks.org 💭 생각의 흐름 일단 문제 자체에서 DFS를 사용하여 사이클을 탐색하라고 했다. 정석적인 DFS recursive function을 작성하고 사이클 생기는 시점에 true만 리턴하면 된다고 생각했다. Q. 사이클이 생기는 시점이 언제인가? A. BackEdge (부모노드 이외의 노드에 연결되는 선이 발견되는 시점) 따라서 visited (방문 기록) 배열을 두고 visited 상에 방문된 상태로 기록되있으면서 parent 노드가 아닌 노드로 연결되있을 경우 바로 true (사이클이 존재)를 리턴하도록 한다. ⚠️ 실수 아래 그림 처럼 그..

개요 모든 경우의 수를 탐색하는 Brute Force 알고리즘으로 조건이 존재할 때 사용한다. State-Space Tree 라고도 한다. 기본적으로 DFS 를 사용하며 조건에 부합하지 않는 branch에 대해 Pruning (가지치기)를 하여 불필요한 경우의 수를 따지지 않는다. Branch and Bound BFS 베이스로 (depth == level) 기준으로 자리를 구분한다. 관련 문제 www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/ Write a program to print all permutations of a given string - GeeksforGeeks A Computer Scie..

문제 아이디어 총 단지수 == Graph 갯수 단지 내 집의 수 == Graph 내 노드(Vertex) 수 출력으로 요구하는 값만 봐고 DFS & BFS가 떠올랐다. 총 단지수 => main 에서 DFS 호출 수 단지 내 집의 수 => 한 DFS 내 재귀 호출 수 그래프 연결작업 => 행렬 전체를 돌며 '오른쪽, 아래'로 연결된 [행번호,열번호] 양방향 연결 리스트 추가 약간 헷갈렸던 것이 단지 내 집의 수 (DFS내 재귀 호출 수 카운트) 하는 부분이었다. DFS 코드 // main에서 마지막 argument로 DFS 호출 횟수를 keep하는 변수를 넘겨서 fun dfs (rowIndex: Int, colIndex: Int, callCount: Int) { //start vertex 는 0,0 가정 상..

문제 아이디어 정점, 간선 단어를 보자마자 '그래프'? 연결 요소 == 이어진 그래프를 의미한다. BFS or DFS를 떠올린다. 나는 BFS를 선택했다. 모든 노드(정점) 목록을 원소로 갖는 집합(Set)을 두고 한 번의 BFS마다 생기는 그래프를 전체 집합에서 제외시키는 방식으로 풀이했다. (전체 집합이 공집합이 될 때까지 Loop) 실수 undirected graph (무방향 그래프) 인것을 확인하지 않고 단방향 연결 리스트로만 체크하다가 틀려버렸다. 구현 [Graph.kt] import java.util.* import kotlin.collections.ArrayList class Graph(private val vertexNumber: Int) { val vertexSet : Set = (1 ...

1. 개념 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환..