[Python, 백준/1260번] DFS와 BFS

---

☑️ [Python, 백준/1260번] DFS와 BFS

1️⃣ 문제

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

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

2️⃣ 접근

인접 행렬 혹은 인접 리스트를 만들어서 간단하게 풀 수 있는 문제다. 입력 값이 [노드A, 노드B]를 쌍(Pair)으로 묶어서 준다. 요 Data만 가공해서 인접 행렬이나 인접 리스트로 만들면 되는데.. 이전에 풀었던 문제와 같이 find_index 함수를 만들어서 풀어보려고 했다. 비효율적이긴 하겠지만 재밌으니까.

 

근데 결과만 말하면 실패했다.

def find_index(index: int) -> int:
    for i in range(edge_count):
        if edge_data[i][0] == index and visit[edge_data[i][1]] == False:
            return edge_data[i][1]
        elif edge_data[i][1] == index and visit[edge_data[i][0]] == False:
            return edge_data[i][0]
    return -1

 

위 코드가 find_index 함수인데 조금 더럽지만..^^ 매개변수로 Index를 추가하면 Pair인 Node Index를 반환한다. 예제 1, 2, 3번은 쉽게 정답으로 나왔지만 예제에 나온 Case와 다른 종류의 테스트에서는 실패했다. 내가 실패한 반례는 다음과 같다.

5 3 1
1 5
3 5
5 2
[1, 5, 2, 3]
[1, 5, 2, 3]

 

저 형태에서는 3번 Node와 5번 Node는 이어져있고 2번 Node와 5번 Node도 이어져있다. [3, 5], [2, 5] 형태인데 내가 한 방법에서는 List의 0번째 원소를 기준으로 Sort 해주기 때문에 식별할 수 없었다. 만약에 이 방법에서 해결하고자 한다면 2개의 Array를 만들어서 더 낮은 수를 비교해주는 방식이나 Quick Sort를 사용해서 Pivot 이상의 값은 1번째 원소의 위치로 이동시키는 방법도 있겠지만.. 너무 비효율적이다.

 

비효율 + 비효율 = 최고의 비효율을 만드는 것 보다 인접 행렬을 만들어서 해결했다. 인접 행렬을 만드는 방법은 몰라서 인터넷에서 검색해서 찾아봤다. 확실히 이렇게 행렬로 접근하는게 숫자가 작은 Node부터 큰 Node까지 순차적으로 탐색하기 때문에 Sort를 신경쓰지 않을 수 있어서 좋다.

3️⃣ 코드

import sys
sys.stdin = open('input.txt', 'r')
from collections import deque

vertex_count, edge_count, start_node = map(int, input().split())
visit = [False] * (vertex_count + 1)

graph = [[0]*(vertex_count+1) for _ in range(vertex_count+1)]
for i in range (edge_count):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1
    
def dfs(s_node):
    visit[s_node] = True
    print(s_node, end = ' ')
    for i in range(1, vertex_count + 1):
        if graph[s_node][i] == 1 and not visit[i]:
            dfs(i)

def bfs(s_node):
    q = deque([s_node])
    visit[s_node] = True
    
    while len(q) > 0:
        s = q.popleft()
        print(s, end = ' ')
        for i in range(1, vertex_count + 1):
            if graph[s][i] == 1 and not visit[i]:
                visit[i] = True
                q.append(i)
        
dfs(start_node)
visit = [False] * (vertex_count + 1)
print()
bfs(start_node)

# def dfs(s_node):
#     visit[s_node] = True
#     print(s_node, end = ' ')
    
#     c_node = 0
#     while c_node != -1:
#         c_node = find_index(s_node)
#         if visit[c_node] == False and c_node != -1:
#             dfs(c_node)

# def bfs(s_node):
#     q = deque([s_node])
#     visit[s_node] = True
#     c_node = 0
#     while len(q) > 0:
#         s = q.popleft()
#         print(s, end = ' ')
        
#         c_node = find_index(s)
#         while c_node != -1:
#             c_node = find_index(s)
#             if visit[c_node] == False and c_node != -1 :
#                 visit[c_node] = True
#                 q.append(c_node)
            
# # A 기준으로 정렬과
# # B 기준으로 정렬을 만든다.
# # A 와 B 중 더 낮은 수 Return.
# def find_index(index: int) -> int:
#     for i in range(edge_count):
#         if edge_data[i][0] == index and visit[edge_data[i][1]] == False:
#             return edge_data[i][1]
#         elif edge_data[i][1] == index and visit[edge_data[i][0]] == False:
#             return edge_data[i][0]
#     return -1

# dfs(start_node)
# visit = [False] * (vertex_count + 1)
# print()
# bfs(start_node)

 

아래 주석은 실패한 코드지만... 5시간? 정도의 시간을 쏟았기 때문에 차마 지우질 못했다...