(코테) [Java] 그래프 만들기

전제 파악 먼저

질문 예시인 1 3, 2 6은 아래 중 어떤 걸 의미할 수 있음

문제에서 보면 한번 갔다가 다시 돌아오는 경우나 한번만 가고 끝나는 경우가 있을 수 있음

그래서 문제를 어떻게 풀어야하는지 잘 확인해 보아야함

해석	의미	예시
방향 없음 (무방향 그래프)	1 — 3, 2 — 6	친구 관계, 양방향 도로
방향 있음 (단방향 그래프)	1 → 3, 2 → 6	트리, 네트워크 흐름, 의존성
방향 + 가중치 있음	1 → 3 (가중치 w)	다익스트라, 벨만포드
방향 + 시간 / 비용 / 거리	2 → 6 (시간 5초)	백준 10282 해킹 문제

 

대표적인 그래프 표현 방식 2가지

1. 인접 리스트 (Adjacency List) ⭐ 가장 많이 씀

• 정점 수가 많고 간선 수가 적을 때 유리 (희소 그래프)
• 구현이 간결하고 공간 효율 좋음

List<Integer>[] graph = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
    graph[i] = new ArrayList<>();
}
graph[1].add(3);
graph[2].add(6);

➕ 가중치도 넣고 싶다면?

List<int[]>[] graph = new ArrayList[N + 1];
// graph[from].add(new int[]{to, weight});
graph[1].add(new int[]{3, 5}); // 1 → 3 (가중치 5)

 

 

2. 인접 행렬 (Adjacency Matrix)

• 정점 수가 적고, 간선이 많을 때 유리 (밀집 그래프)
• 모든 노드 간 연결 상태를 빠르게 확인할 수 있음

int[][] graph = new int[N + 1][N + 1];
// 무방향 그래프라면
graph[1][3] = 1;
graph[3][1] = 1;

// 단방향 그래프라면
graph[2][6] = 1;

➕ 가중치도 넣을 수 있음

graph[2][6] = 7; // 2 → 6, 가중치 7

 

 

 

정리하자면?

목적	방식	추천 이유
일반적인 코딩 테스트, 경로 탐색 문제	인접 리스트	공간 효율 좋고 유연
간선에 가중치가 있음 (다익스트라 등)	List<int[]>[]	int[]{to, cost} 형태
노드 수가 작고, 연결이 빽빽함	인접 행렬	즉시 접근이 빠름
노드 번호가 비연속적임	Map 사용 가능	Map<Integer, List<...>>