[BOJ/JAVA] 백준 1939번 : 중량제한

1939번: 중량제한

 

 

---

 

 

• 풀이

 

처음에 백트래킹으로 풀려고 했지만 시간초과가 떴습니다.

M값은 10만이 최대이다. 시간초과가 왜??나는지에 대해서 아직 정확하게 모르겠습니다..

전체적으로 보았을 때 a에서 b로 가는 노드 중 가장 경로 중 가장 작은 값이 가장 큰 경로를 찾으면 되는 문제라 a에서 b로가는 모든 경로를 한번씩만 훑으면 더 빠른것이 아닌가??라는 생각이 들었습니다... (물론, a와 b가 가장 작은 값으로 한번에 연결되어있다면 굳이 모든 노드를 다 돌을 필요가 없지만 이러한 경우의 수 빼고는 다 돌아야되는 것이 맞는 것 아닌가...??!)

 

일단, 해결 풀이 방법은 이분탐색과 bfs를 사용했습니다. (알고리즘 분류를 통해 해결 방법을 찾았습니다.)

이분탐색의 기준은 weight으로 입력 중 최대 중량을 초기화시켜준 뒤 left = 0, right = 최대중량으로 이분탐색을 하며 bfs를 돌았습니다. mid값 보다 bfs를 돌며 큰 값이 있는 경우는 ritght를 mid -1로 초기화 시켜주고 문제가 없을 시 left를 mid + 1로 초기화시켜주었습니다.

 

 

 

• 시간초과 코드 (백트래킹) 

 

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

public class Main {
	static int N, M, answer;
	static ArrayList[] arrayList;
	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);

		N = in.nextInt();
		M = in.nextInt();
		answer = 0;
		arrayList = new ArrayList[N+1];
		check = new boolean[N+1];
		
		for(int i = 1; i <= N; i++)
			arrayList[i] = new ArrayList<Node>();
		
		for(int i = 0; i < M; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			int weight = in.nextInt();
			
			arrayList[a].add(new Node(b, weight));
			arrayList[b].add(new Node(a, weight));
		}
		
		int x = in.nextInt();
		int y = in.nextInt();
		check[x] = true;
		for(int i = 0; i < arrayList[x].size(); i++) {
			Node node = (Node) arrayList[x].get(i);
			
			check[node.a] = true;
			answer = Math.max(answer, dfs(node.weight, node.a, y));
			check[node.a] = false;
		}
	}
	
	private static int dfs(int min, int index, int b) {
		if(index == b) {
			return min;
		}
		
		for(int i = 0; i < arrayList[index].size(); i++) {
			Node node = (Node) arrayList[index].get(i);
			if(check[node.a]) continue;
			check[node.a] = true;
			min = Math.min(dfs(Math.min(min, node.weight), node.a, b),min);
			check[node.a] = false;
		}
		
		return min;
	}
}

class Node {
	int a;
	int weight;
	
	public Node(int a, int weight) {
		this.a = a;
		this.weight = weight;
	}
}

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 int N, M, answer;
	static ArrayList[] arrayList;
	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);

		N = in.nextInt();
		M = in.nextInt();
		answer = 0;
		arrayList = new ArrayList[N+1];
		int max = 0;
		
		for(int i = 1; i <= N; i++)
			arrayList[i] = new ArrayList<Node>();
		
		for(int i = 0; i < M; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			int weight = in.nextInt();
			
			arrayList[a].add(new Node(b, weight));
			arrayList[b].add(new Node(a, weight));
			max = Math.max(weight, max);
		}
		
		int x = in.nextInt();
		int y = in.nextInt();
		
		int left = 0;
		int right = max;
		while(left<= right) {
			int mid = (left + right) / 2;
			
			check = new boolean[N+1];
			
			if(bfs(x,y,mid)) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		
		answer = right;
	}
	
	private static boolean bfs(int start, int end, int weigth) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		check[start] = true;
		
		while(!queue.isEmpty()) {
			int d = queue.poll();
			
			if(d == end) {
				return true;
			}
			
			for(int i = 0 ; i < arrayList[d].size(); i++) {
				Node node = (Node) arrayList[d].get(i);
                if (!check[node.a] && weigth <= node.weight) {
                    check[node.a] = true;
                    queue.add(node.a);
                }
            }
		}
		
		return false;
	}
}

class Node {
	int a;
	int weight;
	
	public Node(int a, int weight) {
		this.a = a;
		this.weight = weight;
	}
}

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;
	}
}