[DFS] 백준 1325 효율적인 해킹 JAVA

[문제출처 | https://www.acmicpc.net/problem/1325 ]

그래프 이론
그래프 탐색
너비 우선 탐색
깊이 우선 탐색

---

정답비율 안 보고 이번 주 스터디에 제시한 문제...

그래프 탐색 분류에서 실버길래 괜찮지 않을까~ 가져왔는데 일단 테케도 하나뿐이고 보아하니 시간초과나 메모리초과로 꽤나 골치아픈 문제였다.(오답)첫 풀이는 백준 바이러스 문제와 비슷해보여서 단방향 연결로 받는데 이때, 'A가 B를 신뢰할 때 B를 해킹하면 A를 해킹할 수 있다는' 부분에서 B->A 로 접근을 했다.
1. 근접리스트로 B행에 A리스트를 쌓고 ( adjList[b].add(a) )
2. 배열을 돌며 각 행 리스트의 사이즈 값이 큰 인덱스를 찾아(=신뢰되는 경우가 많은 컴퓨터)
3. 배열을 돌며 그 인덱스(컴퓨터)를 신뢰하는 컴퓨터를 바로 출력하면 되지 않나 생각했다.

제공 된 테케를 보고 짰을 때는 답이 나오니 맞을 줄 알았다. (이게 그래프 탐색이라 할 수 있나 하긴했다)
그리고 당연하게 결과는 '틀렸습니다' 빼엠~ ಥ_ಥ

그렇담 일단 DFS 로직으로 접근을 해보자..

바이러스 로직에, 모든 정점에서 타고 들어가봐야하니 1~N번까지 도는 반복문 안에 dfs 함수를 넣어 돌려야 한다.
그리고 방문처리는 매 정점에서 시작이니 이 반복문에서 매번 초기화를 해주고 dfs를 탄다.

dfs 함수에서는 정점을 파라미터로 받아 방문처리와 근접리스트 배열의 한 행에 대한 리스트를 탐색한다.
연결된 컴퓨터를 따라 방문하지 않은(탐색하지 않은) 컴퓨터를 재귀하여 타고 타고 탐색한다.

이때, 그 컴퓨터에 연결된(신뢰된) 수를 저장하는 변수를 두는 것에 아이디어가 부족해서 한참을 빙빙 돌았다..

결국 검색 찬스ˋ( ° ▽、° )! 다른 분들의 풀이를 검색해보는데 나랑 비슷한 접근으로 푸신 분이 계셨다.
(참고 블로그 : https://dev-gorany.tistory.com/95 )
1. 컴퓨터에 연결된 수를 담는 배열을 둔다. ( conn[ ] )
2. 답을 ArrayList로 관리한다.
 2-1. max 값이 갱신되면 적재하던 ArrayList를 초기화하고 다시 쌓는다. ( ans.clear( ) )

그런데 답이 반대로 나와서 왜지 싶다가 adjList[b].add(a) 로 넣었던 부분을 adjList[a].add(b) 로 바꾼 후 제대로 나왔다.

 

---

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

// 통과 10032ms
public class Main_1325 {

	static int N, M, res;
	static boolean[] visited;
	static int[] conn;
	static ArrayList<Integer>[] adjList;
	static ArrayList<Integer> ans;

	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()); // 컴퓨터 1~N
		M = Integer.parseInt(st.nextToken()); // 관계 수
		conn = new int[N+1];
		adjList = new ArrayList[N + 1]; // 1번부터 쓰기 위함
		for (int i = 0; i < adjList.length; i++) {
			adjList[i] = 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());
			adjList[a].add(b);
		}

		for (int i = 1; i <= N; i++) {
			visited = new boolean[N+1];
			dfs(i);
		}
		
		int max = 0;
		ans = new ArrayList<Integer>();
		for (int i = 1; i <= N; i++) {
			if(max < conn[i]) { // 연결된 수 최대값 갱신
				// max 갱신
				max = conn[i];
				// 그간 쌓았던 ans 리스트 초기화
				ans.clear();
				// 현재 인덱스 적재
				ans.add(i);
			} else if(max == conn[i] ){ // 똑같은 최대값일 땐
				// 이어서 적재
				ans.add(i);
			}
		}
		
		for (int a : ans) {
			System.out.print(a + " ");
		}
	}

	private static void dfs(int curr) {
		visited[curr] = true;
		for (int next : adjList[curr]) { // 연결된 컴퓨터를 따라 
			if(!visited[next]) { // 방문하지 않았을 때
				conn[next]++; // 해당 컴퓨터 연결수 증가
				dfs(next); // 타고..타고...
			}
		}
	}

}