[99클럽/코딩테스트 챌린지] 그래프 자료구조, DFS, BFS

그래프란

그래프 자료구조는 노드(정점)와 간선(엣지)으로 이루어진 데이터 구조이다

• 노드(정점): 그래프에서 데이터가 저장되는 기본 단위. 예를 들어, 사람의 관계를 나타내는 그래프에서는 각 사람이 노드 이다.
• 간선(엣지): 노드와 노드를 연결하는 선. 간선은 방향성이 있을 수도 있고 없을 수도 있다. 예를 들어, 두 사람이 친구라면 이를 연결하는 간선이 있다.

그래프의 종류

방향그래프	설명
	간선에 방향이 있는 그래프이다. 예를 들어, A → B는 A에서 B로 가는 방향만 가능하다.

무방향그래프	설명
	간선에 방향이 없는 그래프이다. A와 B가 연결되어 있으면 양방향으로 이동할 수 있다.

가중그래프	설명
	간선마다 특정 **가중치(값)**가 부여된 그래프이다. 예를 들어, 도시 간 거리가 간선의 가중치로 표시될 수 있다.

비가중그래프	설명
	간선에 가중치가 없는 그래프이다. 모든 간선은 같은 값으로 간주된다.

사이클릭	설명
	**사이클(순환)**이 존재하는 그래프이다. 특정 노드에서 시작해 다시 그 노드로 돌아오는 경로가 있다.

에이사이클릭	설명
	**사이클(순환)**이 없는 그래프이다. 어떤 노드에서도 다시 원래 노드로 돌아오는 경로가 없다.

트리	설명
	하나의 루트 노드를 중심으로 계층 구조를 이루는 에이사이클릭 무방향 그래프이다. 모든 노드가 단 하나의 부모를 가지며, 루트부터 시작해 잎(Leaf)까지 연결된다.

포레스트	설명
	트리의 집합으로, 여러 개의 독립된 트리로 구성된 그래프이다. 에이사이클릭 무방향 그래프이며, 서로 연결되지 않은 트리들로 이루어져 있다.

그래프를 표현하는 방법

인접행렬

행렬 형태로 노드 간 연결 관계를 표시

행과 열이 노드를 나타내며, 간선이 있으면 1, 없으면 0으로 표시함. (가중치가 있을 경우 가중치로 표기)

탐색에 O(1) 밖에 안 걸리나, 메모리를 차지함

	1	2	3	4
1	0	1	1	0
2	1	0	0	1
3	1	0	0	1
4	0	1	1	0

 

 

인접리스트

각 노드에 연결된 노드들을 리스트로 저장 (가중치 있을 경우 추가 표기)

메모리는 효율적이나 탐색에 O(N - 노드갯수)이 걸림

 

1: [2, 3]
2: [1, 4]
3: [1, 4]
4: [2, 3]

간선리스트

간선을 리스트 형태로 저장

각 간선은 연결된 두 노드를 나타냄. (가중치 있을 경우 추가 표기)

메모리는 효율적이나 탐색에 O(N - 간선갯수)이 걸림

 

[(1, 2), (1, 3), (2, 4), (3, 4)]

 

DFS, BFS 탐색

DFS  Depth-First Search (깊이우선탐색)

 

• 그래프에서 한 경로를 가능한 멀리 끝까지 탐색한 후, 더 이상 갈 곳이 없으면 뒤로 돌아가며 탐색하는 방식이다.
• 스택(재귀 호출 또는 명시적 스택 자료구조)을 활용하여 경로를 관리한다.

탐색 과정

1->2->5->6->3->4->7

스택에서 빼는 순간 방문처리 후 그 아이템의 자식을 스택에 추가 *굵은글씨는 추가, 취소선은 삭제를 나타냄*

취소선 처리일 때 방문처리됨

		4(1의 자식)
	4 (1의 자식)	3(1의 자식)	4 (1의 자식)
	3 (1의 자식)	6(2의자식)	3 (1의 자식)	4 (1의 자식)	7 (4의 자식)
1	2 (1의 자식)	5(2의자식)	6 (2의자식)	3 (1의 자식)	4 (1의 자식)	7 (1의 자식)

 

BFS  Breadth-First Search (넓이우선탐색)

 

• 그래프에서 시작 노드부터 가까운 노드들을 먼저 탐색한 후, 점차 멀리 있는 노드를 탐색하는 방식이다.
• 큐를 이용하여 탐색할 노드의 순서를 관리한다.

탐색 과정

1->(1로 인한 2,3,4)->(3통과)->(4통과)->(2로 인한 5,6)->(5통과)->(4으로 인한 7)

큐에다 넣는 순간 방문처리 후, 빼는 순간 그 아이템의 자식들을 큐에 추가  *굵은글씨는 추가, 취소선은 삭제를 나타냄*

굵은글씨 일때 방문처리 됨

		6 (2의자식)
		5 (2의자식)	6 (2의자식)	7 (4의자식)
	4 (1의자식)	4 (1의자식)	5 (2의자식)	6 (2의자식)	7 (4의자식)
	3 (1의자식)	3 (1의자식)	4 (1의자식)	5 (2의자식)	6 (2의자식)	7 (4의자식)
1	2 (1의자식)	2 (1의자식)	3 (1의자식)	4 (1의자식)	5 (2의자식)	6 (2의자식)	7 (4의자식)

 

BFS / DFS 관련 백준 문제

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

n, lines, start = map(int, input().split())
graph = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(lines):
    e1, e2 = map(int,input().split())
    graph[e1][e2] = graph[e2][e1] = 1

visited_recur = [0 for _ in range(n + 1)]
visited_dfs = [0 for _ in range(n + 1)]
visited_bfs = [0 for _ in range(n + 1)]
result1 = []
def dfs_recur(v):
  visited_recur[v] = 1
  # 여기서 방문체크
  result1.append(v)
  for i in range(1, n+1):
      if(graph[v][i] != 0 and visited_recur[i] == 0):
          dfs_recur(i)

def dfs_stack(v):
  result = []
  stk = []
  stk.append(v)
  while len(stk) > 0:
    n_idx = stk.pop(0)
    if(visited_dfs[n_idx] == 0):
      visited_dfs[n_idx] = 1
      result.append(n_idx)
      for i in range(n, 0, -1):
          if(graph[n_idx][i] != 0 and visited_dfs[i] == 0):
            stk.insert(0, i)
  return result

def bfs_stack(v):
  result = [v]
  que = []
  que.append(v)
  visited_bfs[v] = 1
  while len(que) > 0:
    n_idx = que.pop(0)
    # 왼쪽에서부터 탐색해서 쌓도록 거꾸로가야함
    for i in range(1, n+1):
      if(graph[n_idx][i] != 0 and visited_bfs[i] == 0):
        que.append(i)
        visited_bfs[i] = 1
        result.append(i)
  return result
#dfs_recur(start)
print(' '.join(map(str,dfs_stack(start))))
print(' '.join(map(str,bfs_stack(start))))

 

일단 아래와 같이 구현하긴 했으나 dfs를 스택으로 구현 한 건은 뭔가  코드가 직관적이지가 않다..

스택에 불필요하게 스킵될만한 아이들도 들어가야하고, 웬만하면 dfs는 재귀로 짤 수 있음 짜는게 좋을 것 같다.. ㅠ