😥 백준 1260 : DFS와 BFS

1260: DFS와 BFS

DFS/BFS 개념을 공부하고 문제 풀기 시작했다~!

📌 Try 1

import sys

def dfs(graph, visit, start_node, N):
    print(start_node, end=' ')
    
    stack = []
    for i in range(1, N + 1):
        if graph[start_node][i]:
            graph[start_node][i] = 0
            graph[i][start_node] = 0
            
            stack.append(i)
    
    while stack:
        node = stack.pop(0)
        
        if node not in visit:
            visit.append(node)
            dfs(graph, visit, node, N)

def bfs(start_node):
    queue = [start_node]
    visit = []
    
    while queue:
        start_node = queue.pop(0)
        visit.append(start_node)
        
        print(start_node, end=' ')
    
        # append step
        for i in range(1, N + 1):
            if i not in visit and i not in queue:
                graph[start_node][i] = 0
                graph[i][start_node] = 0
                queue.append(i)
        
        print('queue =', queue, 'visit =', visit)
    

N, M, V = map(int, sys.stdin.readline().rstrip().split())

# Construct Graph
graph = [[0] * (N + 1) for i in range(N + 1)]
visit = []
for i in range(M):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    graph[x][y] = 1
    graph[y][x] = 1

dfs(graph, visit, V, N)

이 문제에 꽤 많은 시간을 소모했는데도 풀지 못했다.
이전에 정리한 DFS/BFS 글의 탐색 데이터와 형식이 달라 어떻게 접근해야 하는지 모르겠다.
아직 DFS/BFS 개념이 부족해서 응용이 안되는 것 같다. 😥

🎯 Solution

import sys

def dfs(start_node):
    print(start_node, end=' ')
    visit[start_node] = 1
    
    for i in range(1, N + 1):
        if graph[start_node][i] and visit[i] == 0:
            dfs(i)

def bfs(start_node):
    queue = [start_node]
    visit[start_node] = 0
    
    while queue:
        start_node = queue.pop(0)
        print(start_node, end=' ')
        
        for i in range(1, N + 1):
            if graph[start_node][i] and visit[i] == 1:
                queue.append(i)
                visit[i] = 0
    
# input
N, M, V = map(int, sys.stdin.readline().rstrip().split())

# Construct Graph
graph = [[0] * (N + 1) for i in range(N + 1)]
visit = [0 for i in range(N + 1)]

for i in range(M):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    graph[x][y] = 1
    graph[y][x] = 1

# output
dfs(V)
print()
bfs(V)

참고 블로그 코드를 참고해서, 거의 유사하다.
아직은 어렵다,,,

🎁 Reference

• 깨지고 부서져라 - 백준 1260번(python 파이썬)
  https://pacific-ocean.tistory.com/260