We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
그 이유가 궁금합니다.
그리고 강사님은 조합을 하셨는데 시간복잡도를 n의 제곱이라고 설명하셨습니다.
package codingTest.two; import java.io.*; import java.util.*; public class 호석이두마리치킨 { static FastReader scan = new FastReader(); static StringBuilder sb = new StringBuilder(); static class Ans implements Comparable<Ans> { public int a; public int b; public Ans(int a, int b) { this.a = a; this.b = b; } @Override public int compareTo(Ans o) { if (this.a != o.a) return this.a - o.a; return this.b - o.b; } } static int N; static int M; static ArrayList<Integer>[] adj; static int[] d; static boolean[] visit; static int[] sel; static ArrayList<Ans> ansArrayList = new ArrayList<>(); static void input() { N = scan.nextInt(); M = scan.nextInt(); adj = new ArrayList[N + 1]; visit = new boolean[N + 1]; d = new int[N + 1]; sel = new int[4]; for (int i = 1; i <= N; i++) adj[i] = new ArrayList<>(); for (int i = 0; i < M; i++) { int x = scan.nextInt(); int y = scan.nextInt(); adj[x].add(y); adj[y].add(x); } } static int ans = Integer.MAX_VALUE; static void bruteForce (int x, int cnt) { if (cnt == 3) { if (ans >= bfs(sel[1], sel[2])) { ans = bfs(sel[1], sel[2]); if (sel[1] < sel[2]) { ansArrayList.add(new Ans(sel[1], sel[2])); } else { ansArrayList.add(new Ans(sel[2], sel[1])); } } return; } for (int i = x + 1; i <= N; i++) { sel[cnt] = i; cnt += 1; bruteForce(i , cnt); sel[cnt] = 0; cnt -= 1; } } static int bfs(int x, int y) { Queue<Integer> queue = new LinkedList<>(); //init queue.add(x); queue.add(y); for (int i = 1; i <= N; i++) { visit[i] = false; d[i] = 0; } visit[x] = true; visit[y] = true; // start while (! queue.isEmpty()) { int p = queue.poll(); for (Integer z : adj[p]) { if (visit[z]) continue; queue.add(z); visit[z] = true; d[z] = d[p] + 1; } } int sum = 0; for (int i = 1; i <= N; i++) { sum += d[i]; } return sum * 2; } public static void main(String[] args) { input(); bruteForce(0 , 1); Collections.sort(ansArrayList); Ans ans1 = ansArrayList.get(0); sb.append(ans1.a).append(' ').append(ans1.b).append(' '); sb.append(ans); System.out.println(sb); } static class FastReader { BufferedReader br; StringTokenizer st; public FastReader() { br = new BufferedReader(new InputStreamReader(System.in)); } public FastReader(String s) throws FileNotFoundException { br = new BufferedReader(new FileReader(new File(s))); } String next() { while (st == null || !st.hasMoreElements()) { try { st = new StringTokenizer(br.readLine()); } catch (IOException e) { e.printStackTrace(); } } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } String nextLine() { String str = ""; try { str = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return str; } } }
The text was updated successfully, but these errors were encountered:
Stale issue message
Sorry, something went wrong.
No branches or pull requests
그 이유가 궁금합니다.
그리고 강사님은 조합을 하셨는데 시간복잡도를 n의 제곱이라고 설명하셨습니다.
![image](https://user-images.githubusercontent.com/108928206/218256414-ff9f2c81-bb56-4025-bfdf-346c22c82109.png)
The text was updated successfully, but these errors were encountered: