[Python] 백준 1260

 

단순히 DFS와 BFS를 구현하여 출력하면 된다.

 

그래프 구현

graph = [[0]*(N+1) for x in range(N+1)]

for i in range(M):
    temp = list(map(int, input().split(' ')))
    graph[temp[0]][temp[1]] = 1
    graph[temp[1]][temp[0]] = 1

그래프는 2차원 배열로 구현하였다.

두 정점을 연결하는 간선을 1로 바꿔준다. 양방향 그래프이기 때문에 두 번 바꿔주어야 한다.

예를들어 간선이 1과 2를 연결한다면, 2차원 배열은 다음과 같다.

 

 

DFS 구현

탐색을 시작할 정점을 파라미터로 받아 dfs를 수행하는 함수이며, recursive로 구현하였다.

graph에서 연결된 정점을 리스트로 만들고, 리스트에 해당하는 정점 중 방문하지 않은 정점으로 dfs를 수행한다.

def DFS(v , visit):
    visit.append(v)
    stack = [v]
    while stack :
        temp = stack.pop()
        for i in list(filter(lambda x : graph[temp][x] == 1, range(len(graph[0])))) :
            if i not in visit :
                visit = DFS(i, visit)
    return visit

 

 

BFS 구현

탐색을 시작할 정점을 파라미터로 받아 bfs를 수행하는 함수이다.

DFS 함수와 구현방식은 비슷하지만 recursive를 사용하지 않았다.

def BFS(v):
    queue = [v]
    visit = [v]
    while queue :
        temp = queue.pop(0)
        for i in list(filter(lambda x : graph[temp][x] == 1, range(len(graph[0])))) :
            if i not in visit :
                visit.append(i)
                queue.append(i)
    return visit

 

전체코드

N, M, V = list(map(int, input().split(' ')))

graph = [[0]*(N+1) for x in range(N+1)]

for i in range(M):
    temp = list(map(int, input().split(' ')))
    graph[temp[0]][temp[1]] = 1
    graph[temp[1]][temp[0]] = 1

def DFS(v , visit):
    visit.append(v)
    stack = [v]
    while stack :
        temp = stack.pop()
        for i in list(filter(lambda x : graph[temp][x] == 1, range(len(graph[0])))) :
            if i not in visit :
                visit = DFS(i, visit)
    return visit

def BFS(v):
    queue = [v]
    visit = [v]
    while queue :
        temp = queue.pop(0)
        for i in list(filter(lambda x : graph[temp][x] == 1, range(len(graph[0])))) :
            if i not in visit :
                visit.append(i)
                queue.append(i)
    return visit

for i in DFS(V, []):
    print(i, end = ' ')
print()
for i in BFS(V):
    print(i, end = ' ')

 

 

한 번 왜틀렸징,,