Java 인접리스트 구현하기

Published on 2018 Oct 01 00:35:49
Last Updated on 2018 Oct 01 00:36:49

Java 인접리스트 구현

그래프 문제를 풀 때는 그래프 모델링을 해야하는데, 보통 잘 알려진 방법은 두 가지가 있다.

  1. 인접행렬
  2. 인접리스트

백준 오프라인 강의 들을 때 간선리스트라는 개념도 배웠지만, 잘 알려진게 아니고 나도 당시에 이해하고 넘어간게 아니라서 생략..

어지간한 문제 풀다보면 인접리스트를 많이 사용하게 되는데, 솔직히 자바로 짜면 C++보다 아주 조금 더 귀찮다.

List<Integer> 배열을 만들던지, 아니면 List안에 List<Integer>를 집어넣어서 표현하던지 하고, 각각 반복문 돌려서 new ArrayList<>() 같은 처리도 해줘야 하고…

꼭 이렇게 해줘야한다는 규칙은 없지만 다른 사람들 코드를 봐도 보통 이 두가지를 많이 쓰는 것 같다.

여튼 개인적으로 문제 풀 때 써먹기 위해서 (그리고 솔직히 매번 입력해주는게 귀찮아서) 클래스를 간단하게 짰다.

class Graph {
    private List<List<Integer>> graph;
    public Graph(int initSize) {
        this.graph = new ArrayList<>();
        for(int i = 0; i < initSize+1; i++) {
            graph.add(new ArrayList<>());
        }
    }
    public List<List<Integer>> getGraph() {
        return this.graph;
    }
    public List<Integer> getNode(int x) {
        return this.graph.get(x);
    }
    public void put(int x, int y) {
        graph.get(x).add(y);
        graph.get(y).add(x);
    }
    public void putSingle(int x, int y) {
        graph.get(x).add(y);
    }
}

메서드 이름도 나 혼자 알아보게 짰고, 전체적으로 되게 엉성하다.

각각 설명하자면 다음과 같다.

사실 근데 이 정도만 있어도 딱히 못 쓸건 없고, 굉장히 편하다. 문제가 요구하는 내용에 맞게 메서드 추가하거나 자료형 바꿔주거나 해서 쓰면 된다. (다익스트라를 풀기 위해 Integer대신에 개인적으로 만든 Vertex 클래스를 쓴다던가)

문제 풀때마다 일일히 인접리스트 구현 코드 작성하다보면 정말 가끔 기억이 안나서 코딩 실수 할 때가 있었는데 이런식으로 해놓으니 편하더라.

워낙 간단한 내용이라 이 코드 자체가 다른 사람에게 도움이 될 것 같지는 않고, 실제 상황 (기업 코딩 테스트, 집에서 혼자 백준 풀어보기, 코드포스 참가 등)에서 시간을 절약하기 위해 필요한 자료구조들을 미리 구현해놓는 것은 중요하다고 생각해서 써봤다.

이것을 사용해서 푼 문제는 아래에서 확인해볼 수 있다.

코드 링크