[BOJ/JAVA] 백준 1167번 : 트리의 지름

1167번: 트리의 지름

 

 

 

 

---

 

 

 

• 풀이

 

트리의 자료구조 중 임의의 두점의 거리가 가장 먼 거리를 출력해주면되는 문제입니다.

 

먼저, 트리의 연결은 ArrayList 배열을 통해 연결해 주었습니다.

 

그 후, 트리 탐색은 dfs방식을 사용했습니다.

 

첫번째 풀이는 모든 노드들에서 시작해서 모든 노드들을 돌면서 가장 거리의 합이 높은 노드 길이의 합을 게속 초기화 시켜주는 방식을 사용했습니다. 하지만 해당 코드는 시간 초과가 떴습니다. 해당 문제의 제한 시간은 2초이고 최대 노드의 수는 100,000이기때문이였습니다.

 

바꿀 방법을 생각해보니 모든 노드의 시작부터 할 필요가 없었습니다. 실제로 단 두 번의 시작노드를 통해 정답을 뽑아낼 수 있습니다. 단 두번으로 할 수 있는 근거는 트리입니다. 모든 노드들은 연결되어 있습니다. 한 노드에서 시작해서 가장 먼 노드를 초기화시켜준 뒤 가장 먼 노드부터 시작해서 가장 먼 노드를 구해주면 값을 뽑아낼 수 있습니다. 

 

모두 이어져있기 때문에 한 노드에서 가장 먼 노드를 구하면 가장 먼노드부터 그전에 시작한 노드까지의 합과 그전에 시작한 노드부터 두번째로 먼 노드의 합까지 더할 수 있기 때문입니다.

 

 

• 시간초과 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static ArrayList[] node;
	static int answer;
	static boolean[] check;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		int V = in.nextInt();
		node = new ArrayList[V+1];
		check = new boolean[V+1];
		answer = 0;
		
		for(int i = 1; i <= V ;i++)
			node[i] = new ArrayList<Node>();
		
		for(int i = 0; i < V; i++) {
			int now = in.nextInt();
			
			while(true) {
				int nodeNumber = in.nextInt();
				if(nodeNumber == -1) break;
				int distance = in.nextInt();
				
				node[now].add(new Node(nodeNumber, distance));
			}
		}
		
		for(int i = 1; i <= V; i++) {
			check[i] = true;
			bfs(i, 0);
			check[i] = false;
		}
	}
	
	private static void bfs(int now, int sum) {
		if(answer < sum) {
			answer = sum;
		}
		
		for(int i = 0; i < node[now].size(); i++) {
			Node temp = (Node) node[now].get(i);
			
			if(check[temp.x]) continue;
			
			check[temp.x] = true;
			bfs(temp.x, sum + temp.distance);
			check[temp.x] = false;
		}
	}
}

class Node {
	int x;
	int distance;
	
	public Node(int x, int distance) {
		this.x = x;
		this.distance = distance;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}

 

 

• 통과 코드

 

import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	static ArrayList[] node;
	static int answer, max;
	static boolean[] check;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		SetData();
		System.out.println(answer);
	}

	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

		int V = in.nextInt();
		node = new ArrayList[V+1];
		check = new boolean[V+1];
		answer = 0;
		max = 0;
		
		for(int i = 1; i <= V ;i++)
			node[i] = new ArrayList<Node>();
		
		for(int i = 0; i < V; i++) {
			int now = in.nextInt();
			
			while(true) {
				int nodeNumber = in.nextInt();
				if(nodeNumber == -1) break;
				int distance = in.nextInt();
				
				node[now].add(new Node(nodeNumber, distance));
			}
		}
		
		check[1] = true;
		bfs(1, 0);
		check[1] = false;
		
		check[max] = true;
		bfs(max, 0);
	}
	
	private static void dfs(int now, int sum) {
		if(answer < sum) {
			answer = sum;
			max = now;
		}
		
		for(int i = 0; i < node[now].size(); i++) {
			Node temp = (Node) node[now].get(i);
			
			if(check[temp.x]) continue;
			
			check[temp.x] = true;
			bfs(temp.x, sum + temp.distance);
			check[temp.x] = false;
		}
	}
}

class Node {
	int x;
	int distance;
	
	public Node(int x, int distance) {
		this.x = x;
		this.distance = distance;
	}
}

class InputReader {
	private final InputStream stream;
	private final byte[] buf = new byte[8192];
	private int curChar, snumChars;

	public InputReader(InputStream st) {
		this.stream = st;
	}

	public int read() {
		if (snumChars == -1)
			throw new InputMismatchException();
		if (curChar >= snumChars) {
			curChar = 0;
			try {
				snumChars = stream.read(buf);
			} catch (IOException e) {
				throw new InputMismatchException();
			}
			if (snumChars <= 0)
				return -1;
		}
		return buf[curChar++];
	}

	public int nextInt() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public long nextLong() {
		int c = read();
		while (isSpaceChar(c)) {
			c = read();
		}
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		long res = 0;
		do {
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	public int[] nextIntArray(int n) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

	public String nextLine() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString();
	}

	public boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

	private boolean isEndOfLine(int c) {
		return c == '\n' || c == '\r' || c == -1;
	}
}