[백준] 그래프의 탐색 (DFS, BFS)

그래프의 탐색에는 깊이우선 탐색과, 너비우선 탐색 방법 두가지 방법이 존재한다.

각각을 구할 때, 인접행렬로 구하는 방식이 있고, 간선 리스트로 구하는 방식이 존재한다.

인접행렬은 이차원배열이기 때문에 O(N^2)의 시간이 걸리고, 간선리스트는 간선의 합만큼만 시간복잡도가 걸리기 때문에 O(V+E) 의 시간복잡도가 존재한다.

시간을 최소화 하고싶다면 간선리스트로 구현하자!

 

1260번. DFS와 BFS

https://www.acmicpc.net/problem/1260

def dfs(n,v):
    global arr,check
    check[v] = True
    print(v,end=' ')
    for i in range(1,n+1):
        if arr[v][i] == 1 and check[i] == False:
            dfs(n,i)


def bfs(n,v):
    global arr
    check = [False] * (n+1)
    q = []
    q.append(v)
    check[v] = True
    while len(q) != 0:
        x = q.pop(0)
        print(x,end=' ')
        for i in range(1,n+1):
            if arr[x][i] == 1 and check[i] == False:
                check[i] = True
                q.append(i)



n,m,v = list(map(int,input().split()))
arr = [[0] * (n+1) for _ in range(n+1)]
check = [False] * (n+1)
for _ in range(m):
    a,b = list(map(int,input().split()))
    arr[a][b] = 1
    arr[b][a] = 1
dfs(n,v)
print()
bfs(n,v)

간선리스트로도 한번 구현해보았다.

def dfs(n,v):
    global arr,check
    check[v] = True
    print(v,end=' ')
    for i in arr[v]:
        if check[i] == False:
            dfs(n,i)

def bfs(n,v):
    global arr
    check = [False] * (n+1)
    q = []
    q.append(v)
    check[v] = True
    while q:
        x = q.pop(0)
        print(x,end=' ')
        for i in arr[x]:
            if check[i] == False:
                check[i] = True
                q.append(i)



n,m,v = list(map(int,input().split()))
arr = [[] for _ in range(n+1)]
check = [False] * (n+1)
for _ in range(m):
    a,b = list(map(int,input().split()))
    arr[a].append(b)
    arr[b].append(a)
for i in range(n+1):
    arr[i].sort()
dfs(n,v)
print()
bfs(n,v)

간선리스트 vs 인접리스트

메모리, 시간에서 차이를 보였다. 경우의 수가 더 많다면 더 큰 차이를 보이지 않을까 생각한다. 메모리면에서도 2차원 배열을 다 사용하는 것과, 정확한 메모리 공간을 차지하는 것의 차이점이 있다는 것을 알 수 있었다.

 

11724번. 연결 요소의 개수

https://www.acmicpc.net/problem/11724

파이썬으로 아무리 해도 시간초과가 발생하는 문제. 덕분에 현타와서 몇일 알고리즘을 쉬었다. 

input().split() vs sys.stdin.readline().split() 으로 시간초과 여부가 갈리게 되는 것을 확인하였다.

import sys
sys.setrecursionlimit(10000)


def solution(start):
    global arr,check
    check[start] = True
    for i in arr[start]:
        if check[i] == False:
            solution(i)


n,m = map(int,sys.stdin.readline().split())
arr = [[] for _ in range(n+1)]
check = [False] * (n+1)
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())
    arr[a].append(b)
    arr[b].append(a)
for i in range(n):
    arr[i].sort()
answer = 0
for i in range(1,n+1):
    if check[i] == False:
        solution(i)
        answer += 1
print(answer)

1707번. 이분 그래프

https://www.acmicpc.net/problem/1707

import sys
sys.setrecursionlimit(10 ** 6)


def solution(start,color):
    global arr,check
    check[start] = color
    for i in arr[start]:
        if check[i] == 0:
            if solution(i,3-color) == False:
                return False
        elif check[i] == check[start]:
            return False
    return True


case = int(input())
for _ in range(case):
    n,m = map(int,sys.stdin.readline().split())
    arr = [[] for _ in range(n+1)]
    check = [0] * (n+1)
    for _ in range(m):
        a,b = map(int,sys.stdin.readline().split())
        arr[a].append(b)
        arr[b].append(a)
    for i in range(n):
        arr[i].sort()
    ans = True
    for i in range(1,n+1):
        if check[i] == 0:
            ans = solution(i,1)
            if ans == False:
                break
    print("YES" if ans else "NO")