백준 1325. 효율적인 해킹
미리 말하자면 아 그저 개떡같은 스레기 문제ㅎㅎ. 아니 문제는 괜찮은데 백준 플랫폼에서 자바로 풀면 뭐로 하든 시간 초과만 계속 남. 자바로 푼 사람들 거의 시간초과. 시간 조정하든 해라!!!!! 하물며 답안으로 그대로 복사해도 시간 초과 ㅋㅋ..
문제
해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.
이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.
이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.
출력
첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.
풀이
우선 이 문제는 Do it! 알고리즘 코딩 테스트 자바에 그래프 장에 있는 문제다. 그래프를 이용한 접근이라는 것을 알 수 있었고, 컴퓨터간 연결되어 있다는 문제 설명을 보고 dfs, bfs로 접근했다.
문제 설명에는 A가 B를 신뢰하는 경우에 B를 해킹하면 A도 해킹할 수 있다고 되어있다.
그럼 입력값이 다음과 같이 주어졌을 때를 보자.
5 4
3 1
3 2
4 3
5 3
컴퓨터의 개수는 5개고 신뢰 관계는 4개 입력으로 들어온다.
입력은 A와 B순으로 입력되고 문제 설명과 동일하게 A가 B를 신뢰한다를 의미한다.
다시 풀이로 돌아와서, A가 B를 신뢰하는 경우 B를 해킹하면 A를 해킹할 수 있다고 했다.
그렇다면 3번 컴퓨터는 1번과 2번을 신뢰하고 있다. 그러므로 1번을 해킹하면 3번을 해킹할 수 있고, 2번을 해킹해도 3번을 해킹할 수 있다. 또한 4번과 5번 컴퓨터는 3번 컴퓨터를 신뢰하고 있다. 그러므로 3번을 해킹할 수 있다면 4번과 5번 또한 해킹할 수 있다는 말이 된다.
1을 해킹함으로써 3,4,5 총 4개를 해킹할 수 있고, 2번 또한 마찬가지로 4개를 해킹할 수 있다.
그래서 나는 그래프를 B를 해킹하면 A를 해킹할 수 있다 생각하고 그래프에 삽입했다,
1번에서 접근 가능한 노드는 3번
2번에서 접근 가능한 노드는 3번
3번에서 접근 가능한 노드는 4, 5번
4번에서 접근 가능한 노드는 X
5번에서 접근 가능한 노드는 X
노드B -> 해킹할 수 있는 노드 A
1 -> 3
2 -> 3
3 -> 4, 5
4 ->
5 ->
1번 컴퓨터부터 순서대로 Queue에 넣으면서 Bfs를 이용했고 각 컴퓨터에서 방문하는 컴퓨터의 수를 카운팅하여 값을 구해냈다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class boj1325 {
static ArrayList<Integer>[] arr;
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
N = Integer.parseInt(stk.nextToken());
int M = Integer.parseInt(stk.nextToken());
arr = new ArrayList[N + 1];
int[] answer = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
stk = new StringTokenizer(br.readLine());
int A = Integer.parseInt(stk.nextToken());
int B = Integer.parseInt(stk.nextToken());
arr[A].add(B);
}
for (int i = 1; i <= N; i++) {
answer[i] = bfs(i);
}
int maxVal = 0;
for (int i : answer) {
maxVal = Math.max(maxVal, i);
}
for (int i = 1; i < N + 1; i++) {
if (answer[i] == maxVal) {
System.out.print(i + " ");
}
}
}
// bfs 에서 컴퓨터가 해킹할 수 있는 컴퓨터의 수를 return
static public int bfs(int idx) {
Deque<Integer> dq = new LinkedList<>();
boolean[] visited = new boolean[N + 1];
int cnt = 0;
visited[idx] = true;
dq.add(idx);
while (!dq.isEmpty()) {
int a = dq.pollFirst();
for (Integer i : arr[a]) {
if(!visited[i]){
visited[i] = true;
dq.add(i);
cnt++;
}
}
}
return cnt;
}
}그런데 말이지, 시초 난다.
나 같은 경우 신뢰 관계가 A가 B를 신뢰하면 B를 해킹했을 때 A를 해킹할 수 있기 때문에 B에 연결된 노드들로 담고 bfs를 진행했다.
블로그를 찾아본 결과, 내가 한 방식으로 하면 시초가 난다고 한다. A와 B 순 그대로 입력을 받고 bfs를 통해 몇 번이나 해킹당할 수 있는지를 계산하여 구한다고 하고 책의 답안도 같다. 하지만 책의 답안 또한 그대로 복사하여 백준에서 제출했을 경우 시간 초과가 난다. 찾아보니 뭐 운도 따라야한다는데 후.......
하지만 내 생각은 다르다. A B의 신뢰관계 순을 바꾸든 같게 하든 시간 복잡도는 동일할 것이라고 생각한다. 혹시 차이가 있다면 미세한 차이가 발생할 수 있나? 라는 생각이 들기는 하는데, 이렇게 하든 저렇게 하든 노드가 서로 연결된 개수도 동일해서 별 차이가 없을 것이라고 생각한다.
이 문제는 그냥 그래프를 생각하고 이것에 bfs를 반영해서 해결하려고 하는 방식을 알아간다고 생각해야겠다.
풀리긴 하니 문제가 잘못된 것 같진 않지만, 백준에서 처리가 안되니 너무 답답하고 시간 낭비한 생각이 든다.
스트레스 ㅎㅎ
아래는 책의 정답 코드이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static ArrayList<Integer>[] arr;
static int[] answer1;
static boolean[] visited;
static int N;
static int M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine());
N = Integer.parseInt(stk.nextToken());
M = Integer.parseInt(stk.nextToken());
arr = new ArrayList[N + 1];
answer1 = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = new ArrayList<>();
}
for (int i = 0; i < M; i++) {
stk = new StringTokenizer(br.readLine());
int A = Integer.parseInt(stk.nextToken());
int B = Integer.parseInt(stk.nextToken());
arr[A].add(B);
}
for (int i = 1; i <= N; i++) {
visited = new boolean[N+1];
bfs(i);
}
int maxVal = 0;
for (int i = 1; i <= N; i++){
maxVal = Math.max(maxVal, answer1[i]);
}
for (int i = 1; i <= N; i++) {
if (answer1[i] == maxVal) {
System.out.print(i + " ");
}
}
}
// bfs 에서 컴퓨터가 해킹할 수 있는 컴퓨터의 수를 return
static public void bfs(int idx) {
Queue<Integer> dq = new LinkedList<>();
dq.add(idx);
visited[idx] = true;
while (!dq.isEmpty()) {
int a = dq.poll();
for (int i : arr[a]) {
if(!visited[i]){
visited[i] = true;
answer1[i]++;
dq.add(i);
}
}
}
}
}