9470번 - Strahler 순서(비순환 그래프)

문제:

 

풀이:

가장 큰 Strahler 순서를 구하기 위해서는,

첫 노드부터 마지막 노드까지 깊이에 따라 순차적으로 Strahler 순서를 구해야 한다.

이를 위해서 각 노드는 다음 노드 정보를 저장하고 있어야 한다. 그래야 다음 노드로 이동을 할 수 있기 때문이다.

 

다음 노드로 이동을 했다 하더라도, 만일 이전 노드를 모두 계산하지 않고 넘어가면,

올바르게 Strahler 순서를 계산할 수 없다.

 

또한 문제에 조건에 따라,

"들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다."

라는 조건을 고려해야 한다.

 

결국 마지막 노드의 Strahler 순서를 구하기 위해서는 아래 조건이 만족되어야 한다.

1. 각 노드는 다음 노드의 정보를 가지고 있어야 함
2. 각 노드의  Strahler 순서를 계산하려면, 이전 노드의 Strahler 순서를 모두 알아야 함
3. Strahler 순서를 계산하기 위해서는 이전 노드의 가장 큰 Strahler 순서와, 그 개수를 알아야 함.

이렇듯 노드는 3개 이상의 각기 다른 형태의 정보를 저장하고 있어야 한다.

여러 자료구조만을 이용해도 되겠지만, 클래스를 이용하기 적절한 조건이다.

위의 조건에 만족하는 클래스를 작성해보도록 하자.

class River {
    private int prevCount;
    private int strahler;
    private int strahlerCount; // 동일한 Strahler의 개수
    private List<River> next;

    River() {
        this.prevCount = 0;
        this.strahler = 0;
        this.strahlerCount = 0;
        this.next = new ArrayList<>();
    }
}

• prevCount는 이전 노드의 Strahler 순서가 모두 구해졌는지 나타낸다.
  Strahler 순서가 구해지지 않은 이전 노드가 추가되면 1씩 더해지고,
  이전 노드의 Strahler 순서가 구해지면 1씩 빼져, 이전 노드의 Strahler 순서가 모두 구해지면 0이된다.
• strahler는 말 그대로 현 노드의 Strahler 순서를 나타낸다.
• strahlerCount는 이전 노드들의 가장 큰 Strahler 순서가 중복되는 정도를 나타낸다.
• next는 다음 노드들을 나타낸다.

클래스의 각 변수에 대한 설명에, 메서드에 할 일이 담겨있다. 아래 문장에 대한 메서드를 작성해야 한다.

"Strahler 순서가 구해지지 않은 이전 노드가 추가되면 1씩 더해지고,
이전 노드의 Strahler 순서가 구해지면 1씩 빼져, 이전 노드의 Strahler 순서가 모두 구해지면 0이된다."

// 다음 노드를 저장하며, 다음 노드의 이전 노드 개수를 1 더해줌
void addNext(River r) {
    next.add(r);
    r.prevCount += 1;
}

void subPrevCount() {
    prevCount--;
}

이렇게 위 문장에 대한 메서드를 작성할 수 있다.

addNext() 메서드는 다음 노드를 저장할 때, 다음 노드의 prevCount를 1 늘려준다.

 

또한 올바른 Strahler 순서를 구하기 위한 메서드도 있으면 좋을 것 같다.

"들어오는 모든 강 중에서 Strahler 순서가 i인 강이 1개이면 순서는 i, 2개 이상이면 순서는 i+1이다."

라는 문장에 따른 메서드를 작성해보자.

// 올바른 strahler 값과 반복 횟수를 저장하기 위한 메서드
void updateStrahler(int newStrahler) {
    if (this.strahler < newStrahler) {
        this.strahler = newStrahler;
        this.strahlerCount = 1;
    } else if (this.strahler == newStrahler) {
        this.strahlerCount++;
    }
}

// 최종적으로 해당 노드의 strahler값을 정해주기 위한 메서드
void finalizeStrahler() {
    if (this.strahlerCount > 1) {
        this.strahler++;
    }
}

updateStrahler은 이전 노드의 Strahler 순서 중 가장 큰 값으로 지금 노드의 Strahler 순서를 업데이트 해주고,

만일 같은 Strahler 순서가 나온다면 strahlerCount에 1을 더해준다.

finalizeStrahler은 최대 Strahler 순서(i)가 두개이상 있을 때, Strahler 순서를 i+1로 변경해준다.

 

또한 직접 접근을 막기 위해 getter 메서드를 만들어 주어서 아래와 같은 클래스가 완성되었다.

class River {
    private int prevCount;
    private int strahler;
    private int strahlerCount; // 동일한 Strahler의 개수
    private List<River> next;

    River() {
        this.prevCount = 0;
        this.strahler = 0;
        this.strahlerCount = 0;
        this.next = new ArrayList<>();
    }

    int getPrevCount() {
        return prevCount;
    }

    int getStrahler() {
        return strahler;
    }

    List<River> getNext() {
        return next;
    }

    // 다음 노드를 저장하며, 다음 노드의 이전 노드 개수를 1 더해줌
    void addNext(River r) {
        next.add(r);
        r.prevCount += 1;
    }

    void subPrevCount() {
        prevCount--;
    }

    // 올바른 strahler 값과 반복 횟수를 저장하기 위한 메서드
    void updateStrahler(int newStrahler) {
        if (this.strahler < newStrahler) {
            this.strahler = newStrahler;
            this.strahlerCount = 1;
        } else if (this.strahler == newStrahler) {
            this.strahlerCount++;
        }
    }

    // 최종적으로 해당 노드의 strahler값을 정해주기 위한 메서드
    void finalizeStrahler() {
        if (this.strahlerCount > 1) {
            this.strahler++;
        }
    }

}

 

먼저 main 메서드를 설계해보자. 입, 출력을 담당할 것이다.

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

    int T = Integer.parseInt(st.nextToken());
    int[][] arr = new int[T][2];
    for (int i = 0; i < T; i++) {
        st = new StringTokenizer(br.readLine());
        int K = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        List<River> riverList = new ArrayList<>();
        for (int j = 0; j <= M; j++) {
            riverList.add(new River());
        }

        for (int j = 0; j < P; j++) { // 각 노드의 정보 저장
            st = new StringTokenizer(br.readLine());
            int prev = Integer.parseInt(st.nextToken());
            int next = Integer.parseInt(st.nextToken());
            riverList.get(prev).addNext(riverList.get(next));
        }

        arr[i][0] = K;
        arr[i][1] = findMax(M, riverList);
    }
    for (int i = 0; i < T; i++) {
        System.out.println(arr[i][0] + " " + arr[i][1]);
    }
}

각 노드의 정보를 입력받을 때, List와 River 클래스를 이용하며,

각 노드의 정보가 저장될때, addNext() 메서드를 활용해, 다음 노드를 함께 저장한다.

이 과정에서 다음 노드의 prevCount가 1씩 증가된다.

이후, findMax() 메서드를 통해 하천계의 Strahler 순서를 구한다.

 

올바른 하천계의 Strahler 순서를 구할 수 있게 해주는 findMax() 메서드를 작성해보자.

static int findMax(int M, List<River> riverList) {
    Queue<River> queue = new LinkedList<>();

    // 시작 노드들을 큐에 넣어줌
    for (int j = 1; j <= M; j++) {
        River river = riverList.get(j);
        if (river.getPrevCount() == 0) {
            river.updateStrahler(1);
            queue.add(river);
        }
    }

    // 다음 노드를 queue에 저장된 순서로 탐색
    while (!queue.isEmpty()) {
        River river = queue.poll();
        for (River next : river.getNext()) {
            next.subPrevCount(); // 다음 노드의 이전 노드 하나(현재 노드)를 탐색했음
            next.updateStrahler(river.getStrahler()); // 다음 노드의 Strahler 값을 업데이트
            if (next.getPrevCount() == 0) { // 다음 노드의 이전 노드를 모두 탐색했다는 뜻
                next.finalizeStrahler(); // 최종적으로 다음 노드의 Strahler 값을 업데이트
                queue.add(next);
            }
        }
    }

    return riverList.get(M).getStrahler();
}

BFS 알고리즘을 활용하여 문제를 풀 수 있었다.

1. queue에 시작 노드들을 저장한다.
   각 노드들은 List 형식으로 저장되어 있고, 시작 노드들의 prevCount는 0이므로 쉽게 구할 수 있다.
2. 큐에 데이터가 들어있는 동안 아래 과정을 수행한다.
   1. queue에서 River 객체 하나를 꺼낸다.
   2. 해당 River객체에서 다음 노드의 정보를 모두 탐색한다.
      1. 다음 노드가 이전 노드 하나를 탐색했다고 표시한다.(subPrevCount() 메서드)
      2. 이에 따라 다음 노드의  Strahler 순서를 업데이트 한다.(updateStrahler() 메서드)
      3. 만일 다음 노드의 prevCount 값이 0이면,
         다음 노드의 정확한 Strahler 순서를 계산하고,(finalizeStrahler() 메서드)
         큐에 다음 노드를 추가한다.
3. 위 반복문이 종료되면, 마지막 노드(M)의 Strahler 순서, 즉 하천계의 Strahler 순서를 반환한다.

 

전체코드:

import java.io.*;
import java.util.*;

class River {
    private int prevCount;
    private int strahler;
    private int strahlerCount; // 동일한 Strahler의 개수
    private List<River> next;

    River() {
        this.prevCount = 0;
        this.strahler = 0;
        this.strahlerCount = 0;
        this.next = new ArrayList<>();
    }

    int getPrevCount() {
        return prevCount;
    }

    int getStrahler() {
        return strahler;
    }

    List<River> getNext() {
        return next;
    }

    // 다음 노드를 저장하며, 다음 노드의 이전 노드 개수를 1 더해줌
    void addNext(River r) {
        next.add(r);
        r.prevCount += 1;
    }

    void subPrevCount() {
        prevCount--;
    }

    // 올바른 strahler 값과 반복 횟수를 저장하기 위한 메서드
    void updateStrahler(int newStrahler) {
        if (this.strahler < newStrahler) {
            this.strahler = newStrahler;
            this.strahlerCount = 1;
        } else if (this.strahler == newStrahler) {
            this.strahlerCount++;
        }
    }

    // 최종적으로 해당 노드의 strahler값을 정해주기 위한 메서드
    void finalizeStrahler() {
        if (this.strahlerCount > 1) {
            this.strahler++;
        }
    }

}

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

        int T = Integer.parseInt(st.nextToken());
        int[][] arr = new int[T][2];
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int P = Integer.parseInt(st.nextToken());

            List<River> riverList = new ArrayList<>();
            for (int j = 0; j <= M; j++) {
                riverList.add(new River());
            }

            for (int j = 0; j < P; j++) { // 각 노드의 정보 저장
                st = new StringTokenizer(br.readLine());
                int prev = Integer.parseInt(st.nextToken());
                int next = Integer.parseInt(st.nextToken());
                riverList.get(prev).addNext(riverList.get(next));
            }

            arr[i][0] = K;
            arr[i][1] = findMax(M, riverList);
        }
        for (int i = 0; i < T; i++) {
            System.out.println(arr[i][0] + " " + arr[i][1]);
        }
    }

    static int findMax(int M, List<River> riverList) {
        Queue<River> queue = new LinkedList<>();

        // 시작 노드들을 큐에 넣어줌
        for (int j = 1; j <= M; j++) {
            River river = riverList.get(j);
            if (river.getPrevCount() == 0) {
                river.updateStrahler(1);
                queue.add(river);
            }
        }

        // 다음 노드를 queue에 저장된 순서로 탐색
        while (!queue.isEmpty()) {
            River river = queue.poll();
            for (River next : river.getNext()) {
                next.subPrevCount(); // 다음 노드의 이전 노드 하나(현재 노드)를 탐색했음
                next.updateStrahler(river.getStrahler()); // 다음 노드의 Strahler 값을 업데이트
                if (next.getPrevCount() == 0) { // 다음 노드의 이전 노드를 모두 탐색했다는 뜻
                    next.finalizeStrahler(); // 최종적으로 다음 노드의 Strahler 값을 업데이트
                    queue.add(next);
                }
            }
        }

        return riverList.get(M).getStrahler();
    }
}

 

시행착오:

처음에는 클래스에 메서드를 작성하지 않고, findMax 메서드에서 모든 일을 수행해주었다.

그러나 코드의 가독성이 좋지 않다는 것을 알게 되었고, River 클래스에 관련된 로직을 메서드로 분리하여,

더욱 가독성 높은 코드를 작성하고, 각 메서드와 클래스의 책임을 명확히 할 수 있었다.

 

올바른 객체지향적 프로그래밍을 좀 더 잘하기 위해 정진해야겠다.