알고리즘
그래프(DFS, BFS) 문제
dodop
2025. 3. 11. 22:31
Clone Grpah
dfs를 이용해서 deepCopy를 수행하는 문제다.
/**
* Definition for a Node.
* class Node(var `val`: Int) {
* var neighbors: ArrayList<Node?> = ArrayList<Node?>()
* }
*/
class Solution {
fun cloneGraph(node: Node?): Node? {
if(node == null) {
return null
}
val map = mutableMapOf<Node, Node>()
return dfs(node, map)
}
private fun dfs(node: Node, map: MutableMap<Node, Node>): Node? {
if(map.containsKey(node)) {
return map[node]
}
val copy = Node(node.`val`)
map.put(node, copy)
for (n in node.neighbors) {
n?.let{copy.neighbors.add(dfs(it, map))}
}
return copy
}
}
Course Schedule
사전에 방문해야 하는 노드가 정해져 있는 경우 방향이 있는 연결 리스트를 이용해서 사이클 발생 여부를 조회하는 문제다.
DFS로 풀면 다음과 같이 풀 수 있다.
class Solution {
fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
// 1. DFS 활용 방안
val graph = HashMap<Int, MutableList<Int>>()
val visited = IntArray(numCourses) {0}
for((a, b) in prerequisites) {
// b에서 a를 갈 수 있음 (b를 들어야 a를 갈 수 있음)
graph.computeIfAbsent(b) {mutableListOf()}.add(a)
}
fun dfs(course: Int): Boolean {
if(visited[course] == 1) return false // 탐색 중인 노드 (해당 노드를 마주치게 되면 사이클 발생)
if(visited[course] == 2) return true // 이미 탐색 완료 됨 (이미 탐색 완료된 노드는 안전한 노드)
visited[course] = 1 // 방문 시작 표시
for(next in graph[course] ?: emptyList()){
// 사이클 발생시 예외 전달
if(dfs(next).not()) {
return false
}
}
visited[course] = 2 // 방문 완료 표시
return true
}
for(course in 0..numCourses-1) {
if(visited[course] == 0 && dfs(course).not()) {
return false
}
}
return true
}
}
Kahn's algorithm을 이용해서 BFS를 사용하면 다음과 같이 쓸 수 있다.
class Solution {
fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
// 2. BFS 활용 방안 (Kahn's algorithm)
val graph = HashMap<Int, MutableList<Int>>()
val indegree = IntArray(numCourses) {0}
for((a, b) in prerequisites) {
// b에서 a를 갈 수 있음 (b를 들어야 a를 갈 수 있음)
graph.computeIfAbsent(b) {mutableListOf()}.add(a)
// a에서 사전에 들어야 하는 갯수 증가
indegree[a] ++
}
val queue: Queue<Int> = LinkedList()
for(i in 0 until numCourses) {
// 사전에 들어야 하는 진입 차수가 0인 노드를 큐에 추가
if(indegree[i] == 0) queue.add(i)
}
var count = 0
while (queue.isNotEmpty()) {
val course = queue.poll()
count ++ // 코스 완료 표시
for (next in graph[course] ?: emptyList()) {
indegree[next]-- // 사전에 들어야 하는 갯수를 제거 시킴 (코스 완료)
if(indegree[next]==0) {
queue.add(next) // 선행 과목 모두 방문된 노드를 큐에 넣음
}
}
}
return count == numCourses
}
}
DFS를 이용한 방안과 BFS를 이용한 방안 모두 시간 복잡도 모두 O(V + E) (V : 노드 수, E: 간선 수) 이다.
Number of Islands
좌우상하 네방향으로 돌아다니며 섬의 갯수를 찾는 기본적인 탐색의 문제다.
먼저 DFS를 이용하여 문제를 풀었다.
시간 복잡도 = O(MxN)
공간 복잡도 = O(MxN)
여기서 dx, dy를 사용하지 않고 네방향으로 dfs()를 실행하게 하면 참조 연산이 줄어들 수 있다.
class Solution {
val dx = listOf(0, 0, 1, -1)
val dy = listOf(1, -1, 0, 0)
fun numIslands(grid: Array<CharArray>): Int {
val m = grid.size
val n = grid[0].size
var answer = 0
fun dfs(x: Int, y: Int) {
for (i in 0..3) {
val newX = x + dx[i]
val newY = y + dy[i]
if(0<=newX && newX<m && 0<= newY && newY<n && grid[newX][newY] == '1') {
grid[newX][newY] = '0'
dfs(newX, newY)
}
}
}
for(i in 0..m-1) {
for (j in 0..n-1) {
if(grid[i][j] == '1') {
answer++
grid[i][j] = '0'
dfs(i,j)
}
}
}
return answer
}
}
두번째로 BFS를 이용해서도 풀 수 있다.
시간복잡도 : O(MxN)
공간복잡도 : O(min(M, N))
val dx = listOf(0, 0, 1, -1)
val dy = listOf(1, -1, 0, 0)
fun numIslands(grid: Array<CharArray>): Int {
val m = grid.size
val n = grid[0].size
var answer = 0
fun bfs(x: Int, y: Int) {
val queue: Queue<Pair<Int, Int>> = LinkedList()
queue.add(x to y)
grid[x][y] = '0'
while(queue.isNotEmpty()) {
val (x, y) = queue.poll()
for (i in 0..3) {
val newX = x + dx[i]
val newY = y + dy[i]
if(0<=newX && newX<m && 0<= newY && newY<n && grid[newX][newY] == '1') {
grid[newX][newY] = '0'
queue.add(newX to newY)
}
}
}
}
for(i in 0..m-1) {
for (j in 0..n-1) {
if(grid[i][j] == '1') {
answer++
bfs(i,j)
}
}
}
return answer
}
UnionFind(Disjoint Set)을 이용해서도 풀 수 있다.
시간복잡도 : O(MxNXα(MxN))
공간복잡도: O(MxN)
=> 이건 다음 시간에...
Longest Consecutive Sequence
이건 그래프라기 보다, 값 비교로 풀었다.
class Solution {
fun longestConsecutive(nums: IntArray): Int {
if(nums.size == 0) {
return 0
}
val sortedNums = nums.sorted()
var temp = sortedNums[0]
var answer = 1
var length = 1
for (i in 1..nums.size-1) {
if(sortedNums[i] == temp) {
continue
}else if(temp+1 == sortedNums[i]) {
length += 1
answer = max(answer, length)
}else {
length = 1
}
temp = sortedNums[i]
}
return answer
}
}
Alien Dictionary 유사 문제
NeetCode
neetcode.io
BFS 위상 정렬 (Kahn's Algorithm)을 이용해서 우선순위를 이용한 그래프 탐색을 이용할 수 있다.
시간복잡도 : O(MxN)
공간복잡도 : O(V+E)
fun alienOrder(words: Array<String>): String {
val graph = HashMap<Char, MutableSet<Char>> // 문자 간의 관계 저장
val indegree = HashMap<Char, Int>() // 각 문자에 대한 진입 차수
// 모든 문자 노드를 그래프에 추가
for (word in words) {
for ( c in word) {
graph.putIfAbsent(c, mutableSetOf())
indegree.putIfAbsent(c, 0)
}
}
// 인접 리스트(그래프) 만들기
for ( i in 0 until words.size-1) {
val first = words[i]
val second = words[i+1]
val minLength = min(first.length, second.length)
if (first.length > second.length && first.startsWith(second)) {
return "" // 잘못된 사전 순서가 있는 경우
}
for (j in 0 until minLength) {
val c1 = first[j]
val c2 = second[j]
if(c1 != c2) { // 처음으로 다른 문자 등장
if(!graph[c1]!!.contains(c2)) {
graph[c1]!!.add(c2)
indegree[c2] = indegree[c2]!! + 1 // 진입 차수 증가
}
break // 순위가 정해졌기 떄문에 그 뒤는 볼 필요가 없음
}
}
}
// BFS를 위한 Queue (진입 차수가 0인 문자부터 처리)
val queue :Queue<Char> = LinkedList()
for((c, degree) in indegree) {
if(degree == 0 ) {
queue.add(c)
}
}
val order = StringBuilder()
while(queue.isNotEmpty()) {
val char = queue.poll()
order.append(char)
for(next in graph[char]!!) {
indgree[next] = indegree[next]!! -1
if(indegree[next] == 0) {
queue.add(next)
}
}
}
// 모든 문자를 방문 가능하면 응답 아니라면 불가 응답
return if (order.length == graph.size) order.toString() else ""
}
Graph Valid Tree 유사 문제
NeetCode
neetcode.io
Union-Find 방법으로 찾으면 다음과 같다.
시간복잡도 : O(N*α(N))
공간복잡도 : O(N)
class Solution {
fun validTree(n: Int, edges: Array<IntArray>): Boolean {
if (edges.size != n - 1) return false // ❗ 간선 수 조건 불충족
val parent = IntArray(n) { it } // 각 노드의 부모 초기화
// Find with path compression
fun find(x: Int): Int {
if (parent[x] != x) {
parent[x] = find(parent[x])
}
return parent[x]
}
// Union - returns false if cycle detected
fun union(x: Int, y: Int): Boolean {
val rootX = find(x)
val rootY = find(y)
if (rootX == rootY) return false // 🔥 사이클 발생
parent[rootY] = rootX
return true
}
for ((a, b) in edges) {
if (!union(a, b)) return false // 사이클이 있다면 false
}
return true // 연결 + 무사이클이면 트리
}
}
DFS로 찾으면 다음과 같다.
시간복잡도 : O(N)
공간복잡도 : O(N)
class Solution {
fun validTree(n: Int, edges: Array<IntArray>): Boolean {
if (edges.size != n - 1) return false // 트리 조건 위반
val graph = HashMap<Int, MutableList<Int>>()
for (i in 0 until n) {
graph[i] = mutableListOf()
}
for ((a, b) in edges) {
graph[a]!!.add(b)
graph[b]!!.add(a)
}
val visited = BooleanArray(n)
fun dfs(node: Int, parent: Int): Boolean {
if (visited[node]) return false // 🔥 사이클 발생
visited[node] = true
for (neighbor in graph[node]!!) {
if (neighbor == parent) continue // 부모는 무시
if (!dfs(neighbor, node)) return false
}
return true
}
if (!dfs(0, -1)) return false // DFS 중 사이클 발견
// 모든 노드가 방문되었는지 확인 (연결 여부 확인)
return visited.all { it }
}
}
BFS로도 풀 수 있다.
시간복잡도 : O(N+E)
공간복잡도 : O(N+E)
import java.util.*
class Solution {
fun validTree(n: Int, edges: Array<IntArray>): Boolean {
if (edges.size != n - 1) return false // 트리 조건 위반
// 인접 리스트로 그래프 구성
val graph = HashMap<Int, MutableList<Int>>()
for (i in 0 until n) {
graph[i] = mutableListOf()
}
for ((a, b) in edges) {
graph[a]!!.add(b)
graph[b]!!.add(a)
}
val visited = BooleanArray(n)
val queue: Queue<Pair<Int, Int>> = LinkedList() // Pair(currentNode, parentNode)
queue.add(0 to -1) // 시작 노드 0, 부모는 -1
while (queue.isNotEmpty()) {
val (node, parent) = queue.poll()
if (visited[node]) return false // 🔥 사이클 발생
visited[node] = true
for (neighbor in graph[node]!!) {
if (neighbor == parent) continue // 부모 노드는 무시
if (visited[neighbor]) return false // 🔥 사이클 발생
queue.add(neighbor to node)
}
}
// 모든 노드가 방문되었는지 확인 (연결성)
return visited.all { it }
}
}
Number of Connected Components in an Undirected Graph 유사 문제
NeetCode
neetcode.io
상단의 문제와 비슷한 문제로 DFS로 풀었다 .
class Solution {
fun countComponents(n: Int, edges: Array<IntArray>): Int {
val graph = Array(n) { mutableListOf<Int>() }
for ((a, b) in edges) {
graph[a].add(b)
graph[b].add(a)
}
val visited = BooleanArray(n)
var answer = 0
fun dfs(node: Int, parent: Int) {
if (visited[node]) return
visited[node] = true
for (neighbor in graph[node]) {
if (neighbor == parent) continue
dfs(neighbor, node)
}
}
for (i in 0 until n) {
if (!visited[i]) {
answer++
dfs(i, -1)
}
}
return answer
}
}