첫 시도에서 시간 초과가 나와 문제를 다시 읽어보았다. 주의할 점은 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력해야 한다는 것이다. 즉, 가장 많은 신뢰를 받는 컴퓨터의 수를 max로 잡아 그 수와 동일한 컴퓨터 번호를 출력하는 개념으로
이해하고 문제 풀이를 진행하였다.
🧀 프로세스
- 입력받은 값들을 기반으로 ArrayList 를 생성해주고 단방향 그래프를 형성해준다.
static int N, M;
static ArrayList<Integer>[] adj;
static int[] res;
static void input() {
N = scan.nextInt();
M = scan.nextInt();
adj = new ArrayList[N+1];
res = new int[N+1];
for(int i=1; i<=N; i++) adj[i] = new ArrayList<>();
while(M-- >0) {
int x = scan.nextInt(), y = scan.nextInt();
adj[x].add(y);
}
}
순회
- 1 - N 까지 BFS 를 호출해주며 연결된 컴퓨터의 수를 증가시키고 max를 갱신한다. 그 max의 수와 동일한 컴퓨터 번호를 ArrayList 에 넣어주고 오름차순 후, 출력해준다.
static void pro() {
int max = 0;
// 모든 컴퓨터의 연결된 컴퓨터 수 측정
for(int i=1; i<=N; i++)
bfs(i);
// 최대치 계산
for(int i=1; i<=N; i++)
max = Math.max(res[i], max);System.out.println(res[i]);
ArrayList<Integer> list = new ArrayList<>();
for(int i=1; i<=N; i++)
if(res[i] == max) list.add(i);
Collections.sort(list);
for(int k: list)
sb.append(k+" ");
System.out.println(sb);
}
BFS
- 여기서 주의할 점은 res[y]++ 이다. 이렇게 코드를 작성한 이유는 adj[k] 에 들어있는 요소들 즉, y는 k와 연결되어 있는 컴퓨터다. 가장 많이 연결되어 있는 컴퓨터의 수를 측정하기 때문에 아래와 같이 코드를 작성하였다.
/*
* 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호
* 즉, 연결된 경우가 가장 많은 컴퓨터의 수를 측정하면 됨
*/
static void bfs(int x) {
Queue<Integer> Q = new LinkedList<>();
Q.add(x);
boolean[] visit = new boolean[N+1];
visit[x] = true;
while(!Q.isEmpty()) {
int k = Q.poll();
for(int y : adj[k]) {
if(visit[y]) continue;
Q.add(y);
visit[y] = true;
res[y]++;
}
}
}
✅ 전체 코드
static int N, M;
static ArrayList<Integer>[] adj;
static int[] res;
static void input() {
N = scan.nextInt();
M = scan.nextInt();
adj = new ArrayList[N+1];
res = new int[N+1];
for(int i=1; i<=N; i++) adj[i] = new ArrayList<>();
while(M-- >0) {
int x = scan.nextInt(), y = scan.nextInt();
adj[x].add(y);
}
}
static void pro() {
int max = 0;
// 모든 컴퓨터로 해킹하는 경우의 수 측정
for(int i=1; i<=N; i++) bfs(i);
// 최대치 계산
for(int i=1; i<=N; i++)
max = Math.max(res[i], max);System.out.println(res[i]);
ArrayList<Integer> list = new ArrayList<>();
for(int i=1; i<=N; i++)
if(res[i] == max) list.add(i);
Collections.sort(list);
for(int k: list) sb.append(k+" ");
System.out.println(sb);
}
/*
* 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호
* 즉, 연결된 경우가 가장 많은 컴퓨터의 수를 측정하면 됨
*/
static void bfs(int x) {
Queue<Integer> Q = new LinkedList<>();
Q.add(x);
boolean[] visit = new boolean[N+1];
visit[x] = true;
while(!Q.isEmpty()) {
int k = Q.poll();
for(int y : adj[k]) {
if(visit[y]) continue;
Q.add(y);
visit[y] = true;
res[y]++;
}
}
}
public static void main(String[] args) {
input();
pro();
}