인접 리스트 Tip (dict)

실전 그래프 구현: Map 기반 인접 리스트

그래프를 다룰 때 가장 효율적인 표현 중 하나는 인접 리스트(Adjacency List)이다.

자바에서 Map<Integer, List<Integer>> 형식을 사용해 인접 리스트를 구성하고, 실전 문제에서 활용하는 방법을 보여준다.

1. 인접 리스트를 Map으로 표현하기

자바에서는 각 정점과 그에 연결된 정점들을 Map에 저장하는 방식으로 인접 리스트를 표현할 수 있다.

예시 코드

Map<Integer, List<Integer>> graph = new HashMap<>() {{
    put(0, List.of(1, 3, 6));
    put(1, List.of(0, 3));
    put(2, List.of(3));
    put(3, List.of(0, 1, 2, 7));
    put(4, List.of(5));
    put(5, List.of(4, 6, 7));
    put(6, List.of(0, 5));
    put(7, List.of(3, 5));
}};

• 키: 정점 번호
• 값: 해당 정점과 연결된 이웃 정점 목록

2. 간선 리스트를 Map 기반 인접 리스트로 변환하기

알고리즘 문제에서는 보통 간선 정보(edge list) 가 주어지며, 이를 Map 형태의 인접 리스트로 바꿔야 한다.

예시 입력

int[][] edges = {
    {0, 1}, {0, 3}, {0, 6},
    {1, 3}, {2, 3}, {3, 7},
    {4, 5}, {5, 6}, {5, 7}
};
int n = 8; // 정점 개수

양방향 그래프 변환

Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
    graph.put(i, new ArrayList<>());
}

for (int[] edge : edges) {
    int a = edge[0], b = edge[1];
    graph.get(a).add(b);
    graph.get(b).add(a);  // 양방향일 경우
}

단방향 그래프 변환

Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
    graph.put(i, new ArrayList<>());
}

for (int[] edge : edges) {
    int from = edge[0], to = edge[1];
    graph.get(from).add(to);  // 단방향 연결
}

 

3. 연결된 노드 탐색하기

기본 구조

int curVertex = 3;
for (int nextVertex : graph.get(curVertex)) {
    System.out.println("노드 " + curVertex + " → 다음 노드 " + nextVertex);
}

전체 예시

Map<Integer, List<Integer>> graph = new HashMap<>() {{
    put(0, List.of(1, 3, 6));
    put(1, List.of(0, 3));
    put(2, List.of(3));
    put(3, List.of(0, 1, 2, 7));
    put(4, List.of(5));
    put(5, List.of(4, 6, 7));
    put(6, List.of(0, 5));
    put(7, List.of(3, 5));
}};

int curVertex = 3;
for (int nextVertex : graph.get(curVertex)) {
    System.out.println("노드 " + curVertex + " → 다음 노드 " + nextVertex);
}

출력 결과

노드 3 → 다음 노드 0
노드 3 → 다음 노드 1
노드 3 → 다음 노드 2
노드 3 → 다음 노드 7