[백준] 1260번 DFS와 BFS (Python)

문제

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

코드

• 인접리스트 방식

# dfs bfs문제
# 인접행렬 방식과 인접리스트 방식 두개다 모두 익숙해지기

N,M,V = map(int, input().split())
node = {}
for i in range(N):
    node[i+1] = []

for i in range(M):
    x, y = map(int, input().split())
    node[x].append(y)
    node[y].append(x)

for i in range(1, N+1): # 정렬을 해주고 돌려줘야 값이 재대로 나온다 인접리스트라 그런가?
    node[i].sort()      # {1: [2, 3], 2: [5, 1], 3: [4, 1], 4: [5, 3], 5: [4, 2]} => {1: [2, 3], 2: [1, 5], 3: [1, 4], 4: [3, 5], 5: [2, 4]}



visited = []

# 스택으로 dfs를 구현할 경우 순서가 거꾸로 나옴...
# def dfs(node,V): # dfs 인접리스트로 풀면 역순?? 그렇게 나와서 안되는것 같다 인접행렬로 풀어보자
#     stack = [V]
#     visited = []
#     while stack:
#         current_node = stack.pop()
#         visited.append(current_node)
#         for i in node[current_node]:
#             if i not in visited and i not in stack:
#                 stack.append(i)
        
#     return visited

def dfs(node, start, visited):
    visited.append(start)
    for i in node[start]:
        if i not in visited:
            dfs(node, i, visited)
    return 


# def bfs(node,V):
#     queue = [V]
#     visited = []
#     while queue:
#         current_node = queue.pop(0)
#         visited.append(current_node)
#         for i in node[current_node]:
#             if i not in visited and i not in queue:
#                 queue.append(i)
#     return visited

def bfs(node,V): 
    queue = [V]
    visited = [V] # 시작노드를 추가해주고 시작한다.
    while queue:
        current_node = queue.pop(0)
        for i in node[current_node]:
            if i not in visited: # 이 코드가 조건문도 한개더 안넣어도 되고 위에 bfs보다 빠르다.
                queue.append(i)
                visited.append(i) # visited 노드에 추가해준다
    return visited

dfs(node, V, visited)
b_node = bfs(node, V)

for i in visited:
    print(i, end=" ")
print()
for i in b_node:
    print(i, end=" ")

 

• 인접행렬 방식

# dfs bfs  인접행렬로 풀어보기

n, m, v = map(int, input().split())
node = [[0] * (n+1) for _ in range(n+1)]


for i in range(m):
    line = list(map(int, input().split()))
    
    node[line[0]][line[1]] = 1
    node[line[1]][line[0]] = 1



def dfs (node, start, visited):
    visited.append(start)
    for i in range(1, n+1):
        if node[start][i] and i not in visited: # node[start][i] 가 1이어야한다.
            visited = dfs(node, i, visited)
    return visited

def bfs(node, start):
    q = [start]
    visited = [start]
    while q:
        current_node = q.pop(0)
        for i in range(1, n+1):
            if node[current_node][i] and i not in visited:
                q.append(i)
                visited.append(i)
    return visited


print(' '.join(map(str, dfs(node, v, []))))
print(' '.join(map(str, bfs(node, v))))

 

코드설명

 

인접리스트 1차시도

처음에 인접리스트 방식으로 dfs는 스택방식 bfs는 큐방식으로 구현을 해봤는데 dfs 스택방식으로 푸니까 순서가 거꾸로 나오는 현상이 일어났다..

 

인접리스트 2차시도

그래서 dfs를 재귀방식으로 바꿧는데도 예제 2번처럼 큰수가 먼저 들어오게되면 들어온순서로 인접리스트에 들어가게 되기 때문에 출력시 순서가 이상하게나온다. 그래서 인접리스트를 정렬을 해주고 수행시에는 정상 작동이 된다.

 

인접행렬

결국 이 문제에서 인접리스트로 풀게되면 생각해야 될게 많은 것 같아 인접행렬로도 수행해봤다.

인접행렬로 풀 경우에는 따로 정렬을 해주지 않아도 정상 출력이 된다.

 

그리고 join을 사용하면 리스트를 for문으로 출력안해줘도 str로 간편하게 출력이 가능하다.

 

 

느낀점은 dfs bfs를 풀때 인접리스트 보다는 인접행렬로 푸는게 나을 것 같다는 생각이 들었고 dfs를 구현할때는 스택보다는 재귀로 구현하는게 좋은 것 같다.