Jam's story

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

코딩테스트/백준

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

애플쩀 2022. 8. 9. 08:41

 

원래는 이렇게 생각했었다가 ,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
}
Comments