Computer Science Knowledge Storage

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
SWEA 5521 상원이의 생일파티입니다.

포인트

이 문제는 그래프 탐색 문제입니다.

특정 인물(상원이, 번호 1번)을 기준으로 자신의 친구와 친구의 친구까지 초대할 수 있는 사람 수를 구하는 것이 목적입니다.
즉, 깊이 2까지 탐색하는 문제로, 단순한 BFS 또는 DFS가 아니라 범위를 제한한 탐색이 핵심입니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Q5521 {
    private static int tc, N, M;
    private static List<List<Integer>> friends;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine().trim());

        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        for (int t = 1; t <= tc; t++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            friends = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                friends.add(new ArrayList<>());
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                friends.get(a).add(b);
                friends.get(b).add(a);
            }

            int sum = 0;
            boolean[] already = new boolean[N + 1];
            already[1] = true;
            for (int num : friends.get(1)) {
                if (!already[num]) {
                    sum++;
                    already[num] = true;
                }
                for (int next : friends.get(num)) {
                    if (!already[next]) {
                        sum++;
                        already[next] = true;
                    }
                }
            }

            sb.append("#").append(t).append(" ").append(sum).append("\n");
        }
        System.out.println(sb);
    }
}
/*
2
6 5
2 3
3 4
4 5
5 6
2 5
6 5
1 2
1 3
3 4
2 3
4 5
 */

코드 설명

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());
    friends.get(a).add(b);
    friends.get(b).add(a);
}

• 인접 리스트 방식으로 친구 관계를 저장할 friends 리스트를 초기화합니다.
• 사람 번호는 1번부터 시작하므로 0번은 사용하지 않습니다.
• 양방향 그래프 형태로 친구 관계를 저장합니다.

for (int num : friends.get(1)) {
    if (!already[num]) {
        sum++;
        already[num] = true;
    }
    for (int next : friends.get(num)) {
        if (!already[next]) {
            sum++;
            already[next] = true;
        }
    }
}

• 상원이(1번)의 친구(num)와 친구의 친구(next)를 순회하며 초대 가능한 사람을 탐색합니다.
• 이미 초대한 사람은 already 배열로 체크하여 중복을 방지합니다.

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

잃어버린 결과표에서 순위를 알 수 있는 선수의 수를 구하는 문제였습니다.
순위를 안다는 것은 누군가에게 지고 이겼는지에 대한 모든 결과를 알고 있으면 되므로 wins 배열과 loses 배열을 통해 확인합니다.

소스코드

import java.util.*;

class Solution {
    List<List<Integer>> wins = new ArrayList<>();
    List<List<Integer>> loses = new ArrayList<>();
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        for(int i = 0; i <= n; i++) {
            wins.add(new ArrayList<>());
            loses.add(new ArrayList<>());
        }
        
        for(int[] result: results) {
            int win = result[0];
            int lose = result[1];
            wins.get(win).add(lose);
            loses.get(lose).add(win);
        }
        
        for(int i = 1; i <= n; i++) {
            boolean[] visited = new boolean[n + 1];
            Queue<Integer> q = new LinkedList<>();
            
            visited[i] = true;
            q.add(i);
            while(!q.isEmpty()) {
                int win = q.poll();
                for(int lose: wins.get(win)) {
                    if (visited[lose]) continue;
                    visited[lose] = true;
                    q.add(lose);
                }
            }
            
            q.add(i);
            while(!q.isEmpty()) {
                int lose = q.poll();
                for(int win: loses.get(lose)) {
                    if (visited[win]) continue;
                    visited[win] = true;
                    q.add(win);
                }
            }
            
            boolean flag = true;
            for(int j = 1; j <= n; j++) {
                if(!visited[j]) {
                    flag = false;
                }
            }
            if (flag) {
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 설명
  • List<List<Integer>> wins = new ArrayList<>();
    List<List<Integer>> loses = new ArrayList<>();
    src가 이긴 desc가 진 배열이 wins 배열, src가 진 desc가 이긴 배열이 loses 배열입니다.

for(int i = 0; i <= n; i++) {
    wins.add(new ArrayList<>());
    loses.add(new ArrayList<>());
}

for(int[] result: results) {
    int win = result[0];
    int lose = result[1];
    wins.get(win).add(lose);
    loses.get(lose).add(win);
}

• wins 배열과 loses 배열을 초기화합니다.

for(int i = 1; i <= n; i++) {
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> q = new LinkedList<>();

    visited[i] = true;
    q.add(i);
    while(!q.isEmpty()) {
        int win = q.poll();
        for(int lose: wins.get(win)) {
            if (visited[lose]) continue;
            visited[lose] = true;
            q.add(lose);
        }
    }

    q.add(i);
    while(!q.isEmpty()) {
        int lose = q.poll();
        for(int win: loses.get(lose)) {
            if (visited[win]) continue;
            visited[win] = true;
            q.add(win);
        }
    }

• 첫번째 while문을 통해 i가 이긴 선수들과 이긴 선수들의 결과표를 통해 인덱스를 방문합니다.
• 두번째 while문을 통해 i가 진 선수들과 진 선수들의 결과표를 통해 인덱스를 방문합니다.

boolean flag = true;
    for(int j = 1; j <= n; j++) {
        if(!visited[j]) {
            flag = false;
        }
    }
    if (flag) {
        answer++;
    }
}

return answer;

• 모든 배열을 방문하였다면 순위를 알 수 있는 것이므로 answer를 증가하고 반복문 종료시 answer를 반환합니다.
•  

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

bfs 탐색을 통해 1번 노드에서 가장 먼 노드를 찾는 문제였습니다. 저는 visited 배열과 step 배열을 통해서 문제를 풀었습니다.

소스코드

import java.util.*;

class Solution {
    boolean[] visited;
    int[] step;
    List<List<Integer>> graph = new ArrayList<>();
    Queue<Integer> q = new LinkedList<>();
    
    public void bfs() {
        while(!q.isEmpty()) {
            int src = q.poll();
            for(int desc: graph.get(src)) {
                if (!visited[desc]) {
                    visited[desc] = true;
                    step[desc] = step[src] + 1;
                    q.add(desc);
                }
            }
        }
    }
    
    public void init(int n) {
        visited = new boolean[n + 1];
        step = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        q.add(1);
        visited[1] = true;
        step[1] = 1;
    }
    
    public int solution(int n, int[][] edge) {
        int answer = 1;
        
        init(n);
        
        for(int[] vertex: edge) {
            int src = vertex[0];
            int desc = vertex[1];
            graph.get(src).add(desc);
            graph.get(desc).add(src);
        }
        
        bfs();
        
        Arrays.sort(step);
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            if (max < step[i]) {
                answer = 1;
                max = Math.max(max, step[i]);
            } else if (max == step[i]) {
                answer++;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 설명
  
  • boolean[] visited
    해당 인덱스의 노드를 방문했는지 확인하는 배열입니다.
  • int[] step
    해당 인덱스의 노드의 그래프의 깊이 입니다.
  • List<List<Integer>> graph = new ArrayList<>()
    src와 desc로 설정하여 graph를 설정합니다.
  • Queue<Integer> q = new LinkedList<>()
    bfs 를 위한 Queue를 선언합니다.
• bfs 메소드
  일반 bfs 메소드입니다.
  • src와 desc를 선언하여 방문하지 않은 desc면 q에 넣고 step도 초기화합니다.
• init 메소드
  변수들을 초기화하는 메소드입니다.

Arrays.sort(step);
int max = Integer.MIN_VALUE;
for(int i = 1; i <= n; i++) {
    if (max < step[i]) {
        answer = 1;
        max = Math.max(max, step[i]);
    } else if (max == step[i]) {
        answer++;
    }
}

return answer;

• 몇번 인덱스를 찾는 문제가 아니라 가장 먼 노드의 갯수를 구하는 문제이므로 Array를 정렬합니다.
• step이 가장 큰 노드를 찾으면 answer를 초기화 합니다.
• max와 step[i]가 같으면 answer을 1 증가합니다.
• 반복문 종료 후 answer를 반환합니다.