[백준] 1260. DFS와 BFS

문제 바로가기

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

 

💡 문제 요약

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

• 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.

• 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.

• 입력으로 주어지는 간선은 양방향이다.

ex)

입력	출력
4 5 1	1 2 4 3
1 2	1 2 3 4
1 3
1 4
2 4
3 4
5 5 3	3 1 2 5 4
5 4	3 1 4 2 5
5 2
1 2
3 4
3 1

 

💡 알고리즘 설계

• 코드에 주석으로 설명

💡 내 코드

import sys
sys.setrecursionlimit(10000)    # 재귀함수의 최대 깊이를 설정
from collections import deque

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

    for neighbor in graph[V]:   # 현재 노드인 V와 연결된 노드들 중에서
        if not visited[neighbor]:   # 방문한 적 없는 노드를
            dfs(graph, neighbor, visited)   # 방문한다.

def bfs(graph, V, visited):
    visited[V] = True   # 현재 노드 V를 방문 처리
    que = deque([V])    # 현재 노드를 큐에 넣어준다.

    while que:  # 큐가 빌 때 까지 반복
        V = que.popleft()   # 큐의 첫번째 원소를 꺼낸다.
        print(V, end=' ')   # 해당 원소가 현재 노드가 된다.
        
        for neighbor in graph[V]:   # 현재 노드 V와 연결된 노드 중
            if not visited[neighbor]:   # 아직 방문하지 않은 노드를 
                que.append(neighbor)    # 큐에 삽입한다.
                visited[neighbor] = True    # 아직 방문하지 않은 노드들을 큐에 중복으로 넣지 않기 위해 방문처리 한다.

if __name__ == '__main__':
    # N:노드 갯수, M:간선 갯수, V:탐색을 시작할 정점의 번호
    N, M, V = map(int, sys.stdin.readline().split())

    # (N+1) X (N+1)의 빈 배열을 만들어준다. 1 ~ N까지만 사용
    graph = [[] * (N+1) for _ in range(N+1)]

    # 서로 연결된 노드들(인접한 노드들)을 입력하여 그래프 생성
    for _ in range(M):
        a, b = map(int,sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)
        graph[a].sort()
        graph[b].sort()

    print(graph)

    # 방문여부 체크 리스트
    visited = [False] * (N+1)
    dfs(graph, V, visited)

		print()
		
    visited = [False] * (N+1)
    bfs(graph, V, visited)

 

💡 추가 설명

ex)

입력	출력
4 5 1	1 2 4 3
1 2	1 2 3 4
1 3
1 4
2 4
3 4

해당 예시의 그래프를 그려보면 다음과 같다.

• 코드에 있는 graph 리스트: [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]
  • 1번 노드에 연결된 노드: 2, 3, 4
  • 2번 노드에 연결된 노드: 1, 4
  • 3번 노드에 연결된 노드: 1, 4
  • 4번 노드에 연결된 노드: 1, 2, 3

• bfs의 que의 변화:
  • while문 1: deque([1])
  • while문 2: deque([2, 3, 4])
  • while문 3: deque([3, 4])
  • while문 4: deque([4])

 

💡 느낀점

• 기본적인 dfs, bfs 구현하는 것 조차 아직 서툴다.. 얼른 구조를 익히자.