[파이썬/Python] 백준 1260번: DFS와 BFS

숨·2024년 7월 16일

코테

알고리즘 문제 풀이

목록 보기

33/105

📌 문제 : 백준 1260번

📌 문제 탐색하기

N : 정점의 수 (1 ≤ N ≤ 1,000)
M : 간선의 수 (1 ≤ M ≤ 10,000)
V : 탐색 시작 정점 번호 (1 ≤ V ≤ N)

✅ 입력 조건
1. N,M, V 공백으로 구분해 입력
2. M번 반복해 연결 정보 입력
✅ 출력 조건
1. DFS를 통해 V부터 방문된 점 출력
2. BFS를 통해 V부터 방문된 점 출력

DFS, BFS 순서로 수행하며 방문한 점들을 차례로 출력하는 문제이다.

차례대로 연결하며 방문 순서만 출력해주면 되기 때문에 인접 리스트를 활용해 그래프를 만들어준다.

N개의 정점, M개의 정점간 관계인 간선 정보를 입력받아 저장하고,
방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 하므로 입력받아 저장한 그래프 연결 정보를 오름차순 정렬해준다.

DFS는 방문한 정점에 방문 처리를 해주면서 그와 연결된 정점를 재귀적으로 탐색하는 방식으로 구현한다.
BFS는 queue를 활용하여 방문 처리해주면서 가까운 노트부터 탐색하도록 구현한다.

가능한 시간복잡도

그래프 저장 → $O(M)$
그래프 정렬 → $O(MlogM)$
DFS → $O(N + M)$
BFS → $O(N + M)$

최종 시간복잡도
$O(MlogM)$ 이므로 2억번 내로 계산이 가능할 것 같다.

알고리즘 선택

DFS와 BFS로 연결 노드 탐색하기

📌 코드 설계하기

N, M, V 입력
연결 정보 저장
DFS/BFS 정의
방문 처리 리스트 정의 후, DFS/BFS 수행하며 원하는 결과 출력

📌 시도 회차 수정 사항

1회차

# 연결된 방문 안한 정점 방문
for i in graph[v]:
      if not visited[i]:
           queue.append(i)
           visited[i] = 0

결과
이와 같이 출력이 무한히 반복되는 문제가 발생했다. BFS 구현한 함수에서 방문 처리를 1로 해주어야 하는데 0으로 해주어 계속 방문 안한 정점이 발생해서 나타난 문제였다.

# 연결된 방문 안한 정점 방문
for i in graph[v]:
    if not visited[i]:
        queue.append(i)
        visited[i] = 1

결과
방문 처리를 제대로 해주어 해결했다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# 1. N, M, V 입력
N, M, V = map(int, input().split())

# 2. 연결 정보 저장
graph = [[] for _ in range(N+1)]

for _ in range(M):
    start, end = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)

# 정점별 연결 정점 오름차순 정렬
for i in range(N+1):
    graph[i].sort()

# 3. DFS/BFS 정의
def dfs(graph, start, visited):
    # 방문 처리
    visited[start] = 1
    # 결과 출력
    print(start, end=' ')
    # 연결된 방문 안한 정점 방문
    for i in graph[start]:
        if not visited[i]:
            dfs(graph, i, visited)

def bfs(graph, start, visited):
    queue = deque([start])
    # 방문 처리
    visited[start] = 1
    while queue:
        v = queue.popleft()
        # 결과 출력
        print(v, end=' ')
        # 연결된 방문 안한 정점 방문
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = 1

# 4. 방문 처리 리스트 정의 후, DFS/BFS 수행하며 원하는 결과 출력
visited = [0] * (N+1)
dfs(graph, V, visited)

print()

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

결과

📌 회고

코드를 제대로 작성했는지 꼭 확인하자.

📌 기억해야 할 정보

📖 그래프 (Graph)

노드(Node)/정점(Vertex) + 간선(Edge) 으로 표현

그래프 탐색 : 하나의 노드를 시작으로 다수의 노드 방문하는 것

📖 2가지 그래프 표현 방식

인접 행렬 (Adjacency Matrix)

2차원 배열로 그래프 연결 관계 표현 (파이썬 2차원 리스트)

연결 ❌ 노드끼리 무한(Infinity)의 비용

👍) 특정 노드 연결 정보 얻는 속도 빠름

👎) 모든 관계 저장 → 노드 많을수록 메모리 낭비

인접 리스트 (Adajacency List)

리스트로 그래프 연결 관계 표현

모든 노드에 연결된 노드 정보를 차례로 연결

👍) 연결 정보만 저장 → 메모리 효율적 사용

👎) 특정 노드 연결 정보 얻는 속도 느림