[백준] 1325번 효율적인 해킹 dfs- java

 

원래는 이렇게 생각했었다가 ,4,5가 제일 많이 호출되기 때문에 실패

 

화살표 방향을 원래대로 .

 cnt배열을 static 으로 선언하여, 어떤 노드에 가장 많이 방문하는지로

 

 

• N은 컴퓨터 갯수, M은  간선의 수
• 모든 배열들을 , 1로 시작하는  컴퓨터 숫자와 동일하게 사용하기 위해 선언시 갯수+1로 선언
• static 으로 cnt 선언 => 각 노드에 몇번을 방문했는지 알게해주는 배열
• ArrayList con에 A번째마다 각각 신뢰하는 B들을 넣어주기
• A가 B를 신뢰한다 -> con[A] -> B B B B 
• 이제 for문으로  con ArrayList을 돌게되는데, 
• visited는 con을 돌때마다 초기화를 해줘야 한다. 안그러면 모두가 true로 설정되어있어서 더이상 돌 수 없으니
• con[1] con[2]는 들어가있는게 없으니 돌것이 없고
• con[3] 부터 가능하다.
• con[3]->  1,2, 방문
• con[4] ->1,2,3 방문
•  con[5] -> 1,2,3 방문
• .trim()은 문자열 좌우에서 공백을 제거하는 함수

package 그래프탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.StringTokenizer;

public class B1325_2 {
static int N, M ;
static boolean[] visited;
static ArrayList<Integer> [] con;
static int[] cnt;
	
	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());
		
		cnt=new int[N+1];
		con=new ArrayList[N+1];
	
		for (int A = 1; A <=N; A++) {
			con[A]=new ArrayList<Integer>();
		}
		
		for (int i = 0; i < M; i++) {
			st=new StringTokenizer(br.readLine()," ");
			int A=Integer.parseInt(st.nextToken());
			int B=Integer.parseInt(st.nextToken());
			
			con[A].add(B);
		}
		
		for (int i = 1; i <=N; i++) {
			visited=new boolean[N+1];
			System.out.println(i+"인덱스 돌기 ");
				dfs(i);
		}
		
		StringBuilder sb=new StringBuilder();
		int max=0;
		for (int i = 1; i <=N; i++) {
			if(cnt[i]>max) max=cnt[i];
		}
		for (int i = 1; i <=N; i++) {
			if(max==cnt[i]) sb.append(i+" ");
		}
		System.out.println(sb.toString());
		
}

	private static void dfs(int i) {
		visited[i]=true;
		for(int a: con[i]) {
			if(!visited[a]) {
				cnt[a]++;
			System.out.println("a:"+a+" , cnt["+a+"]="+cnt[a]);
				dfs(a);
			}
		}

	}//dfs
}