[JAVA] 이차원 ArrayList로 그래프 표현

코딩 테스트 문제에서 그래프 관련 알고리즘이 자주 등장한다. 이때 그래프 구조를 표현 하는데 많이 사용하는 것이 이차원 ArrayList 이다.

 

이차원 ArrayList의 선언부터 활용하끼 3단계로 나눠 설명하겠다.

 

 

그래프의 대한 내용은 아래 포스팅을 참고하면 된다.

[자료구조] 그래프 (Graph)

---

01. 이차원 ArrayList 선언과 초기화

그래프의 에지를 표현하는 클래스를 만들어 두었다.

class Edge{
    int endNode;
    int value;

    public Edge(int endNode, int value) {
        this.endNode = endNode;
        this.value = value;
    }
}

 

해당 클래스를 자료형으로 하는 이차원 ArrayList를 선언하는 코드

ArrayList<Edge>[] list = new ArrayList[E];

 

ArrayList 각각에 생성 작업을 추가로 해주는 코드

for(int i = 0 ; i < list.length ; i++) {
    list[i] = new ArrayList<Edge>();
}

 

이제 초기화를 완료하였다. 이어서 생성한 이차원 ArrayList에 그래프 데이터를 저장해 보겠다.

 

02. 그래프 데이터 저장하기

다음과 같은 간단한 그래프가 있다고 가정하겠다.

예시 그래프

예시 그래프를 코딩 테스트에선 입력값을 아래 처럼 주어진다.

3 4		# 노드가 3개, 엣지가 4개
1 2 4		# 1번 노드에서 2번노드로 가는 가중치 4의 엣지
2 1 10
1 3 7
3 2 6

 

그래프 데이터를 이차원 ArrayList에 저장하는 코드

for(int i = 0 ; i < E ; i++) {
    st = new   StringTokenizer(br.readLine());
    int s = Integer.parseInt(st.nextToken());
    int e = Integer.parseInt(st.nextToken());
    int v =  Integer.parseInt(st.nextToken());

    list[s].add(new Edge(e, v));
}

 

위 코드 처럼 저장하면 이차원 ArrayList에 다음과 같이 데이터가 저장된다.

1 → (2, 4) (3, 7)

2 → (1, 10)

3 → (2, 6)

 

03. 그래프 데이터 가져오기

마지막으로 저장된 그래프 데이터 중 필요한 데이터를 가져와보겠다.

 

1번 노드에서 시작하는 엣지 데이터를 가져오는 코드

for(int i = 0 ; i < list[1].size() ; i++) {
    Edge tmp = list[1].get(i);
    int next = tmp.endNode;
    int value = tmp.value;

    bw.write(next + " " + value + "\n");
}

# 실행 결과
2 4
3 7

---

이차원 ArrayList를 사용해 그래프 표현 전체 코드

import java.io.IOException;
import java.io.FileReader;

void main() throws IOException {
    String filepath = "input";
    BufferedReader br = new BufferedReader(new FileReader(filepath));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String NE = br.readLine();
    StringTokenizer st = new  StringTokenizer(NE);

    int N = Integer.parseInt(st.nextToken());
    int E = Integer.parseInt(st.nextToken());

    ArrayList<Edge>[] list = new ArrayList[E];

    for(int i = 0 ; i < list.length ; i++) {
        list[i] = new ArrayList<Edge>();
    }

    for(int i = 0 ; i < E ; i++) {
        st = new   StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int v =  Integer.parseInt(st.nextToken());

        list[s].add(new Edge(e, v));
    }

    for(int i = 0 ; i < list[1].size() ; i++) {
        Edge tmp = list[1].get(i);
        int next = tmp.endNode;
        int value = tmp.value;

        bw.write(next + " " + value + "\n");
    }

    bw.flush();
    bw.close();
}

class Edge{
    int endNode;
    int value;

    public Edge(int endNode, int value) {
        this.endNode = endNode;
        this.value = value;
    }
}

---

내용 출처

Do it! 알고리즘 코딩 테스트: 자바 편 | 김종관