[BOJ21276] 계보 복원가 호석 (자료구조, 해시맵, 인접 리스트, 그래프)

 

 

---

문제 링크

https://www.acmicpc.net/problem/21276

21276번: 계보 복원가 호석

 

문제 풀이

- 한달 지난 후 두번째 풀이

- 배열/정렬/해시맵/인접행렬과 같은 자료 구조를 활용하는 문제였다 

예제 입력
7 -- 사람 수
daeil sangdo yuri hoseok minji doha haeun
7 -- 정보의 개수
hoseok sangdo     -- X 의 조상은 Y이다
yuri minji
hoseok daeil
daeil sangdo
haeun doha
doha minji
haeun minji


예제 출력 
2          -- 가문의 수
minji sangdo -- 가문의 시조, 그 아래는 이름을 오름차순으로 하여 직계 자식 수와 이름 정렬 후 출력
daeil 1 hoseok
doha 1 haeun
haeun 0
hoseok 0
minji 2 doha yuri
sangdo 1 daeil
yuri 0

 

절차

0. String[] names, Map<String, Integer> nameIdx 필드 선언하여 이름과 인덱스 정보를 기록했다

 

1. 데이터 초기화시 List<Integer>[] ancestor (인접리스트)에서 조상이 없는 경우(=리스트가 비어있는 경우) 해당 노드가 조상이다

-- 조상 정보 획득

hoseok	sangdo, daeil
yuri	minji
daeil	sangdo
haeun	doha, minji
doha	minji

 

2. 직계 자식 정보를 구한다. (노드 사이의 depth 차이가 1이 되는 경우 부모-자식 관계라 할 수 있다)

2-1 방식) 초기화시 List<Integer>[] childs 인접 행렬을 하나 더 선언하여 순차 조회하면서 int[] depths 정보를 갱신한다. 

(자식 노드면 +1 해주면 된다)

 

2-2 방식) List<Integer>[] ancestor 인접 행렬의 size()가 곧 해당 노드의 depth 의미하므로, 순차 조회시 자식 노드와 조상노드의 depth차가 1만큼 나면 부모-자식 관계가 되어 원하는 정보를 구할 수 있었다 .

 

hoseok	2 depth
yuri	1 depth
daeil	1 depth
haeun	2 depth
doha	1 depth
minji	0 depth
sangdo	0 depth

출처. 백준

 

3. String[] names를 오름차순 정렬하여 순차 조회하면서 문제에 주어진 정보를 StringBuilder에 담는다.

-- name 자식수 자식이름 .. 

 

4. StringBuilder 데이터를 출력한다

 

 

 

제출 코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int N, M;
    
    static String[] names;

    static Map<String, Integer> nameIdx;
    
    static List<Integer>[] ancestor;

    static List<String>[] childs;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine()); 

        names = new String[N];
        nameIdx = new HashMap<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            String name = st.nextToken();
            names[i] = name;
            nameIdx.put(name, i); 
        }


        M = Integer.parseInt(br.readLine());

        ancestor = new ArrayList[N]; 
        childs = new ArrayList[N]; 
        for(int i = 0; i < N; i++) {
            ancestor[i] = new ArrayList<>();
            childs[i] = new ArrayList();
        }

        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            String _child = st.nextToken();
            String _ancestor = st.nextToken();

            ancestor[nameIdx.get(_child)].add(nameIdx.get(_ancestor));
        }
    }

    static void pro() {
        // 최상위 조상과, 부모-자식 관계 정보 구한다 (depth 차이가 1이면 부모-자식 관계)
        List<String> roots = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            if(ancestor[i].isEmpty()) {
                roots.add(names[i]);
            }

            for(int j : ancestor[i]) {
                int depthI = ancestor[i].size(); 
                int depthJ = ancestor[j].size();

                if(depthJ == depthI - 1) {
                    childs[j].add(names[i]);
                }
            }
        }


        sb.append(roots.size()).append("\n");
        Collections.sort(roots); 
        for(String root : roots) sb.append(root).append(" ");

        sb.append("\n");

        
        Arrays.sort(names); 
        for(String name : names) {
            int idx = nameIdx.get(name);

            sb.append(name).append(" ");

            List<String> child = childs[idx];
            sb.append(child.size()).append(" ");

            Collections.sort(child);
            for(String c : child) sb.append(c).append(" ");

            sb.append("\n");
        }

    }

    public static void main(String[] args) throws Exception {
        // 입력 초기화
        input();
        
        // 로직 실행
        pro();
        
        // 결과 출력
        System.out.println(sb.toString());
    }
    
}