https://www.acmicpc.net/problem/1325

해설

이 문제는 전형적인 그래프에 BFS를 돌리는 문제입니다.

다만, 문제 조건에 따라 a -> b 로 그래프의 방향을 두는것이 나닌 b -> a 로 그래프 방향을 추가하여야 신뢰할 수 있는 컴퓨터 간의 관계를 올바르게 사용할 수 있습니다.

 

또한 이 문제 같은경우 JAVA로 BFS를 풀이하면, 시간초과가 난다는 리뷰들이 존재하는데, 저 또한 계속해서 해당 문제에 대해 시간초과가 존재하지만, BufferedReader, static 과 같은 해결방법을 사용하려 해도 해결되지 않아 일단은 이 상태로 제출하였으니 참고 부탁드립니다.

 

시간초과를 해결한 방법은, A->B로 갈떄마다 cache[B] += 1 로 하여 B의 자식노드를 갱신시킨 것 입니다.

처음에 시간초과가 난 방식은, A->B 로 가면, 저는 B->A로 가도록하여 B의 자식노드 개수가 몇개인지 Counting 했습니다.

하지만 그 대신에 A에서 B노드로 올라가도록 처리하면 더 빠르게 처리합니다.

명확한 이유는 모르겠지만, DFS 입장에서 자식 노드가 분기되면서 모든 자식을 방문하는 것보다는 하나의 자식노드가 각각 부모노드로 올라가는게 DFS의 깊이가 더 작아지리라는 것을 생각할 수 있습니다.

명확한 이유를 찾지 못하여서 이유를 만들어서 찾아낸 것 같습니다. 알 수가 없네요.

코드

정답코드1입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static ArrayList<Integer>[] graph = new ArrayList[10001];
	static PriorityQueue<Integer> pq = new PriorityQueue<>();
	static ArrayList<Integer> answerArr = new ArrayList<>();
	static int[] cache = new int[10001];
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		Arrays.fill(cache, -1);
		for(int i=0;i<N; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken()) - 1;
			int B = Integer.parseInt(st.nextToken()) - 1;
			
			graph[A].add(B);
		}
		
		for(int i=0;i<N; i++) {
			BFS(i, new boolean[N]);
		}
		
		for(int i=0;i<N; i++) {
			answer = Math.max(answer, cache[i]);
		}
		for(int i=0;i<N; i++) {
			if(answer == cache[i]) sb.append(i + 1).append(" ");
		}
		System.out.println(sb);
	}
	
	static void DFS(int now, boolean[] visited) {
		visited[now] = true;
		int ret = 0;
		for(int connected = 0; connected < graph[now].size(); connected++) {
			int nextNode = graph[now].get(connected);
			if(visited[nextNode] == true) continue;
			cache[nextNode]++;
			DFS(nextNode, visited);
		}
		
		return ;
	}
	
	static void BFS(int now, boolean[] visited) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(now);
		visited[now] = true;
		
		while(!q.isEmpty()) {
			now = q.poll();
			for(int connected = 0; connected < graph[now].size(); connected++) {
				int nextNode = graph[now].get(connected);
				if(visited[nextNode] == true) continue;
				visited[nextNode] = true;
				cache[nextNode]++;
				q.offer(nextNode);
			}
		}
	}
	
}

 

시간초과 나는 BFS코드입니다.

import java.util.*;
 
 
public class Main {
	
	public static int N,M;
	public static ArrayList<ArrayList<Node>> nodes = new ArrayList<>();
	public static int[] answer;
	public static boolean[] visited;
	public static int cnt=0;
	public static int max = 0;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N=sc.nextInt();
    	M=sc.nextInt();
    	answer = new int[N+1];
    	
    	for(int i=0;i<=N;i++) {
    		nodes.add(new ArrayList<>());
    	}
    	
    	for(int i=0;i<M;i++) {
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		nodes.get(b).add(new Node(a));
    	}
    	
    	for(int i=1;i<=N;i++) {
    		visited = new boolean[N+1];
    		cnt = 0;
    		BFS(i);
    		answer[i] = cnt;
    		max = Math.max(max,  cnt);
    	}
    	
    	for(int i=1;i<=N;i++) {
    		if(answer[i] == max)
    			System.out.print(i+" ");
    	}
    }
    public static void BFS(int start) {
    	Queue<Integer> q = new LinkedList<>();
    	q.offer(start);
    	visited[start] = true;
    	
    	while(!q.isEmpty()) {
    		int startNode = q.poll();
    		for(int i=0;i<nodes.get(startNode).size();i++) {
    			int endNode = nodes.get(startNode).get(i).nodeB;
    			
        		if(visited[endNode] == false) {
        			q.offer(endNode);
        			visited[endNode] = true;
        			cnt+=1;
        		}    			
    		}
    	}
    }
}
 
class Node {
	int nodeB;
	public Node(int nodeB) {
		this.nodeB = nodeB;
	}
}

 

DFS + 메모이제이션을 사용할시 2%에서 틀립니다.

아래의 경우 메모이제이션을 적용할 수 있지 않을까 해서 적용했는데, 최적 부분구조가 성립하지 않는 것으로 보입니다.

이유는, A->B 단방향그래프가 B->A로도 가능한 경우가 존재하기 때문인 것 같습니다.

만약 메모이제이션을 뺼 경우, 시간초과가 발생하고 틀리지는 않습니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static ArrayList<Integer>[] graph = new ArrayList[10001];
	static PriorityQueue<Integer> pq = new PriorityQueue<>();
	static ArrayList<Integer> answerArr = new ArrayList<>();
	static int[] cache = new int[10001];
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		Arrays.fill(cache, -1);
		for(int i=0;i<N; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken()) - 1;
			int B = Integer.parseInt(st.nextToken()) - 1;
			
			graph[B].add(A);
		}
		
		for(int i=0;i<N; i++) {
			int temp = DFS(i, new boolean[N]);
			
			if(answer < temp) {
				answer = temp;
				answerArr.clear();
				answerArr.add(i);
			}else if(answer == temp) {
				answerArr.add(i);
			}
		}
		
		for(int v : answerArr) {
			sb.append(v+1).append(" ");
		}
		System.out.println(sb);
	}
	
	static int DFS(int now, boolean[] visited) {
		if(cache[now] != -1) return cache[now];
		visited[now] = true;
		
		int ret = 0;
		for(int connected = 0; connected < graph[now].size(); connected++) {
			int nextNode = graph[now].get(connected);
			if(visited[nextNode] == true) continue;
			ret += DFS(nextNode, visited) + 1;
		}
		
		return cache[now] = ret;
	}
	
}

 

메모이제이션을 제거하고 DFS로만 진행할시 시간초과 발생하는 코드입니다.

순서가 강제되도록 만들어서 최적 부분구조가 성립한다 생각했지만, 코드의 방향 그래프에 따라 순서가 달라질 수 있으므로 적용이 안됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static ArrayList<Integer>[] graph = new ArrayList[10001];
	static PriorityQueue<Integer> pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		for(int i=0;i<N; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken()) - 1;
			int B = Integer.parseInt(st.nextToken()) - 1;
			
			graph[B].add(A);
		}
		
		for(int i=0;i<N; i++) {
			int temp = DFS(i, new boolean[N]);
			if(answer < temp) {
				answer = temp;
				pq.clear();
				pq.offer(i);
			}else if(answer == temp) {
				pq.offer(i);
			}
		}
		
		for(int v : pq) {
			System.out.print( (v+1) +" ");
		}
	}
	
	static int DFS(int now, boolean[] visited) {
		visited[now] = true;
		int ret = 0;
		for(int connected = 0; connected < graph[now].size(); connected++) {
			int nextNode = graph[now].get(connected);
			if(visited[nextNode] == true) continue;
			ret += DFS(nextNode, visited) + 1;
		}
		
		return ret;
	}
	
}

 

'알고리즘 > 백준' 카테고리의 다른 글

[백준] 2667 단지번호붙이기 - BFS(넓이우선탐색) JAVA  (0) 2023.06.14
[백준] 2178 미로 탐색 - BFS(넓이우선탐색) JAVA  (0) 2023.06.12
[백준] 1260 DFS와 BFS - DFS(깊이우선탐색) + BFS(넓이우선탐색) JAVA  (0) 2023.06.11
[백준] 2606: 바이러스 - BFS(너비우선탐색) + 유니온 파인드(UnionFind, Disjoint set) JAVA  (0) 2023.06.11
[백준] 9663 N-Queen - 브루트포스(BruteForce) + 시간초과(TimeOut) JAVA  (0) 2022.07.11

+ Recent posts

티스토리툴바