문제
풀이
import java.io.*;
import java.util.*;
public class Q1325_효율적으로해킹하기 {
static ArrayList<Integer>[] arr;
static boolean visited[];
static int result[];
static int max;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
arr = new ArrayList[n + 1];
result = new int[n + 1];
// 방문 배열 초기화
// visited = new int[n + 1];
// for (int i = 1; i <= n; i++) {
// visited[i] = -1;
// }
visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = new ArrayList<>();
}
// 에지 정보 초기화
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
arr[s].add(e);
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
visited = new boolean[n+1];
}
}
max = 0;
for (int i = 1; i <= n; i++) {
if (max < result[i]) {
max = result[i];
}
}
for (int i = 1; i <= n; i++) {
if (result[i] == max) {
System.out.print(i + " ");
}
}
}
public static void dfs(int node) {
visited[node] = true;
result[node]++;
for (int next : arr[node]) {
if (!visited[next]) {
dfs(next);
}
}
// visited[node] = -1;
}
}리뷰
bfs와 dfs 두 알고리즘으로 풀 수 있는 문제였다.
여기서 나는 최대 깊이?를 찾는 문제라 생각하여 dfs를 사용하였다.
잘못 생각한 부분
잘 못된 풀이
- 풀이 바로 아래 테스트 케이스를 예시로 코드를 살펴보자
public class Q1325_효율적으로해킹하기 {
static ArrayList<Integer>[] arr;
static boolean visited[];
static int result[];
static int max;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
arr = new ArrayList[n + 1];
result = new int[n + 1];
// 방문 배열 초기화
// visited = new int[n + 1];
// for (int i = 1; i <= n; i++) {
// visited[i] = -1;
// }
visited = new boolean[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = new ArrayList<>();
}
max = 0;
// 에지 정보 초기화
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
arr[s].add(e);
}
// 이 반복문을 진행하면서 result배열은 1로 고정된다
// 1,2,3,4,5,6
// 1,1,2,3,4,5
// 1,1,1,2,3,4
// ...
// 1,1,1,1,1,1
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i, 1);
visited = new boolean[n+1];
}
}
for (int i = 1; i <= n; i++) {
if (result[i] == max) {
System.out.print(i + " ");
}
}
}
public static void dfs(int node, int depth) {
// 이 부분이 문제였다
// depth는 1씩 증가하고 그때마다 max는 업데이트 된다.
if (depth > max) {
max = depth;
}
result[node] = depth;
visited[node] = true;
for (int next : arr[node]) {
if (!visited[next]) {
dfs(next, depth + 1);
}
}
// visited[node] = -1;
}
}a가 b를 신뢰하면 b를 해킹하면 a도 해킹할 수 있다는 조건은
a가 b를 신뢰하고, b가 c를 신뢰하면 c를 해킹하면 b,a를 모두 해킹할 수 있게 된다..
근데 처음 풀었던 방법은 입력값이 아래와 같을 때
6 5 // n m
1 2
2 3
3 4
4 5
5 6변수 depth는 1씩 증가하여 max=6이 되는데, 결과 배열 result는 dfs를 호출하는 for문이 반복될 때마다 i가 1씩 증가하면서 result의 모든 인덱스가 1로 고정된다.
결국 max = 6이 되는데 result의 모든 인덱스는 1,1,1,1,1,1이므로 아무런 값도 출력하지 않게 된게 문제였다.
수정
그런데 문제에서 묻는 것은 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터를 찾으라는 것이었다. 따라서 각 에지마다 신뢰관계를 누적해줘야 한다. 입력값이
5 4
3 1
3 2
4 3
5 3일 때, 흐름은 다음과 같다.
-
방문 배열을 초기화한다.
-
엣지 정보를 초기화해준다.
-
n만큼 반복하며 dfs를 호출해준다.
- 여기서 각 노드에 연결된 노드의 수를 누적해준다.
- i = 1일때, result[1]++ -> result={1,0,0,0,0}
- i = 2일때, result[2]++ -> result={1,1,0,0,0}
- i = 3일때, result[3]++, result[1]++, result[2]++ -> result={2,2,1,0,0}
- i = 4일때, result[4]++, result[3]++, result[1]++, result[2]++ -> result={3,3,2,1,0}
- i = 5일때, result[5]++, result[3]++, result[1]++, result[2]++ -> result={4,4,3,0,1}
- 이런식으로 해킹 가능한 컴퓨터의 수가 업데이트된다.
-
반복문을 돌며 result에서 최대값을 찾아 max를 업데이트 한다.
-
반복문을 돌며 result에서 max와 같은 수를 가진 인덱스를 출력해준다.
틀렸어도 어째서 틀렸는지 정확하기 이해하고 넘어가고자, 어디서 문제가 발생했는지 디버깅하고 있었는데, 내가 예상했던 결과와 실제 출력되는 값들이 달라 어디가 틀렸는지 오랫동안 삽질했다.
그런데 알고보니 반복문에서 변수를 잘 못 적어서 그랬다....
변수 하나 잘 못 적은거 때문에 얼마나 시간을 날려먹었는지 모르겠다ㅜㅜ
꾸준히 하자!