[백준] 1260번 - DFS와 BFS(파이썬)

 

 

백준 1260번 DFS와 BFS

 

 

DFS와 BFS를 사용하여 정렬한 값을 출력하는 문제이다.

 

 

💡 문제 해결 아이디어

 

정답 비율이 낮아 재밌어보여 풀어보았는데 그냥 단순히 DFS와 BFS 알고리즘을 통해 해결할 수 있는 문제였다.

 

아마 낮은 정답률의 원인이 정점 번호가 작은 것을 먼저 방문하는 것 때문인 거 같다.

 

방향이 주어지지 않았기 때문에 노드가 서로 바라보도록 연결하면 되겠다고 생각하여 연결되는 두 노드(node1, node2)를 입력받으면 그래프의 node1 위치에 node2를 추가하고 node2 위치에 node1을 추가하여 서로 연결시켰다.

 

여기서 중요한 점은 graph에 등록하고 등록된 그래프를 오름차순 정렬 시켜주는 코드이다.

 

정렬은 list의 기본 메서드인 sort()를 통하여 해결하였다.

 

그래프 전체를 정렬하면 안되고 노드를 입력받은 부분만 정렬해주어야한다.

 

 

정렬하는 코드

graph[node1].sort()

graph[node2].sort()

 

 

코드

# 정점의 갯수 N / 간선의 갯수 M / 시작점 V
from collections import deque


def dfs(v, visited):
    print(v, end=' ')
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            visited[i] = True
            dfs(i, visited)


def bfs(start):
    visited = [False] * (n+1)
    queue = deque([start])
    visited[start] = True
    print(start, end=' ')
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                print(i, end=' ')
                queue.append(i)


n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)
    graph[node1].sort()
    graph[node2].sort()

visited = [False] * (n+1)
dfs(v, visited)
print()
bfs(v)