[백준_1260] DFS와BFS python

오늘 코테 캠프에서 배운 내용이였다.

복습하기에 안성맞춤인 문제였다.

 

중요 포인트를 정리해보자면,

• DFS와 BFS를 코테에서 사용할 때는 둘 중 자신있는 것을 사용하면 된다.
• n이 1000을 넘지 않는 경우에는 2차원 배열로 이를 구현하는 것이 좋으며, 넘을 경우에는 인접 리스트로 이를 구현하는 쪽이 메모리 측면에서 유리하다.
• DFS는 재귀를 이용해, BFS는 큐(Queue)를 이용하여 구현한다.
• 최단거리를 구할 때는 BFS와 step 배열을 사용한다.
• visited의 관리가 중요하다.
• BFS든 DFS든 먼저 초기 vertex를 호출해주고 시작하는것이 직관적이다. (실수할 가능성이 줄어든다)

# n, m, v 입력
n, m, v = map(int, input().split())

# starts, ends
starts, ends = [], []

# s, e 입력
for _ in range(m):
    s, e = map(int, input().split())
    
    # starts, ends에 담아줌
    starts.append(s)
    ends.append(e)

# grid
grid = [
    [0] * (n + 1)
    for _ in range(n + 1)
]

# grid 채우기
for s, e in zip(starts, ends):
    # 정방향
    grid[s][e] = 1
    # 역방향
    grid[e][s] = 1

# visited
visited = [
    0 for _ in range(n + 1)
]

# dfs
def dfs(vertex):
    for curr_v in range(1, n + 1):
        # 만약 현재 vertex와 curr_v가 연결되어있고,
        # 방문한 적이 없으면,
        if grid[vertex][curr_v] and not visited[curr_v]:
            # curr_v를 출력해주고,
            print(curr_v, end =' ')
            # 방문 표시
            visited[curr_v] = 1
            # curr_v와 연결된 곳을 탐색하는 함수 호출
            dfs(curr_v)

# 설계 1 (DFS)
# 방문 설정 해주고
visited[v] = 1
# 출력 해주고
print(v, end=' ')
# dfs 돌리기
dfs(v)

# deque 사용 준비
from collections import deque

# q (Queue)
q = deque()

# bfs()
def bfs():
    # 큐에 원소가 남아 있는 동안
    while q:
        
        # 큐에서 하나 꺼낸 값 == vertex(방금 출력한 정점)
        vertex = q.popleft()
        
        for curr_v in range(1, n + 1):
            # vertex와 curr_v가 연결되어 있고,
            # curr_v가 방문한 적 없는 정점일 경우,
            if grid[vertex][curr_v] and not visited[curr_v]:
                # curr_v 출력해주고
                print(curr_v, end=' ')
                # 방문 흔적 남기기
                visited[curr_v] = 1
                # q에 원소 추가
                q.append(curr_v)

# 설계 2 (BFS)
# 줄 띄우고
print()
# visited 초기화
visited = [
    0 for _ in range(n + 1)
]
# 방문 설정 해주고
visited[v] = 1
# 출력해주고
print(v, end=' ')
# 큐에 넣어주고
q.append(v)
# bfs 돌리기
bfs()