Jam's story
[백준] 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
}
'코딩테스트 > 백준' 카테고리의 다른 글
[백준-22871] 징검다리 건너기 -java (0) | 2022.08.12 |
---|---|
[백준] DFS와 BFS - java (0) | 2022.08.10 |
[백준] 2667번 단지번호붙이기 다시풀어보기 (DFS, BFS)- JAVA (0) | 2022.08.07 |
[백준] 나이트의 이동 다시 풀어보기 (BFS) - JAVA (0) | 2022.08.07 |
[백준] 2667번 단지번호 붙이기 - java (0) | 2022.08.05 |
Comments