코딩테스트-인접행렬

인접행렬을 이용한 그래프 표현과 DFS 탐색

이번 글에서는 인접행렬(Adjacency Matrix)로 그래프의 연결 상태를 2차원 배열로 표현하는 방법과, 이를 이용한 DFS(깊이 우선 탐색) 과정을 정리한다.

---

1. 인접행렬을 통한 그래프 표현

인접행렬은 정점 간 연결 관계를 0 또는 1로 나타내는 2차원 배열이다. a[i][j] = 1이면 정점 i와 j가 연결되어 있다는 뜻이다.

• 양방향(무방향) 간선은 a[i][j]와 a[j][i]를 대칭적으로 모두 1로 표시한다.
• 배열 크기는 정점 개수(V)에 맞춰 설정한다.

---

2. 방문 기록 관리 (visited)

재귀로 그래프를 탐색할 때, 이미 방문한 정점을 다시 방문하면 무한 루프에 빠진다. 이를 막기 위해 visited 배열로 방문 여부를 기록해 중복 탐색을 방지한다.

---

3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int V = 10;              // 세미콜론 필수!
bool a[V][V], visited[V];      // 인접행렬 / 방문 배열

void go(int from) {
    visited[from] = 1;         // 방문 처리
    cout << from << '\n';

    for(int i = 0; i < V; i++) {
        if(visited[i]) continue;   // 이미 방문했으면 건너뜀
        if(a[from][i]) {           // from과 i가 연결되어 있으면
            go(i);                 // 재귀로 이동
        }
    }
    return;
}

int main() {
    // 무방향 간선: 대칭으로 설정
    a[1][2] = 1; a[2][1] = 1;
    a[1][3] = 1; a[3][1] = 1;
    a[3][4] = 1; a[4][3] = 1;
    // ... 이하 생략

    // 아직 방문하지 않은 정점에서 탐색 시작 (연결요소 전부 방문)
    for(int i = 0; i < V; i++) {
        if(!visited[i]) {
            // 간선이 하나라도 있는 정점부터 탐색하고 싶다면 조건 추가 가능
            go(i);
        }
    }

    return 0;
}

동작 흐름

• go(from) : 현재 정점을 방문 처리하고 출력한 뒤, 연결된 정점을 하나씩 재귀로 파고든다.
• visited[i] 체크로 이미 간 곳은 건너뛴다 → 중복/무한 탐색 방지.
• main의 반복문은 끊겨 있는 그래프(여러 연결요소)도 빠짐없이 방문하기 위한 장치다.

---

인접행렬의 한계와 최적화 포인트

인접행렬은 구현이 직관적이지만, 정점 개수 V가 커질수록 메모리가 V² 로 급증한다. 또한 go() 안에서 매번 0 ~ V-1을 전부 확인하므로, 간선이 적은(희소) 그래프에서는 비효율적이다.

• 정점이 적을 때 : 인접행렬이 오히려 간단하고 빠르다 (O(V²)).
• 정점이 많고 간선이 적을 때 : 인접 리스트(Adjacency List)로 바꾸면 메모리와 탐색 모두 효율적이다.

기준	인접행렬	인접 리스트
메모리	O(V²)	O(V + E)
간선 존재 확인	O(1)	O(차수)
추천 상황	정점이 적거나 간선이 촘촘할 때	정점이 많고 간선이 적을 때

---

정리

• 인접행렬: a[i][j] = 1이면 연결. 무방향은 대칭으로 설정.
• DFS는 재귀 + visited 배열로 중복 방문을 막는다.
• main의 반복문으로 모든 연결요소를 탐색한다.
• 정점이 많으면 인접 리스트가 메모리·속도 면에서 유리하다.