백준 1325 (그래프 이론을 위한 가변배열)

그래프 이론을 공부하기 위해 필요한 개념이 가변배열이라 생각한다.
알고리즘을 공부하다보면 메모리 초과에 대한 압박이 있을 수 밖에 없기때문에, 가변배열을 이해할 수 있어야한다.

테스트 케이스가 커지고 메모리 압박이 늘어날수록, 2차원 배열만으로 풀기는 어려워지는만큼, 가변배열에 대한 이해와 응용이 중요해진다.

첫번째 방법은, 리스트에 배열을 추가하는 방법이다.

import java.util.*;

public class Main {
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        ArrayList<Integer> list[] = new ArrayList[n+1];

        for(int i=1; i<=n; i++){
            list[i] = new ArrayList<>();    //list 배열에 arraylist를 하나씩 할당
        }

        for(int i=1; i<=n; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            list[a].add(b);		//무방향으로 한쪽만 연결
            /*list[b].add(a); 양방향 그래프는 아래와 같이 선언 */
        }

        for(int i=1; i<=n; i++){
            System.out.println(i+" "+list[i] );
        }
    }
}

위의 코드는 ArrayList에 배열을 추가하여 2차원으로 만든 코드이다. 리스트 하나마다 배열을 추가한다고 생각하면 편하다. 다음의 출력은 아래와 같다.

입력
5 4
3 1
3 2
4 3
5 3

출력
1 []
2 []
3 [1, 2]
4 [3]
5 [4, 3]

두번째 방법은 ArrayList 두개를 중첩시키는 방법이다. 두개를 중첩시킨다면 동적인 배열 두개가 생성되기 때문에 값이 들어가지 않는 불필요한 배열의 생성을 막는다.

static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();

for(int i=0; i<n; i++){
    list.add(new ArrayList<Integer>());
}

for(int i=0; i<m; i++){
    int a = sc.nextInt();
    int b = sc.nextInt();
    list.get(a).add(b);
    //양방향일 경우 list.get(b).add(a)도 추가
}

int n = list.get(a).get(b);		//a번째 b 인덱스의 값을 가져와서 n에 저장한다.
int size = list.get(a).size();	//a번째의 사이즈를 리턴한다. 

굳이 위의 두 방법중에서 하나를 선택하자면 첫번째 방법의 성능이 뛰어나다고 생각한다. 같은 문제를 풀더라도 두번째 방법은 메모리 초과가 나는 경우가 있었기 때문.. (아마 내 제출 내역을 보니까 밑의 문제를 풀면서 그랬던 것 같다..)

백준 1325 효율적인 해킹 을 풀면서 가변배열을 적용시켜 보았다.

import java.io.BufferedReader;
import java.util.*;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int n,m;
    static boolean[] visit;
    static int[] count;
    static ArrayList<Integer> map[];

    static void dfs(int node){
        visit[node] = true;

        for(int i:map[node]){
            if(visit[i]) continue;
            count[i]++;
            dfs(i);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        count = new int[n+1];
        map = new ArrayList[n+1];
        visit = new boolean[n+1];

        for(int i=1; i<=n; i++){
            map[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            map[a].add(b);
        }

        for(int i=1; i<=n; i++){
            visit = new boolean[n+1];
            dfs(i);
        }
        int cnt = 0;
        for(int i=1; i<=n; i++){
            cnt = Math.max(cnt,count[i]);
        }

        for(int i=1; i<=n; i++){
            if(count[i] == cnt){
                System.out.print(i + " ");
            }
        }

    }
}

이 문제의 경우 신뢰하는 경우와 그렇지 않은 경우가 있기 때문에 단방향으로 풀어야 한다. 가장 많은 컴퓨터의 수를 출력해야하기 때문에 하나의 컴퓨터마다 dfs를 해주면서 카운트해줘야 한다.