[백준/Python] #1260 : DFS와 BFS - DFS/BFS

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

1260번: DFS와 BFS

 

DFS/BFS 유형 문제 중에 가장 기초적인 문제이다.

이론을 이해하고 났다면 금방 풀 수 있는 문제지만 혹시나 알고리즘 공부가 아예 처음이거나,

문제에 적용하려고 하니 낯선 분들을 위해 베이스로 알면 좋은(?) 개념을 조금 정리해보았다.

 

• 덱(deque) 사용법 - 초기화

deque(iterable, [, maxlen])를 사용해 초기화

from collections import deque

# 비어있는 큐 만들기
deque = deque()

# 원소가 있는 큐 만들기
deque = deque([1, 2, 3])

# 큐 최대 길이 명시하기(원소를 maxlen보다 더 많이 넣으면 maxlen이 자동 갱신됨)
deque = deque(maxlen=5)

 

• 빈 리스트를 요소로 가지는 2차원 리스트를 정렬하면 빈 리스트는 가장 첫번째 인덱스에 온다

a = [[1, 2], [2, 3], [4, 2], [], [2, 1]]
a.sort()
print(a)
# [[], [1, 2], [2, 1], [2, 3], [4, 2]]

 

• [] for _ in range(n) 으로 matrix 만들기

a = [[0]*3 for _ in range(3)]
print(a)
# [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

 

 

---

from collections import deque

N, M, V = map(int, input().split())

graph = [[] for _ in range(N + 1)]
for i in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    graph[x].sort() # 정점 번호가 작은 것부터 방문하므로 정렬 필요
    graph[y].sort()

visited1 = [False] * (N + 1)
visited2 = [False] * (N + 1)

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

def BFS(graph, v, visited):
    queue = deque([v])
    visited[v] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

DFS(graph, V, visited1)
print()
BFS(graph, V, visited2)

 

 

풀이는 이러하다.