[백준] 1260번 : DFS와 BFS 해설 및 풀이 (Python)

2025. 2. 14. 19:42·Study/코딩 테스트
반응형

 

백준 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개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

문제 유형

 

그래프 이론

그래프 탐색

너비 우선 탐색

깊이 우선 탐색

 


 

문제 풀이

 

풀이 방법 도출 과정

  1. 주어진 그래프를 DFS, BFS로 풀어야 합니다. DFS는 재귀를 사용할 것이며 BFS는 큐를 사용하여 문제를 해결하고자 합니다.
  2. 정점 번호가 작은 것부터 방문해야 하므로 각 정점의 인접 리스트를 정렬합니다.
  3. DFS 구현 방식
  • 현재 정점을 방문하고 출력합니다
  • 연결된 정점들을 방문합니다. 이를 재귀로 호출합니다.
  • 방문한 정점은 visited를 True로 방문 처리를 합니다.

 

4 BFS 구현 방식

  • 큐를 사용하여 탐색합니다.
  • 현재 정점을 큐에서 꺼내고 visited를 True로 방문 처리를 합니다.
  • 연결된 정점을 큐에 삽입합니다.

 

시간 복잡도

 

DFS : O(N+M)

BFS : O(N+M)

인접 리스트 정렬 : O(N log N)

 

따라서 총 시간 복잡도는 O(N log N + N + M) 입니다.

 


 

문제 풀이 코드

 

import sys
from collections import deque

# 입력 받기
input = sys.stdin.readline

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

# 인접 리스트 생성
adj = [[] for _ in range(N + 1)]

# 간선 정보 입력
for _ in range(M):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

# 번호가 작은 정점부터 방문하도록 정렬
for i in range(1, N + 1):
    adj[i].sort()

# DFS 구현 (재귀)
def dfs(V):
    visited[V] = True  # 현재 정점 방문 처리
    print(V, end=' ')  # 방문한 정점 출력
    for i in adj[V]:  # 연결된 정점들 탐색
        if not visited[i]:  # 방문하지 않은 경우 탐색 진행
            dfs(i)

# BFS 구현 (큐 사용)
def bfs(V):
    q = deque([V])  # 큐 초기화
    visited[V] = True  # 시작 정점 방문 처리
    while q:
        V = q.popleft()  # 큐에서 정점 꺼내기
        print(V, end=' ')  # 방문한 정점 출력
        for i in adj[V]:  # 연결된 정점들 탐색
            if not visited[i]:  # 방문하지 않은 경우
                q.append(i)  # 큐에 추가
                visited[i] = True  # 방문 처리

# 방문 기록 초기화
visited = [False] * (N + 1)

# DFS 수행
dfs(V)
print()  # 줄바꿈

# 방문 기록 초기화
visited = [False] * (N + 1)

# BFS 수행
bfs(V)
print()
반응형
저작자표시 비영리 변경금지

'Study > 코딩 테스트' 카테고리의 다른 글

[백준] 1003번 피보나치 함수 해설 및 풀이 (Python)  (0) 2025.02.17
[백준] 11723번 집합 해설 및 설명 (Python)  (0) 2025.02.15
[백준] 9461번 : 파도반 수열 해설 및 풀이 (Python)  (0) 2025.02.13
[백준] 11659번 : 구간 합 구하기 4 해설 및 풀이 (Python)  (0) 2025.02.12
[백준] 2631번 줄세우기 해설 및 풀이 (Python)  (0) 2025.02.11
'Study/코딩 테스트' 카테고리의 다른 글
  • [백준] 1003번 피보나치 함수 해설 및 풀이 (Python)
  • [백준] 11723번 집합 해설 및 설명 (Python)
  • [백준] 9461번 : 파도반 수열 해설 및 풀이 (Python)
  • [백준] 11659번 : 구간 합 구하기 4 해설 및 풀이 (Python)
Dev Chu
Dev Chu
  • Dev Chu
    Log_Double 7
    Dev Chu
  • 전체
    오늘
    어제
    • LOG LIST (199)
      • log Double 7 (2)
        • notice (1)
        • 회고록 (1)
      • Study (111)
        • 과제 (2)
        • 코딩 테스트 (105)
        • 대규모 시스템 설계 기초 (4)
      • CS (10)
        • 자료구조 & 알고리즘 (4)
        • Design Pattern (2)
        • TIL (4)
      • FrontEnd (26)
        • HTML & CSS (16)
        • JavaScript & jQuery (9)
        • React (1)
      • BackEnd (24)
        • Java (4)
        • Python (6)
        • Database (0)
        • Spring (6)
      • Infra & DevOps (3)
        • AWS (3)
        • Git (8)
      • Project (3)
        • repo_bis (2)
        • WhiteMonday (1)
      • ETC (20)
        • TIP (13)
        • Error (5)
        • SQLD (2)
  • 블로그 메뉴

    • 코딩 테스트
  • 링크

    • GitHub
  • 공지사항

    • Log Double 7
  • 인기 글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
Dev Chu
[백준] 1260번 : DFS와 BFS 해설 및 풀이 (Python)
상단으로

티스토리툴바