[파이썬] 1260번 'DFS와 BFS' 문제 풀이

[파이썬] 1260번 'DFS와 BFS' 문제 풀이

300x250

DFS와 BFS의 개념을 알고 있다면 풀 수 있는 문제입니다.

(정점 번호가 작은 것을 먼저 방문, 간선은 양방향)

주어진 정점에 대한 정보를 인접리스트로 변환하여 푸는 방법과 인접행렬로 변환 후 푸는 방법 두 가지를 이용하여 문제를 해결하였습니다.

예시

인접리스트란?

시간복잡도: O(V+E)

그래프의 한 꼭짓점에서 연결되어있는 꼭짓점들을 하나의 연결 리스트로 표현하는 방법입니다.

각 정점에 대한 정보가 예시와 같이 주어졌을 때, 인접 리스트는 다음과 같이 표현됩니다.

인접행렬이란?

시간 복잡도: O(V^2)

그래프의 연결 관계를 NxM의 2차원 행렬로 나타낸 것이며 가중치가 없는 경우 1과 0으로 구성되어 있습니다.

간선이 양방향인 경우, 인접행렬은 대각선을 기준으로 하는 대칭 행렬의 형태를 갖고 있습니다.

각 정점에 대한 정보가 예시와 같이 주어졌을 때, 인접 행렬은 다음과 같이 표현됩니다.

인접 행렬(adjacency matrix)

※인접 행렬은 모든 관계를 저장하기 때문에 노드 개수가 많다면 비효율적인 방법이라고 할 수 있습니다.

풀이1(인접리스트)

from collections import deque def dfs(graph, v, visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited) def bfs(graph,coord,visited): queue=deque([coord]) visited[coord]=True while queue: v=queue.popleft() print(v,end=' ') for i in graph[v]: if not visited[i]: queue.append(i) visited[i]=True N, M, V = map(int, input().split()) graph = [[] for _ in range(N+1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) for i in graph: i.sort() visited = [False] * (N + 1) dfs(graph,V,visited) visited = [False] * (N + 1) print() bfs(graph,V,visited)

풀이2(인접행렬)

from collections import deque def dfs(Mat,v,visited): visited[v]=True print(v, end=' ') for i in range(1,N+1): if(visited[i]==False and Mat[v][i]==True): dfs(Mat,i,visited) def bfs(Mat,v,visited): queue=deque([v]) visited[v]=True while queue: v=queue.popleft() print(v, end=' ') for i in range(1, N+1): if(visited[i]==False and Mat[v][i]==True): queue.append(i) visited[i]=True N, M, V = map(int, input().split()) Mat = [[0]*(N+1) for _ in range(N+1)] for _ in range(M): a, b = map(int, input().split()) Mat[a][b]=1 Mat[b][a]=1 print(Mat) visited = [False] * (N + 1) dfs(Mat,V,visited) visited = [False] * (N + 1) print() bfs(Mat,V,visited)

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

from http://lbdiaryl.tistory.com/173 by ccl(A) rewrite - 2021-10-08 15:00:35