1259. [S/W 문제해결 응용] 7일차 - 금속막대

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

import java.io.BufferedReader; import java.io.File; import java.io.FileReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Hashtable; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; import java.util.StringTokenizer;   class Bar {     int head, tail;       public Bar(int head, int tail) {         this.head = head;         this.tail = tail;     } }   class Solution {       static boolean Debug = false;     static int BarSize;       private static int T;     private static int MaxCount;     private static Queue<Integer> AnswerQueue;       private static ArrayList<Bar> bList;     private static int[] visited;     private static int[] headInfo;       public static void main(String args[]) throws Exception {           BufferedReader br;         if (Debug) {             // C:\Users\wvimi\Downloads\input (2).txt             File f = new File("디렉토리", "input (2).txt");             FileReader reader = new FileReader(f);             br = new BufferedReader(reader);         } else {             br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용         }           StringTokenizer st;           int TestSize = Integer.parseInt(br.readLine());         for (T = 1; T <= TestSize; T++) {               // BarSize ;             st = new StringTokenizer(br.readLine());             BarSize = Integer.parseInt(st.nextToken());               // 초기화             visited = new int[BarSize];             headInfo = new int[BarSize];             bList = new ArrayList<>();               //             Hashtable<Integer, Integer> startList = new Hashtable<>();                           // 시작의 경우의 수             Bar item;             int head, tail;             st = new StringTokenizer(br.readLine());             for (int i = 0; i < BarSize; i++) {                 head = Integer.parseInt(st.nextToken());                 tail = Integer.parseInt(st.nextToken());                                   item = new Bar(head, tail);                 bList.add(item);                 headInfo[i] = head;                               }               // 완전탐색             MaxCount = 0;             AnswerQueue = new LinkedList<>();             for(int i=0; i <BarSize; i++) {                 findPath(i);             }                           // log(MaxStack.toString());                           // 값 출력             int index;             Bar bar;             String result = String.format("#%d", T);             while(!AnswerQueue.isEmpty()) {                 index = AnswerQueue.poll();                 bar = bList.get(index);                 result += String.format(" %d %d", bar.head, bar.tail);             }               System.out.println(result);         }       }       static Stack<Integer> bStack = new Stack();     private static void findPath(int index) {         visited[index] = 1;         bStack.add(index);           boolean isLast = true;         int tail = bList.get(index).tail;         for (int i = 0; i < BarSize; i++) {             if (visited[i] == 0 && headInfo[i] == tail) {                 findPath(i);                 isLast = false;             }         }                   if(isLast) {             // log("완성: " + bStack.toString());             if(MaxCount < bStack.size()) {                 MaxCount = bStack.size();                                   AnswerQueue.clear();                 AnswerQueue.addAll(bStack);             }         }           visited[index] = 0;         bStack.pop();     }           private static void log(String input) {         if (Debug) {             System.out.println(input);         }     }       private static void log(String input, Object... args) {         if (Debug) {             System.out.println(String.format(input, args));         }     }   }