[백준/1325/Java] 효율적인 해킹 - BFS/DFS 풀이

 

문제

 

www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

 

 

 

문제를 먼저 풀고 오시는 것을 추천합니다.

이 문제의 풀이는 BFS/DFS 외에도 다양한 방법이 있을 수 있으며 제가 보여드리는 풀이는 그 중 하나입니다.

 

문제분석

문제를 읽다보면 헷갈릴 수 있는데 잘 정리하셔야 합니다.

 

A가 B를 신뢰하는 경우 B를 해킹하면 A도 해킹할 수 있다.

반대의 경우, 즉 A가 B를 신뢰하는 경우 A를 해킹한다고 B가 해킹되는 것은 아닙니다.

 

한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력해야 합니다.

즉, 해킹 시도는 한 번이고 그 해킹 한 번으로 동시에 해킹할 수 있는 컴퓨터의 수가 가장 많은 수를 찾아야 합니다.

그리고 동시에 해킹할 수 있는 컴퓨터의 최대 갯수가 동일한 컴퓨터가 여러 대일 수도 있다는 생각을 해야 합니다.

 

입력

첫째 줄에 N과 M이 주어집니다. (N <= 10000, M <= 100000)

둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B의 형식을 들어온다. (A가 B를 신뢰)

컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져있다. (즉, 중복된 번호 없음)

 

출력

한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

 

 

풀이

단방향 그래프의 문제로 먼저 어떻게 데이터를 저장하는지부터 생각해야 합니다.

2차원 배열로 저장하는 방법 등이 있겠지만 메모리 효율도 괜찮고 다양한 문제에 적용하기 편한 방식으로 저장해보도록 하겠습니다.

그리고나서 신뢰하는 방향으로 이동하면서 방문횟수를 더하여 동시에 해킹이 가능한 수를 구하도록 하겠습니다.

 

데이터 저장방식

단방향 그래프 데이터를 노드 수만큼 1차원 배열을 선언하고

그 1차원 배열에 연결되어 있는 노드들을 List 형태로 저장하도록 하겠습니다.

즉, List 배열이 됩니다. List[N+1]

 

먼저 5개 컴퓨터이므로 1차원 배열을 생성해보도록 하겠습니다.

1차원 배열은 인덱스 번호가 컴퓨터 번호를 뜻하며, 따로 번호를 저장하지 않습니다.

편의상 문제와 동일한 번호를 사용하기 위하여 0번 인덱스는 사용하지 않도록 하겠습니다.

ArrayList배열을 선언하면 이렇게 됩니다.

 

5 4를 입력받으면 5번 컴퓨터에 4를 add합니다.

 

그 다음 3 1을 입력받으면 3번 컴퓨터에 1을 add합니다.

그 다음 3 2를 입력받으면 3번 컴퓨터의 List 배열 맨 뒤에 2를 add합니다.

 

그 다음 4 3을 입력받으면 4번 컴퓨터에 3을 add합니다.

 

 

마지막으로 5 3을 입력받으면 5번 컴퓨터 배열 맨 뒤에 3을 add합니다.

 

이제 입력데이터를 구성했으니 동시에 해킹 가능한 컴퓨터 수를 세어보도록 하겠습니다.

신뢰방향으로 그래프를 표시하면 이렇게 됩니다.

A가 B를 신뢰한다. A -> B

 

편의상 동시에 해킹하는 수를 셀 때 자기 자신을 제외하고 세어보도록 하겠습니다. (초기값 0부터 시작하려고 ㅎㅎ)

B를 해킹하면 A도 해킹할 수 있으므로 B를 해킹하면 B 자기자신을 제외하면 A를 하나 더 해킹할 수 있으므로 B = 1 입니다.

A를 해킹하면 더 이상 해킹할 수 있는 컴퓨터가 없으므로 A = 0 입니다.

즉, 해킹은 신뢰방향의 반대방향으로 진행됩니다.

 

5 -> 3 -> 1번 컴퓨터 순으로 신뢰한다고 생각해보겠습니다.

그러면 5번 컴퓨터를 해킹하면 더 이상 해킹할 수 있는 컴퓨터가 없으면 ⑤ = 0 입니다.

3번 컴퓨터를 해킹하면 3을 신뢰하는 5번 컴퓨터를 해킹할 수 있으므로 ③ = 1 입니다.

1번 컴퓨터를 해킹하면 3을 해킹할 수 있고 3번 컴퓨터를 신뢰하고 5까지 해킹할 수 있습니다. 따라서, ① = 2입니다.

 

예제풀이

백준온라인 문제의 예제에서 나온 번호를 그래프로 그려보면 이렇게 나옵니다.

신뢰하는 관계를 방향대로 읽어가면서 해킹가능한 수를 하나씩 더하면 각 컴퓨터별로 동시에 해킹할 수 있는 개수가 나옵니다.

각 컴퓨터 번호별로 동시에 해킹할 수 있는 수는 제가 소스에서 주석처리를 풀면 확인할 수 있도록 하였습니다.

 

소스

BFS로 풀 때 큐에서 노드를 꺼내면 해당 노드에 연결된 ArrayList 값들을 모두 검색해야 합니다.

따라서, for (int next : list[node])와 같이 for문을 돌아야 한다는 사실을 잊지 마시기 바랍니다.

제 소스는 BFS, DFS 풀이가 모두 존재합니다.

제출할 때는 둘 중 1개만 주석 해제하고 돌리셔야 시간초과가 나지 않습니다.

또한, BFS, DFS 함수 내에서도 컴퓨터를 확인할 때마다 신뢰관계를 출력할 수 있는 소스가 있으니 궁금하신 분들은 주석을 풀고 확인해보시기 바랍니다.

그러나 DFS는 제출하면 통과하지만 동시에 해킹하는 수가 맞는 것은 아니므로 참고만 하시기 바랍니다.

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 = new ArrayList[N + 1];
		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]));
		}

		// DFS
//		for (int i = 1; i <= N; i++)
//		{
//			visited = new int[N+1];
//			visited[i] = 1;
//			dfs(i);
//		}

		// 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());
		
		// 컴퓨터당 해킹최대개수
//		System.out.println(Arrays.toString(ans));
	}

	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)
				{
//					System.out.println(node + " <- " + next);
					ans[next]++;
					visited[next] = 1;
					queue.add(next);
				}
			}
		}
	}

	private static void dfs(int node)
	{
		for (int next : list[node])
		{
			if (visited[next] == 0)
			{
//				System.out.println(node + " -> " + next);
				ans[next]++;
				visited[next] = 1;
				dfs(next);
			}
		}
	}
}

 

단방향 그래프 문제를 풀어보았습니다.

양방향 그래프 문제인 1260번 DFS와 BFS 문제도 같이 풀어보시는 것을 추천드립니다.

 

관련글:

2021/02/07 - [Algorithm] - [백준/1260/Java] DFS와 BFS

[백준/1260/Java] DFS와 BFS

 

2021/01/28 - [Algorithm] - [백준/BOJ/7576] 토마토 - BFS 풀이

[백준/BOJ/7576] 토마토 - BFS 풀이

 

2021/01/29 - [Algorithm] - [백준/BOJ/2178] 미로탐색 - BFS 풀이

[백준/BOJ/2178] 미로탐색 - BFS 풀이