백준1325. 효율적인 해킹 DFS, BFS

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

문제제목 : 효율적인 해킹

문제유형 : BFS, DFS

문제난이도 : 실버2

문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

아이디어

1. 처리해야할 간선의 수가 많으면 BFS가 더 효율적이다.

2. 방문하게 되는 노드의 개수를 계산해서 가장 큰 시작 정점을 출력한다.

 

제출통과코드DFS

package week4;

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

public class BOJ1325_DFS {
	private static ArrayList<Integer>[] adj;
	private static int N, M;
	private static boolean[] visited;
	private static int[] countArray; // 각 인덱스번호의 컴퓨터 해킹시 해킹가능 컴퓨터 수
	

	public static void main(String[] args) throws Exception {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		adj = new ArrayList[N + 1]; 
		
		// 인접리스트 객체 변수 초기화
		for (int i = 0; i <= N; i++) {
			adj[i] = new ArrayList<Integer>();
		}
		
		countArray = new int[N + 1];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj[a].add(b);
		}
		
		for (int i = 1; i <= N; i++) {
			visited = new boolean[N + 1];
			DFS(i);
		}

		// 가장 많은 해킹을 한 수
		int max_value = 0;
		for (int i = 1; i <= N; i++) {
			max_value = Math.max(max_value, countArray[i]);
		}
		
		for (int i = 1; i <= N; i++) {
			if (max_value == countArray[i]) {
				sb.append(i + " ");
			}
		}
		 System.out.println(sb.toString());
	}
	
	public static void DFS(int start) {
		if (visited[start]) return;
		visited[start] = true;
		for (int x : adj[start]) {
			if (!visited[x]) {
				countArray[x]++;
				DFS(x);
			}
		}	
	}
}

시간초과코드DFS

package week4;

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

public class BOJ1325_DFS {
	private static ArrayList<Integer>[] adj;
	private static int N, M;
	private static boolean[] visited;
	private static int count;
	private static int[] countArray; // 각 인덱스번호의 컴퓨터 해킹시 해킹가능 컴퓨터 수
	

	public static void main(String[] args) throws Exception {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		adj = new ArrayList[N + 1]; 
		
		// 인접리스트 객체 변수 초기화
		for (int i = 0; i <= N; i++) {
			adj[i] = new ArrayList<Integer>();
		}
		
		countArray = new int[N + 1];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			adj[b].add(a);
		}
		
		for (int i = 1; i <= N; i++) {
			visited = new boolean[N + 1];
			count = 0;
			DFS(i);
			countArray[i] = count;
		}

		// 가장 많은 해킹을 한 수
		int max_value = 0;
		for (int i = 1; i <= N; i++) {
			max_value = Math.max(max_value, countArray[i]);
		}
		
		for (int i = 1; i <= N; i++) {
			if (max_value == countArray[i]) {
				sb.append(i + " ");
			}
		}
		 System.out.println(sb.toString());
	}
	
	public static void DFS(int start) {
		if (visited[start]) return;
		visited[start] = true;
		for (int x : adj[start]) {
			if (!visited[x]) {
				count++;
				DFS(x);
			}
		}	
	}
}

 

이 코드는 왜 시간초과가 날까.... 

블로그에서 다른 사람들이 통과한 코드를 참고해봐도 위에 통과한 코드와 차이점이라고는 감염 시작점으로부터 감염되는 컴퓨터 수를 count에 저장해서 정점의 DFS가 끝난 후 countArray[] 에 값을 넣어준 것 뿐인데...........

이게 실행시간에 큰 영향이 있는 건가.... 아니면 내가 아직 모르는 부분에서 실행시간이 너무 많이 소요되는걸까..

조금 더 알아보도록 해야겠다... 물어볼 곳이 없다..........누가...알려줘.......

 

 

코드BFS

package week4;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ1325_BFS {

	private static int N, M;
	private static ArrayList<Integer> adj[];
	private static boolean visited[];
	private static int countArr[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		adj = new ArrayList[N + 1];
		countArr = new int[N + 1];
		
		for (int i = 0; i <= N; i++) {
			adj[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			adj[a].add(b); // 도착노드, 출발노드 (b가 감염되면 a이 감염)
		}
		
		for (int i = 1; i <= N; i++) {
			visited = new boolean[N + 1];
			BFS(i);
		}
		
		int max = 0;
		for (int i = 1; i <= N; i++) {
			max = Math.max(max, countArr[i]);
		}
		
		for (int i = 1; i <= N; i++) {
			if (countArr[i] == max) {
				sb.append(i + " ");
			}
		}
		
		System.out.println(sb.toString());
	}
	
	
	
	public static void BFS(int start) {
		if (visited[start]) return;

		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		visited[start] = true;
		
		while(!queue.isEmpty()) {
			int num = queue.poll();
			for (int value : adj[num]) { //주의
				if (!visited[value]) {
					queue.add(value);
					visited[value] = true;
					countArr[value]++; // 현재 노드에 도달할 수 있는 노드 수를 증가
				}
			}
		}
	}
}

1. countArr에는 해당 노드에 도달할 수 있는 노드의 수를 말한다. 

3 이 1과2 를 신뢰하고 4는 3을 신뢰, 5도 3을 신뢰한다고 했을 때

1을 해킹하면 3이 해킹되고, 2를 해킹하면 3이 해킹된다.

3을 해킹하면 4가 해킹되고, 5도 해킹된다.

 

1 |
2 |
3 | 1-> 2 ->
4 | 3->
5 | 3->
===1번 정점 시작===
poll 1
===1끝===
===2번 정점 시작===
poll 2
===2끝===
===3번 정점 시작===
poll 3
add 1
add 2
poll 1
poll 2
===3끝===
===4번 정점 시작===
poll 4
add 3
poll 3
add 1
add 2
poll 1
poll 2
===4끝===
===5번 정점 시작===
poll 5
add 3
poll 3
add 1
add 2
poll 1
poll 2
===5끝===
3 3 2 0 0
1 2

 

 

하... 좀 어렵다 ...