그래프(DFS, BFS) 문제

 

 

Clone Grpah 

• 문제 링크 : https://leetcode.com/problems/clone-graph/description/

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

• 문제 링크 : https://leetcode.com/problems/course-schedule/description/

사전에 방문해야 하는 노드가 정해져 있는 경우 방향이 있는 연결 리스트를 이용해서 사이클 발생 여부를 조회하는 문제다. 

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

• 문제링크  : https://leetcode.com/problems/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 유사 문제 

• 문제 링크 : https://neetcode.io/problems/foreign-dictionary

NeetCode

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 유사 문제 

• 문제 링크 : https://neetcode.io/problems/valid-tree

NeetCode

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 유사 문제 

• 문제 링크 : https://neetcode.io/problems/count-connected-components

NeetCode

상단의 문제와 비슷한 문제로 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
    }
}