백준 23059 (리그 오브 레게노) - java

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

 

문제

백남이는 새 학기를 맞이하여, 리그 오브 레게노(League of Legeno)라는 게임을 시작했다. 리그 오브 레게노는 AOS(Aeon of Strife) 종류의 게임으로, 5명의 플레이어가 한 팀이 되어 상대편의 주요 건물을 부수는 것이 게임의 승리 목표이다. 게임 내에서 유저들은 게임에서 승리하기 위해 자신의 캐릭터의 능력치를 올리도록 해야 한다. 맵에 등장하는 몬스터나 상대 팀의 플레이어를 처치하며 경험치와 골드를 보상으로 얻고, 이 경험치를 통해 캐릭터의 레벨을 올림으로써 레벨 증가에 따른 능력치를 얻게 된다. 그러나 한 게임에서 레벨에 대한 일정 상한선이 존재한다. 다른 방법으로는 골드를 사용하여 아이템들을 구매함으로써 자신의 능력치를 높일 수 있다.

아이템 사이에 미리 정해진 구매 순서가 존재한다. 이제 막 게임을 시작한 백남이는 구매 순서 전체가 아니라 두 아이템 사이의 선후관계 일부만 알고 있다. 백남이가 다음 과정을 반복하여 아이템을 구매할 때, 아이템의 전체 구매 순서를 알아내자.

• 현재 구매할 수 있는 아이템 중 아직 구매하지 않은 아이템을 모두 찾는다.
• 찾은 아이템을 사전 순으로 모두 구매한다.

유형 : 위상 정렬 + 해시

 

접근 방식

• 하위 아이템을 구매하여 상위 아이템을 구매하는 방식이기 때문에 위상 정렬로 해결할 수 있다.
• 다만 아이템의 정보가 문자열로 주어지기 때문에 각 노드 번호에 해당 하는 정보를 얻기 위해 HashMap을 사용해야 한다.

 

전체 코드

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

public class Main {

    static int[] count;
    static int n;
    static HashMap<String,Integer> map = new HashMap<>();
    static HashMap<Integer,String> map2 = new HashMap<>();
    static ArrayList<Integer>[] graph;

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

        count = new int[2*n + 1];

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

        int number = 1;

        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            String s1 = st.nextToken();
            String s2 = st.nextToken();

            int tmpNumF = 0;
            if(!map.containsKey(s1)) {
                tmpNumF = number;
                map.put(s1,tmpNumF);
                map2.put(tmpNumF,s1);
                number++;
            }else {
                tmpNumF = map.get(s1);
            }

            int tmpNumS = 0;
            if(!map.containsKey(s2)) {
                tmpNumS = number;
                map.put(s2,tmpNumS );
                map2.put(tmpNumS,s2);
                number++;
            }else {
                tmpNumS = map.get(s2);
            }

            graph[tmpNumF].add(tmpNumS);
            count[tmpNumS]++;
        }

        Queue<Turn> q = new ArrayDeque<>();
        for(int i = 1 ; i < number ; i++) {
            if(count[i] == 0) {
                q.add(new Turn(i,0));
            }
        }

        PriorityQueue<Turn> pq = new PriorityQueue<>(
                (x,y) -> {
                    if(x.turn == y.turn)
                        return map2.get(x.cur).compareTo(map2.get(y.cur));

                    return x.turn - y.turn;}
        );

        int findNum = 0;
        int[] turn = new int[number + 1];

        while(!q.isEmpty()) {
            Turn cur = q.poll();
            findNum++;
            pq.add(new Turn(cur.cur,cur.turn));

            for(int next : graph[cur.cur]) {
                count[next]--;
                turn[next] = Math.max(turn[next],cur.turn + 1);

                if(count[next] == 0) {
                    q.add(new Turn(next,turn[next]));
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        if(findNum != number - 1){
            sb.append("-1\n");
        }else {
            while (!pq.isEmpty()) {
                sb.append(map2.get(pq.poll().cur)).append("\n");
            }
        }

        System.out.print(sb);

        br.close();
    }

    static class Turn {
        int cur;
        int turn;

        Turn(int cur,int turn) {
            this.cur = cur;
            this.turn = turn;
        }
    }
}