[딩코딩코 2025 코딩테스트 필수 알고리즘] - 17. 그래프

본 글은 딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』
강의를 듣고 정리한 내용입니다.
강의와 수업 자료에 수록된 일부 코드와 이미지를 참고하여 발췌·활용하였습니다.
코딩테스트 준비를 체계적으로 하고 싶으시다면, 아래 링크에서 강의를 확인해 보세요
👉 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 보러 가기
본 게시물은 파트너스 활동의 일환으로 작성되었으며, 구매 시 소정의 수수료를 받을 수 있습니다.

---

그래프

그래프란?

그래프란 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조를 말한다.

비선형 구조는 표현, 선형구조는 자료를 저장하고 꺼내는 것 에 초점이 맞춰져 있는데 그래프는 연결 관계에 초점이 맞춰져 있다.

그래프 용어

• 노드(Node) : 연결 관계를 가진 각 데이터를 의미한다. 정점이라고도 한다.
• 간선(Edge) : 노드 간의 관계를 표시한 선
• 인접 노드(Adjacent Node) : 간선으로 직접 연결된 노드(정점)
• 유방향 그래프 : 방향이 있는 간선을 갖는다.(간선은 한 방향으로만 진행)
• 무방향 그래프 : 방향이 없는 간선을 갖는다.

---

그래프 표현 방법

그래프 표현 방법에는 두 가지 방법이 있다.

1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현
2. 인접 리스트(Adjacency List) : 링크드 리스트로 그래프의 연결 관계를 표현

아래와 같은 그래프가 있다고 하자.

          2 - 3      4. ....  9999999
          ⎜       
      0 - 1

인접 행렬(2차원 배열)

1. 2차원 배열로 표현
2. 0 1 2 3 0 X O X X 1 O X O X 2 X O X O 3 X X O X
3. 위 내용을 배열로 표현
4. graph = [ [False, True, False, False], [True, False, True, False], [False, True, False, True], [False, False, True, False] ]
5. 서로 연결되었는지 확인
   • graph[1][2] → 시간 복잡도 O(1)
6. 공간 복잡도
   • O(N^2)

인접 리스트

1. 모든 노드에 연결된 노드에 대한 정보를 차례대로 저장
2. 0 -> 1 1 -> 0 -> 2 2 -> 1 -> 3 3 -> 2
3. 위 내용을 딕셔너리로 표현
4. graph = { 0: [1], 1: [0, 2] 2: [1, 3] 3: [2]
5. 서로 연결되었는지 확인
   • graph[0] 원소들을 다 봐야함 → 시간 복잡도 O(N)
6. 공간 복잡도
   • O(N)

차이점

두 방식의 차이는 시간 과 공간이다.

인접 행렬으로 표현하면 바로 연결되었는지 여부를 알 수 있다. 그러나, 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2) 만큼의 공간을 사용해야 한다.

인접 리스트로 표현하면 바로 연결되었는지 알 수 없고, 각 리스트를 돌아봐야 한다. 연결되었는지 여부를 알기 위해서 최대 O(간선) 만큼의 시간을 사용해야 한다. 하지만 모든 조합의 연결 여부를 저장할 필요가 없으니 O(노드+간선) 만큼의 공간을 사용한다.