[백준 - Java] 1325번 : 효율적인 해킹 (자바는 시간초과!!!!)

문제

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

설명

스캐너로 입력받고, LinkedList로 누가누가 신뢰하는지 정점 연결해주고, dfs 재귀로 돌려서 구현했다.

dfs 돌면서 가장 많은 정점(컴퓨터)을 거친 컴퓨터가 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터가 됨.

시간 초과

 

버퍼 리더, 라이터 써서 입출력을 받았다.

시간 초과

 

누가 링크드 리스트 쓰면 시간 초과 난 데서 어레이 리스트로 변경

시간 초과

 

그리고 이 문제 해결한 스터디 팀원은 자기 코드가 맞았습니다! 가 뜨긴 하는데 가끔 시간 초과도 뜬다고 함;;;같은 코든데...

 

또!!! C++인가 암튼 자바 말고 다른 언어로 푼 사람들은 자바보다 훨씬 빠른 속도로 정답 처리됨

자바만 시간 초과가 오지게 나는 듯

 

뭐 때문인지 모르겠다 이마리야!!!!!!

 

그래도 다른 블로그의 포스팅과 스터디 팀원의 코드를 분석한 결과로 성공하긴 했다.

그리고 내 코드는 왜 비슷한데 안되는지 한 번 추측해보았다.

 

우선 시간 초과 나는 이전 코드 (시간 초과 코드)

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

public class Main {
	public static ArrayList<Integer>[] adjList;
	public static boolean[] visited;
	public static int[] result;
	public static int count = 0;
	public static int max = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		adjList = new ArrayList[N + 1];
		result =  new int[N+1];

		// 인접 리스트 만들기 
		for (int i = 0; i <= N; 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[b].add(a);
		}

		// 1번 컴퓨터부터 dfs로 인접한 신뢰 컴퓨터 찾기 
		for(int i = 1; i <= N; i++) {
			visited = new boolean[N + 1];
			dfs(i);
			//System.out.println("\ni : " + i + ", value : " + count + "\n");
			result[i] = count;
			max = Math.max(max, count);
			count = 0;
		}

		// max값 가진 컴퓨터 출력 
		for(int i = 1; i <= N; i++) {
			if(result[i] == max) {
				bw.write(i + " ");
			}
		}

		bw.flush();
		bw.close();
	}

	public static void dfs(int v) {
		visited[v] = true;
		count++;
		//System.out.print(v + " ");

		Iterator<Integer> iter = adjList[v].listIterator();
		while (iter.hasNext()) {
			int w = iter.next();
			if (!visited[w]) { 
				dfs(w);
			}
		}
	}

}

 

1번 예제를 넣고 돌려보면

아래와 같이 콘솔에 찍힌다.

 

A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있기에 B->A로 연결 리스트를 만들었다. (ex. adjList [b]. add(a);)

dfs를 돌면서 인접한 정점을 만날 때마다 count변수를 +1 해주고, 이를 바탕으로 4개의 컴퓨터를 해킹시키는 1번과 2번을 정답으로 출력

 

1 3 4 5 
i : 1, value : 4

2 3 4 5 
i : 2, value : 4

3 4 5 
i : 3, value : 3

4 
i : 4, value : 1

5 
i : 5, value : 1

1 2 

 

성공한 스터디 팀원의 코드 (성공 코드)

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

public class Main {
	
	static int[] computer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<Integer>[] list = new ArrayList[N + 1];
		
		for (int i = 1; i <= N; i++) {
			list[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());
			
			list[a].add(b);
		}
		
		//각 컴퓨터(정점)별로 해킹할 수 있는 컴퓨터 수를 셈 -> 그 중에 최대값을 가진 컴퓨터를 출력
		computer = new int[N + 1];
		int max = Integer.MIN_VALUE;
		for (int i = 1; i <= N; i++) {
			boolean[] visited = new boolean[N + 1];
			dfs(i, visited, list);
			System.out.println();
		}
		
		//최대로 해킹할 수 있는 컴퓨터 수를 구함
		for (int i = 1; i <= N; i++) {
			max = Math.max(max, computer[i]);
		}
		
		//가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터가 여러개일수도 있기 때문에 for문을 돌면서 각 컴퓨터 번호를 출력
		for (int i = 1; i <= N; i++) {
			//System.out.println("i : " + i + ", value : " + computer[i] + "\n");
			if (computer[i] == max) {
				bw.write(i + " ");
			}
		}
		
		bw.flush();
		bw.close();
	}
	
	public static void dfs(int start, boolean[] visited, ArrayList<Integer>[] list) {
		visited[start] = true;
		//System.out.print(start + " ");

		for (int node : list[start]) {
			if (!visited[node]) {
				computer[node]++;
				dfs(node, visited, list);
			}
		}
		
	}

}

 

1 
2 
3 1 2 
4 3 1 2 
5 3 1 2 
i : 1, value : 3

i : 2, value : 3

i : 3, value : 2

i : 4, value : 0

i : 5, value : 0

1 2 

 

 

dfs로 똑같이 인접한 정점들을 돌지만 나처럼 count 변수를 ++ 시키는 것이 아니라 아예 인덱스에 해당하는 배열의 값을 ++해줌

그리고 나는 B->A로 인접 리스트에 넣어주었는데 A->B로 인접리스트에 넣어줌.

왜 저렇게 하면 되는 거지....? 내 코드에서 어떤 점이 팀원의 코드보다 더 시간이 걸리는 요인이 되었던 걸까...

 

굳이 따져본다면 팀원은 값이 3 + 3 + 2로 ++횟수가 8이라면

나는 4 +4 + 3 + 1 + 1로 카운트 횟수가 13이라설까....?

이렇게 카운트해주는 것도 시간 복잡도에 그렇게 많은 영향을 미치나?

모르겠다ㅜㅜㅜㅜ

 

암튼 성공한 팀원의 코드를 좀 더 정리해보겠다.

 

설명

팀원은 나처럼 B->A가 아니라 A->B로 인접 리스트를 구현했다.

첨에 왜 저렇게 넣는 거지? 생각했는데 조삼모사다.

 

dfs를 통해 시작 정점부터 탐색을 한다.

dfs함수에서 dfs를 다시 호출하는 즉, 정점에 대해 재귀 함수가 호출되는 횟수는 해킹할 수 있는 컴퓨터의 개수와 동일하다는 것이다.

 

자세한 내용은 https://mygumi.tistory.com/337 이 블로그를 참고하면 좋을 것 같다!!!

 

즉! 시작 정점을 지나 탐색되는 인접한 정점들은 시작 정점을 해킹할 수 있다.

1번 입력 예시를 바탕으로 예를 들어보자.

5번 정점을 시작으로 dfs를 돌면서 인접한 3번 정점에 들렸다. -> 3번 정점으로 5번 정점은 해킹될 수 있다. (5번이 3번을 신뢰하닌까!)

5번 정점을 시작으로 dfs를 돌면서 인접한 1번 정점에 들렸다. -> 1번 정점으로 5번 정점은 해킹될 수 있다.

5번 정점을 시작으로 dfs를 돌면서 인접한 2번 정점에 들렸다. -> 2번 정점으로 5번 정점은 해킹될 수 있다. 

 

public static void dfs(int start, boolean[] visited, ArrayList<Integer>[] list) {
		visited[start] = true;
		//System.out.print(start + " ");

		for (int node : list[start]) {
			if (!visited[node]) {
				computer[node]++;
				dfs(node, visited, list);
			}
		}
		
	}

 

dfs 재귀 호출 전 총 N개의 크기를 가진 computer 배열에 인접한 정점에 해당하는 인덱스의 값을 +1 해준다.

이렇게 ++해주면서 전체 정점을 확인하면 각 컴퓨터가 해킹할 수 있는 컴퓨터의 개수를 파악할 수 있다.

 

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%231325/src/Main.java

KwonMinha/BOJ