백준 1260번 - DFS와 BFS

Posted on | In , , | Comments:

코테 풀이들은 대부분 길어서 더보기 클릭을 하지 않으면 보이지 않도록 해당 문구를 추가합니다.

백준 1260: DFS와 BFS

문제 출처 : https://www.acmicpc.net/problem/1260
image

문제 설명

DFS와 BFS를 구현할 수 있는지 물어보는 직관적인 문제.
인풋을 받아서 적절한 graph 형태로 저장한 후, 이를 각각의 방식으로 순회하면서 출력하면 끝.
어떤 두 정점 사이에 여러 개의 간선이 있을 수 있음에 주의하자.
큐나 스택을 활용할 때는 from collections import deque를 사용한다.

문제 풀이

[1] DFS
: 스택이나 재귀함수로 구현할 수 있다. 아래와 같은 플로우로 구현한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
[Recursive하게 구현하기]
1. 시작점을 먼저 방문 처리 후 해당 노드 출력
2. 인접 노드를 탐색하는데,
3. 해당 노드를 방문한 적이 없다면,
4. 재귀적으로 해당 노드를 방문함.

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ') # 방문 처리한 노드를 출력

    for near_v in graph[v]: # 인접 노드에 대해서
        if not visited[near_v]: # 해당 노드를 방문한 적이 없다면,
            dfs(graph, near_v, visited) # 재귀적으로 방문함

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
[stack으로 구현하기]
1. stack을 만들고 시작점을 삽입
2. while문을 써서 stack이 빌때까지 반복
3. 방문할 노드를 pop()을 통해 뽑음
4. 해당 노드를 방문한 적이 없다면, 방문 처리하고
5. 인접 노드를 stack에 extend()한다.

def dfs(graph, v, visited):
    stack = deque([v]) # stack에 시작점을 삽입

    while stack: # stack이 빌 때까지 반복
        visiting_node = stack.pop() # stack에서 방문할 노드 선택

        if not visited[visiting_node]: # 해당 노드를 방문한 적이 없다면,
            visited[visiting_node] = True # 방문 처리
            print(visiting_node, end=' ') # 방문 완료한 노드 출력
            stack.extend(sorted(graph[visiting_node], reverse=True)) # 인접 노드를 stack에 넣는데 문제의 조건때문에 sort

[2] BFS
: 큐를 통해 구현할 수 있다. 아래와 같은 플로우로 구현한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[Queue를 통해 구현하기]
1. Queue를 만들고 시작점을 삽입 후
2. 해당 노드를 방문 처리함.
3. while문을 사용하여 큐가 빌때까지 반복하는데,
4. 큐에서 이미 방문한 노드를 뽑고, 해당 노드에 대해서 인접한 노드를 전부 방문하는데
5. 인접 노드를 방문한 적이 없다면,
6. 해당 인접 노드를 큐에 넣고 방문 처리한다. (핵심)

def bfs(graph, v, visited):
    queue = deque([v]) # queue에 시작점을 삽입후
    visited[v] = True # 해당 노드를 방문 처리

    while queue: # queue가 빌 때까지 반복
        visited_node = queue.popleft()
        print(visited_node, end=' ') # 방문 완료한 노드를 출력

        for near_v in graph[visited_node]: # 인접 노드에 대해서
            if not visited[near_v]: # 해당 노드를 방문한 적이 없다면
                queue.append(near_v) # 인접 노드를 queue에 넣고
                visited[near_v] = True # 해당 노드를 방문 처리

제출

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# main.py
if __name__ == "__main__":
    import sys; readline = sys.stdin.readline
    from collections import deque
    N, M, V = map(int, readline().split()) # 정점 갯수, 간선 갯수, 탐색 시작 정점 번호
    graph = [[] for _ in range(N+1)] # 0번 인덱스를 버리기 위해 1 추가
    for _ in range(M):
        v1, v2 = map(int, readline().split())
        graph[v1].append(v2)
        graph[v2].append(v1)

    # 정점 번호가 작은 것을 먼저 방문하기 위해 sort
    graph = [sorted(_list) for _list in graph]

    # DFS
    visited = [False for _ in range(N + 1)]
    dfs(graph, V, visited)
    print()

    # BFS
    visited = [False for _ in range(N + 1)]
    bfs(graph, V, visited)