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

 

문제

 

접근방법 및 코드

이번 문제는 내가 풀고자 했던 방식으로 해결이 안돼서 다른 분들의 예제를 참고해서 해결했다. 테스트 코드와 반례를 모두 돌려도 결과값이 동일하게 나오는데 제출하면 5%에서 틀렸다고 나와서 원인을 찾느라 시간이 많이 걸렸고, 가장 아쉬운건 그럼에도 불구하고 원인을 찾지 못했다는 것... 반례 모음집에 있는 테스트를 다 돌려봐도 못 찾아서 정말 답답했다. (혹시나 우연찮게 이 글을 보시는 분 중에 원인을 아시는 분이 계시다면 댓글 남겨주시면 정말 감사 드릴 것 같습니다..)

 

1260번 반례모음: https://www.acmicpc.net/board/view/24356

 

1. 내가한 풀이 방식 (실패)

- 간선은 양방향 -> 인접한 노드를 defaultdict을 사용하여 방향 그래프 구현

- 같은 레벨의 인접노드가 여러개일 경우 작은 값 부터 탐색 -> 우선순위 큐 (여기서 부터 꼬인 것 같기도..)

- dfs는 재귀함수로 bfs는 deque로 구현

import sys
from collections import defaultdict, deque
from heapq import heapify, heappop

read = sys.stdin.readline

def dfs(v):
    print(v, end=' ')
    dfs_visited.append(v)  # 방문한 노드 추가
    heap = graph[v][:]     # 해당 노드의 인접노드 중 작은 값부터 먼저 방문하도록 우선순위 큐 
    heapify(heap)
    while(heap):
        num = heappop(heap) # 인접 노드 중 작은 값 부터 visited에 포함여부 확인 후 탐색
        if num not in dfs_visited:
            dfs(num)

def bfs(v):
    que = deque([v]) 
    bfs_visited= [v]
    
    while(que):
        num = que.popleft()
        print(num, end=' ')
        heap = graph[num][:]
        heapify(heap)
        
        for i in heap:
            if i not in bfs_visited:
                que.append(i)
                bfs_visited.append(i)

n, m, v = map(int, read().split())

graph = defaultdict(list)

for i in range(m):
    key, value = map(int, read().split())
    graph[key].append(value)
    graph[value].append(key)

dfs_visited = []

dfs(v)
print()
bfs(v)

 

2. 다른 방식 (성공)

- 정점의 연결관계(간선)를 이차원 배열로 그래프 구현 (True or False)

- 탐색 depth가 깊어지는 조건
   : 간선의 연결관계가 True이고 visited에 포함되지 않은 노드를 값이 작은 순서대로 탐색 -> 2가지 방법 존재

   첫번째, 인접한 노드만 저장한 형태로 그래프 구현 시, 각 키 값에 대한 인접 노드 배열을 정렬

   두번째, 정점 간의 관계를 그래프로 구현 시, range(1, n+1)로 순서대로 조건문에 대입

- 여기서는 간선을 그래프로 구현했으므로 두번째 방법 사용
   (첫번째 방법 사용에 대한 좋은 예제 : https://ji-gwang.tistory.com/291 참고)

import sys 
from collections import deque

read = sys.stdin.readline

n, m , v = map(int, read().split())

graph = [[False] * (n+1) for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, read().split())
    graph[node1][node2] = True
    graph[node2][node1] = True

dfs_visited = [False] * (n+1)
bfs_visited = [False] * (n+1)

def dfs(v):
    dfs_visited[v] = True # 해당 노드 방문 처리
    print(v, end=" ")
    for i in range(1, n+1):
        if not dfs_visited[i] and graph[v][i]: # i를 방문하지 않았고, v와 i가 연결되어 있을 경우        
            dfs(i) # 해당 i와 연결된 인접노드에 대해서 깊이 탐색

def bfs(v):
    que = deque([v])
    bfs_visited[v] = True
    while que:
        node = que.popleft()
        print(node, end=" ")
        
        for i in range(1, n+1):
            if not bfs_visited[i] and graph[node][i]:
                bfs_visited[i] = True
                que.append(i)
    
    
dfs(v)
print()
bfs(v)

 

	제한	결과1 (input사용)	결과2 (stdin.readline사용)
메모리	128MB	39624KB	39576KB
시간	2초	516ms	160ms

* 확실히 stdin.readline()을 사용 시 속도가 훨씬 빠르다

 

느낀점

- dfs/bfs 문제에서는 대부분 리스트를 사용하여 그래프를 구현하고 defaultdict를 사용하는 경우는 드물다.

- 시간이 많이 걸렸지만, dfs/bfs 기본 개념을 익히기에 좋은 문제다.

 

 

 

문제링크: https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS