-
백준 1325번 효율적인 해킹 :: 마이구미알고리즘 풀이/그래프 2018. 11. 21. 00:44반응형
이 글은 백준 알고리즘 문제 1325번 "효율적인 해킹" 을 풀이한다.
문제는 DFS 를 통해 접근한다.
DFS 가 익숙하지 않는다면, 아래 관련 링크를 읽어보면 좋다.
문제 링크 - https://www.acmicpc.net/problem/1325
DFS - http://mygumi.tistory.com/102
- 현재 코드(Java)는 최근 재채점으로 인해 시간초과를 발생시킨다
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
A가 B 를 신뢰하는 경우에는 B 를 해킹하면, A 도 해킹할 수 있는...... 그러한 연결되어있는....
연결되어있는 관계라면, 마치 바이러스처럼 퍼진다고 볼 수 있다.
이러한 흐름은 양방향 그래프가 아닌 단방향 그래프를 연상시킬 수 있다.
주어지는 입력에 대한 그래프는 다음과 같다. (여기서는 아직 방향을 나타내지는 않았다)
결과적으로 DFS 또는 BFS 를 생각할 수 있다.
쉽게 생각해서, 각 정점을 기준으로 연결된 간선을 통해 탐색하면 된다.
오래전에 푼 문제였지만, 최근 데이터 추가로 인한 시간초과로 실패했다.
우선 이전의 방식을 살펴본다.
기본적인 BFS 를 통해 문제를 해결했었다.
A->B 를 향하는 간선이 아닌, 반대로 B->A 로 접근한다.
A가 B를 신뢰하는 관계에서 A를 해킹한다고 해서, B를 해킹할 수 있는게 아니기 때문이다.
그래서 다시 그래프를 나타내면 다음과 같다.
그 결과, 각 정점에 연결된 간선에 의한 정점들은 해킹할 수 있는 정점을 의미한다.
각 정점을 기준으로 BFS 를 탐색하면 문제는 해결할 수 있고, 해결했었다.
for (int i = 0; i < m; i++) { int v1 = sc.nextInt(); int v2 = sc.nextInt(); a[v2].add(v1); } for (int i = 1; i <= n; i++) { int cnt = 0; Arrays.fill(c, false); q.add(i); c[i] = true; while (!q.isEmpty()) { int v = q.poll(); for (int x : a[v]) { if (!c[x]) { q.add(x); c[x] = true; cnt++; } } }
........... }
다시 풀이하는 과정에서, 계속해서 실패하는 BFS 방식으로 인해, 다른 방식인 DFS 로 접근했다.
(본인이 작성한 BFS 방식인 실패한 이유는 마지막에 언급한다)
이전 BFS 와는 다른 접근으로써, B->A 가 아닌 A->B 로 접근한다.
이 방식은 각 정점에 대해 재귀함수가 호출되는 횟수는 해킹할 수 있는 컴퓨터의 갯수와 동일하게 된다.
이것이 의미하는 것은, DFS 를 통해 각 정점이 기준이 될 때, 탐색되어지는 정점은 현재 기준 정점을 해킹할 수 있다는 것을 의미한다.
자세히 예를 들면, 다음과 같다.
- 5번 정점을 기준으로 DFS 탐색하는 도중 3번 정점을 들렸다 => 3번 정점으로 인해 5번 정점은 해킹되어진다.
- 5번 정점을 기준으로 DFS 탐색하는 도중 1번 정점을 들렸다 => 1번 정점으로 인해 5번 정점은 해킹되어진다.
- 5번 정점을 기준으로 DFS 탐색하는 도중 2번 정점을 들렸다 => 2번 정점으로 인해 5번 정점은 해킹되어진다.
위처럼 각 정점을 기준으로 DFS 를 통해 문제를 해결할 수 있다.
이전 BFS 방식은 큐에서 삽입 및 삭제 연산을 통한 비용으로 인해, 시간초과를 초래한 것이 아닌가? 추측하고 있다.
*다른 의견 및 알고 있는 것이 있다면 댓글을 부탁드린다.
Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/graph/1325.java
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152static ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[10001];static boolean[] visited = new boolean[10001];static int[] ans = new int[10001];static int cnt = 0;private void solve() {StringBuilder sb = new StringBuilder();int n = sc.nextInt();int m = sc.nextInt();for (int i = 1; i <= n; i++) {a[i] = new ArrayList<Integer>();}for (int i = 0; i < m; i++) {int v1 = sc.nextInt();int v2 = sc.nextInt();a[v1].add(v2);}int max = 0;for (int i = 1; i <= n; i++) {visited = new boolean[10001];dfs(i);}for (int i = 1; i <= n; i++) {if (max < ans[i]) {max = ans[i];}}for (int i = 1; i <= n; i++) {if (max == ans[i]) {sb.append(i + " ");}}System.out.println(sb.toString());}public static void dfs(int v) {visited[v] = true;for (int vv : a[v]) {if (!visited[vv]) {ans[vv]++;dfs(vv);}}}cs 반응형'알고리즘 풀이 > 그래프' 카테고리의 다른 글
백준 16236번 아기 상어 :: 마이구미 (0) 2018.12.07 백준 16234번 인구 이동 :: 마이구미 (2) 2018.11.25 백준 2479번 경로 찾기 :: 마이구미 (0) 2018.01.29 백준 1799번 비숍 :: 마이구미 (1) 2018.01.29 백준 2589번 보물섬 :: 마이구미 (0) 2018.01.28