그래프란
정점(vertex/node)과 간선(edge)으로 이루어진 자료구조로 원소 사이 연결관계 표현 시 유용하다.
차수(degree) : 각 정점에 대해 간선으로 이어진 정점의 수
그래프 표현
리스트 혹은 행렬로 표현이 가능하다
| 인접 행렬 | 인접 리스트 | |
| 공간복잡도 | O(V^) | O(V+E) |
| 정점 u,v간 연결 관계 확인하는 시간 복잡도 | O(1) | O(min(deg(u),deg(v)) |
| 정점 v에 연결되어 있는 모든 정점 확인하는 시간 복잡도 | O(V) | O(deg(V)) |
| 효율적인 상황 | -두 점의 연결 여부를 자주 확인하는 경우 -간선이 정점^에 가까울 경우 |
- 특정 정점에 연결된 모든 정점을 자주 확인하는 경우 - 간선이 정점^보다 훨씬 작을 경우 |
BFS 로 모든 노드 방문하는 방법
1. 시작하는 정점을 큐에 넣고 방문 표시
2. 큐에서 정점을 꺼내에 그 정점과 연결된 모든 정점에 대해 3 진행
3. 처음 방문하는 정점일 경우 큐에 넣고 방문 표시
4. 큐가 빌 때까지 2 반복
-> 모든 정점이 큐에 최대 1번씩 들어가기 때문에 인접 리스트 이용 시 O(V+E), 인접 행렬 이용시 O(V^) 시간 복잡도
모든 간선의 길이가 같을 경우 두 지점 사이 거리 구할 때 BFS 이용 가능
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
var st = StringTokenizer(readLine())
val n = st.nextToken().toInt() // 정점
val m = st.nextToken().toInt() // 간선
val adj = Array(n+1) { IntArray(n+1) }
// make a graph
repeat(m) {
st = StringTokenizer(readLine())
val u = st.nextToken().toInt()
val v = st.nextToken().toInt()
adj[u][v] = 1
adj[v][u] = 1
}
// 노드 방문 탐색
var answer = 0
val visited = BooleanArray(n+1) { false }
val q = ArrayDeque<Int>()
for (i in 1..n) {
if (visited[i]) continue
answer++
q.add(i)
visited[i] = true
while (q.isNotEmpty()) {
val cur = q.remove()
for (j in 1..n) {
if (adj[cur][j] == 0 || visited[j]) continue
q.add(j)
visited[j] = true
}
}
}
print("$answer")
}
그래프를 dfs와 bfs로 탐색한 결과를 출력하기
import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.*
private var n = 0 // 정점의 수
private var m = 0 // 간선의 수
private var v = 0 // 탐색을 시작할 정점의 번호
private lateinit var adj: MutableList<MutableList<Int>>
private val bw = BufferedWriter(OutputStreamWriter(System.out))
private lateinit var visited: BooleanArray
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
var st = StringTokenizer(readLine())
n = st.nextToken().toInt()
m = st.nextToken().toInt()
v = st.nextToken().toInt()
adj = MutableList(n + 1) { mutableListOf() }
visited = BooleanArray(n+1) { false }
repeat(m) {
st = StringTokenizer(readLine())
val u = st.nextToken().toInt()
val v = st.nextToken().toInt()
adj[u].add(v)
adj[v].add(u)
}
// 정렬 : 작은 번호부터 방문하기 위함
for (i in 1..n) {
adj[i].sort()
}
dfs(v)
bw.write("\n")
visited = BooleanArray(n+1) { false }
bfs()
bw.close()
}
// 재귀 dfs
private fun dfs(cur: Int) {
visited[cur] = true
bw.write("$cur ")
for (next in adj[cur]) {
if (visited[next]) continue
dfs(next)
}
}
private fun bfs() {
val q = ArrayDeque<Int>()
// bfs start from v
q.add(v)
visited[v] = true
while (q.isNotEmpty()) {
val cur = q.remove()
bw.write("$cur ")
for (next in adj[cur]) {
if (visited[next]) continue
q.add(next)
visited[next] = true
}
}
}1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수 출력하기
bfs 탐색하며 1번 컴퓨터에 연결된 컴퓨터의 수를 센다
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val numberOfComputers = readLine().toInt()
var edges = readLine().toInt()
// 1. 컴퓨터 연결
var st: StringTokenizer
val adj = MutableList(numberOfComputers+1) { mutableListOf<Int>() }
while (edges-- != 0) {
st = StringTokenizer(readLine())
val computer1 = st.nextToken().toInt()
val computer2 = st.nextToken().toInt()
adj[computer1].add(computer2)
adj[computer2].add(computer1)
}
// 2. 바이러스 컴퓨터 숫자 세기
var answer = 0
val q = ArrayDeque<Int>()
val vis = BooleanArray(numberOfComputers+1) { false }
q.add(1)
vis[1] = true
while (q.isNotEmpty()) {
val cur = q.remove()
answer++
for (next in adj[cur]) {
if (vis[next]) continue
q.add(next)
vis[next] = true
}
}
if (answer == 0) print("0")
else print("${answer-1}")
}
상근이의 결혼식에 초대하는 동기의 수 구하기 (자신의 친구, 친구의 친구)
bfs 탐색으로 노드 간 거리 이용(노드간 거리가 2보다 크면 남이다)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt() // 동기 수
var m = readLine().toInt() // 리스트 길이
val adj = MutableList(n+1) { mutableListOf<Int>() }
var st: StringTokenizer
while (m-- != 0) {
st = StringTokenizer(readLine())
val a = st.nextToken().toInt()
val b = st.nextToken().toInt()
adj[a].add(b)
adj[b].add(a)
}
var answer = 0
val q = ArrayDeque<Int>()
val vis = IntArray(n+1) { -1 }
q.add(1)
vis[1] = 0
while (q.isNotEmpty()) {
val cur = q.remove()
answer++
for (next in adj[cur]) {
if (vis[next] != -1 || vis[cur] + 1 > 2) continue
q.add(next)
vis[next] = vis[cur] + 1
}
}
if (answer == 0) print("0")
else print("${answer-1}")
}
가중치가 없는 방향 그래프에서 모든 정점에 대해, i->j로 가는 경로가 있는지 없는지 구하기
-> 각 노드에 대하여 bfs 탐색
(플로이드 와샬 알고리즘을 활용해도 풀 수 있음)
import java.io.*
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val adj = Array(n) { IntArray(n) { -1 } }
var st: StringTokenizer
repeat(n) { i ->
st = StringTokenizer(readLine())
repeat(n) { j ->
adj[i][j] = st.nextToken().toInt()
}
}
for (i in 0 until n) {
val q = ArrayDeque<Int>()
val vis = BooleanArray(n) { false }
q.add(i)
// bfs
while (q.isNotEmpty()) {
val cur = q.remove()
for (j in 0 until n) {
if (adj[cur][j] == 0 || vis[j]) continue
q.add(j)
vis[j] = true
adj[i][j] = 1
}
}
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
repeat(n) { i ->
repeat(n) { j ->
bw.write("${adj[i][j]} ")
}
bw.write("\n")
}
bw.close()
}
BFS 거리구하기
-> 최종 탐색 거리가 작은 사람이 회장 후보
import java.io.*
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
val adj = MutableList(n+1) { mutableListOf<Int>() }
var st: StringTokenizer
while (true) {
st = StringTokenizer(readLine())
val i = st.nextToken().toInt()
if (i == -1) break
val j = st.nextToken().toInt()
adj[i].add(j)
adj[j].add(i)
}
val people = IntArray(n+1)
var min = 100
for (i in 1..n) {
val q = ArrayDeque<Int>()
val vis = IntArray(n+1) { -1 }
var score = 0
q.add(i)
vis[i] = 0
while (q.isNotEmpty()) {
val cur = q.remove()
for (next in adj[cur]) {
if (vis[next] != -1) continue
q.add(next)
vis[next] = vis[cur] + 1
score = vis[next]
}
}
people[i] = score
if (min >= score)
min = score
}
val candidate = mutableListOf<Int>()
for (i in people.indices) {
if (min == people[i])
candidate.add(i)
}
val bw = BufferedWriter(OutputStreamWriter(System.out))
bw.write("$min ${candidate.size}\n")
repeat(candidate.size) { it ->
bw.write("${candidate[it]} ")
}
bw.close()
}
참고