mingssssss

1. 문제

https://www.acmicpc.net/problem/1325

2. 코드

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

public class Main
{
	static int N;
	static int M;

	static List<Integer>[] list;

	static int[] visited = new int[10001];
	static int[] ans = new int[10001];

	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String input = br.readLine();

		StringTokenizer st = new StringTokenizer(input);
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		visited = new int[N+1];
		ans = new int[N+1];
		
        // List 객체 생성 후 ArrayList로 초기화
		list = new ArrayList[N + 1];
        
        // list의 각 인덱스마다 새로운 ArrayList 할당
		for (int i = 1; i <= N; i++)
		{
			list[i] = new ArrayList<Integer>();
		}

		String[] inputs = new String[2];
		for (int i = 1; i <= M; i++)
		{
			input = br.readLine();
			inputs = input.split(" ");
			list[Integer.parseInt(inputs[0])].add(Integer.parseInt(inputs[1]));
		}

		// BFS
		for (int i = 1; i <= N; i++)
		{
			visited = new int[N+1];	// 새로 순회할 때마다 방문배열 초기화
			bfs(i);
		}
		
		// answer
		int max = 0;
		for (int i = 1; i <= N; i++)
		{
			max = Math.max(max, ans[i]);
		}
		
		StringBuffer sb = new StringBuffer();
		for (int i = 1; i <= N; i++)
		{
			if (max == ans[i])
				sb.append(i + " ");
		}
		
		System.out.println(sb.toString().trim());

	private static void bfs(int node)
	{
		Queue<Integer> queue = new LinkedList<Integer>();

		queue.add(node);
		visited[node] = 1;
		while (queue.isEmpty() == false)
		{
			node = queue.remove();
			for (int next : list[node])
			{
				if (visited[next] == 0)
				{
					ans[next]++;
					visited[next] = 1;
					queue.add(next);
				}
			}
		}
	}
}

3. 리뷰

시간초과와의 전쟁을 했었다.. 문제 자체도 이해하는데 30분 정도 걸렸던 것 같다.

먼저 신뢰관계의 두 노드가 나온다. 예를들어 3 1의 노드가 주어진다면, 1을 해킹하면 3을 해킹하는 것과

동일하다는 뜻이다. 처음에는 반대로 이해해서 다른 로직을 짰었다.

문제 이해 후 처음에는 배열로 풀었는데 바로 메모리 초과가 났다.

입력이 10만이 되어서 다른 방법을 찾아야 됐다.

저번에 푼 방법 중에 ArrayList를 2차원 배열로 만들어서 푼 방법이 기억나서 그 방법을 이용했다.

이번에는 구글리을 통해서 ArrayList 의 상위 인터페이스 List에 선언을 하고

각 인덱스를 ArrayList로 생성했다.

그 후 for (int next : list[node])로 list의 값을 하나씩 빼와서 탐색했다.

이렇게 풀어도 시간이 빡빡해서 겨우 통과했다... 역시 정답률 19프로는 다 이유가 있나부다...

이 문제 풀면서 한 단계 성장한 기분이 들었다.

이제는 시간과 메모리까지 고려해서 알고리즘을 작성해야 해서 그 부분을 좀 더 신경 써야겠다.