1849. 영준이의 무게측정 [Fail : 오답]

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

import java.util.StringTokenizer;

class Edge {

int start, end;

int weight;

public Edge(int start, int end, int weight) {

this.start = start;

this.end = end;

this.weight = weight;

}

}

class Node<T> extends ArrayList<T> {

public static Node[] Tree;

public int nodeNo;

public int parentNo;

public int rank;

public void makeSet(int x) {

nodeNo = x;

parentNo = x;

rank = 0;

}

public int findSet() {

Stack<Integer> nodeStack = new Stack<>();

nodeStack.add(nodeNo); // 검색 노드 조건

Node moveNode = Tree[nodeNo];

while (moveNode.nodeNo != moveNode.parentNo) { // 부모 노드 조건

moveNode = Tree[moveNode.parentNo];

nodeStack.add(parentNo);

}

if (nodeStack.size() > 1) { // 찾은 부모가 있다면

int represent = moveNode.nodeNo;

while (!nodeStack.isEmpty()) { // 부모노드를 가르키도록

Tree[nodeStack.pop()].parentNo = represent;

}

}

return moveNode.nodeNo;

}

public void unionSet(Node<T> node) {

Node first = Tree[this.nodeNo];

Node second = Tree[node.nodeNo];

int f = first.findSet();

int s = second.findSet();

if (f == s) {

return;

}

first = Tree[f];

second = Tree[s];

if (first.rank > second.rank) {

second.parentNo = first.nodeNo;

} else {

first.parentNo = second.nodeNo;

if (this.rank == node.rank) {

node.rank++;

}

}

}

}

class Solution {

static int DATA_SIZE;

static Node<Edge>[] tree;

static Boolean isFound;

static int[] visited;

static int[] distance;

static boolean Debug = true;

public static void main(String args[]) throws Exception {

BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "input (29).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in));

}

StringTokenizer st;

int start, end, weight;

int testNo = Integer.parseInt(br.readLine());

for (int T = 1; T <= 6; T++) {

st = new StringTokenizer(br.readLine());

int nodeNum = Integer.parseInt(st.nextToken());

int taskNum = Integer.parseInt(st.nextToken());

StringBuffer sb = new StringBuffer();

System.out.print(String.format("#%d", T, nodeNum, taskNum));

log("");

tree = new Node[nodeNum + 1];

visited = new int[nodeNum + 1];

distance = new int[nodeNum + 1];

Node.Tree = tree;

for (int i = 0; i < tree.length; i++) {

tree[i] = new Node<Edge>();

tree[i].makeSet(i);

}

// [방법2]

ArrayList<Integer> representList = new ArrayList<>();

for (int i = 0; i < taskNum; i++) {

st = new StringTokenizer(br.readLine());

switch (st.nextToken()) {

case "!":

start = Integer.parseInt(st.nextToken());

end = Integer.parseInt(st.nextToken());

weight = Integer.parseInt(st.nextToken());

tree[start].add(new Edge(start, end, weight));

tree[end].add(new Edge(end, start, -1 * weight));

tree[start].unionSet(tree[end]);

break;

case "?":

start = Integer.parseInt(st.nextToken());

end = Integer.parseInt(st.nextToken());

// findPath(start, end);

int a = tree[start].findSet();

int b = tree[end].findSet();

if (a == b) {

// [방법2 ] 무게의 상대값을 기록하여 재활용하기

// if(!representList.contains((Integer) a)) {

// representList.add(a);

// visited = new int[nodeNum + 1];

// distance = new int[nodeNum + 1];

// }

int w_end = findWeight(end);

int w_start = findWeight(start);

int answer = w_end - w_start;

sb.append(String.format(" %d", answer));

} else {

sb.append(" UNKOWN");

}

break;

}

}

System.out.println(sb.toString());

}

}

private static int findWeight(int nodeNo) {

if (visited[nodeNo] == 1) {

log(String.format("3. distance[%d] = %d", nodeNo, distance[nodeNo]));

return distance[nodeNo];

}

// 연결된 노드를 찾는다.

int subParent = 0;

Queue<Integer> que = new LinkedList();

que.add(nodeNo);

Stack<Integer> visiting = new Stack();

while (!que.isEmpty()) {

int reStart = que.poll();

log(String.format("nodeNo:%d    reStart: %d", nodeNo, reStart));

for (Edge line : tree[reStart]) {

log(String.format("visited[%d] = %d", line.end, visited[line.end]));

if (visited[line.end] == 1 || line.end == tree[nodeNo].parentNo) {

// 무게가 기록된 연결된 노드를 찾음 || 부모노드

subParent = line.end;

break;

}

que.add(line.end);

visited[line.end] = 1;

visiting.add(line.end);

}

}

for (int i : visiting) {

visited[i] = 0;

}

que = new LinkedList();

que.add(subParent);

log("subParent 진입: " + subParent);

while (!que.isEmpty()) {

int reStart = que.poll();

for (Edge line : tree[reStart]) {

if (visited[line.end] == 1) {

continue;

}

// que.add(line.end);

que.add(line.end);

visited[line.end] = 1;

distance[line.end] = distance[line.start] + line.weight;

log(String.format("2. distance[%d] = %d", line.end, distance[line.end]));

if (line.end == nodeNo) {

return distance[line.end];

}

}

}

return -1;

}

private static void log(String input) {

if (true) {

System.out.println(input);

}

}

}