[백준] 1260번: DFS와 BFS

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

1260번: DFS와 BFS

 

이번 문제는 가장 기본적인 그래프 알고리즘 구현 문제이다. 양방향 처리에 대하여 풀려다가 우선 기본부터 다지자는 생각으로 이 문제를 선택하였다. dfs는 흔하게 사용하던 기법으로 기존과 같이 사용하여 재귀로 구현하였고 bfs를 큐형태로 만들어 구현하는 것이 새로웠다. 사용방법을 꼭 숙지하고 있어야겠다. 그리고 리스트를 문제에 맞게 큰 NxN개의 2차원 배열로 그래프로 표현할지 아니면 n개의 정점에 연결된 간선들을 하나씩 추가하여 2차원 배열로 표현할지 2가지 방식으로 만들어봤다.(dfs1 = NxN, dfs2 = Nx간선)

 

from collections import deque

def dfs(x,arr,cnt,visited):
    global n

    for i in range(1,n+1):
        if arr[x][i] == 1 and cnt[i] == 0:
            cnt[i] = 1
            visited.append(i)
            dfs(i,arr,cnt,visited)

    return visited

def dfs2(x,arr2,cnt2,visited):
    global n

    for i in range(0,len(arr2[x])):
        y = arr2[x][i]
        if cnt2[y] == 0:
            # print(y)
            cnt2[y] = 1
            visited.append(y)
            dfs2(y,arr2,cnt2,visited)

    return visited


def bfs(v):
    q = deque()
    q.append(v)
    cnt[v] = 1
    while q:
        v = q.popleft()
        print(v,end = " ")
        for i in range(1, n+1):
            if cnt[i] == 0 and arr[v][i] == 1:
                q.append(i)
                cnt[i] = 1

n,m,v = map(int,input().split())

arr = [[0 for j in range(n+1)]for i in range(n+1)]
cnt = [0 for i in range(n+1)]

arr2 = [[] for i in range(n+1)]
cnt2 = [0 for i in range(n+1)]

for i in range(m):
    x,y = map(int,input().split())
    arr[x][y] = 1
    arr[y][x] = 1

    arr2[x].append(y)
    arr2[y].append(x)


cnt[v] = 1
cnt2[v] = 1
vis = dfs(v,arr,cnt,[])
vis.insert(0,v)
print(' '.join(map(str,vis)))

# vis = dfs2(v,arr2,cnt2,[])
# vis.insert(0,v)
# print(vis)

cnt = [0 for i in range(n+1)]
bfs(v)