[BOJ] 1260 DFS와 BFS

DFS, BFS 예제

문제

문제 풀이

문제 리뷰

그래프(Graph)

• 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조
  
• G = (V, E)
  

• 방향 그래프, 무방향 그래프로 나뉘어진다.
  

  방향 그래프 - 방향이 있는 곳으로만 간다.
  

  무방향 그래프 - 양쪽 모두 갈 수 있다.

---

그래프 탐색 방법

DFS, BFS 개념은 DFS와 BFS 에서 따로 정리했습니다!

• DFS (깊이 우선 탐색) : 재귀 or 스택
• BFS (너비 우선 탐색) : 큐

---

DFS, BFS를 구현할 때, 인접행렬이나 인접리스트를 이용한다.

인접행렬보다 인접리스트가 보다 효율적이다.

✔︎ 인접행렬

• 공간 복잡도 : O(V^2)

• 정점(V)이 n개일 때, N x N 이차원 배열로 나타낼 수 있다.
  

  이차원 배열의 행과 열을 통해 정점 간의 간선을 표현

위의 그래프를 보면 정점 1과 정점 3의 간선이 연결되어있음을 알 수 있다.
무방향 그래프이기에 인접행렬로 아래 예시와 같이 나타낼 수 있다.

ex) Ad[1][3] = 1, Ad[3][1] = 1

값이 1이면 정점 간의 간선이 존재한다는 의미이고
값이 0이면 존재하지 않는다는 의미이다.

---

✔︎ 인접리스트

• 공간 복잡도 : O(V + E)

  필요한 공간만 쓰기 때문에

인접행렬은 이차원 배열의 행과 열을 통해 정점 간의 간선을 표현했다면
인접리스트는 해당 정점과 연결되어있는 간선들을 아래 예시와 같이 저장한다.

ex) A[1] = {2, 3, 4, 5} / A[2] = {1, 3, 5}

참고

• [그래프] DFS와 BFS 구현하기 :: 마이구미
• [백준,BOJ 1260] DFS와 BFS(JAVA 구현)

TMI

DFS, BFS 얼른 마스터하자..!

1일 2알고리즘 완료🤓