[SWEA 5643, BOJ 2458] 키 순서(Graph).java

#. Problem

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo

* The copyright in this matter is in SWEA

백준의 2458 문제와 동일하다.

https://www.acmicpc.net/problem/2458

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

자신보다 큰 친구(노드)에게만 방향이 있는 

단방향 그래프 문제이다.

노드의 수 범위는 2 ≤ N ≤ 500

간선의 수 범위는 0 ≤ M ≤ N*(N-1)/2 인데,

제한시간이 10초로 관대하다.

문제에서 원하는

자신의 키가 몇 번째인지 정확히 알기 위해서는

자신보다 작은 친구의 수 + 자신보다 큰 친구의 수 = N - 1 이 되어야 한다.

이 문제를 해결할 수 있는 방법이 정말 다양한 것 같다.

언제라도 다시 풀어보자 !_!

#. Code_bfs_naive

4번 친구를 보면,

행은 자신보다 큰 친구(자신과 연결된)의 정보를 나타내고

열은 자신보다 작은 친구(자신과 연결된)의 정보를 나타낸다.

이 코드에서는 자신과 연결된 노드를 따라가며

자신보다 큰 학생일 경우 Queue에 추가해주고, 학생 수를 count 해준다.

자신보다 작은 학생의 경우도 마찬가지이다.

이렇게 모든 학생을 기준으로 반복해준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Solution5643_bfs {
 
    static int N, M, adj[][];
    static int gtCnt, ltCnt;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            N = Integer.parseInt(br.readLine()); // 학생 수 : 정점 수
            M = Integer.parseInt(br.readLine()); // 관계 수 : 간선 수
            adj = new int[N + 1][N + 1];
            
            int i, j;
            for (int m = 1; m <= M; m++) {
                st = new StringTokenizer(br.readLine());
                
                i = Integer.parseInt(st.nextToken());
                j = Integer.parseInt(st.nextToken());
                // 단방향 그래프
                adj[i][j] = 1;
            }
 
            int res = 0;
            for (int k = 1; k <= N; k++) {
                // 자신보다 작은 친구와 큰 친구의 수
                gtCnt = ltCnt = 0;
                // 자신보다 큰 친구를 찾으러
                gtBFS(k);
                // 자신보다 작은 친구를 찾으러
                ltBFS(k);
                // 자신보다 작은 친구와 큰 친구의 합이 N - 1 이라면 자신이 몇 번째인지 알 수 있음
                if(gtCnt + ltCnt == N - 1) res++;
            }
            
            System.out.println("#" + tc + " " + res);
        }
 
    }
 
    /**
     *  자신보다 키가 큰 학생을 찾아보자.
     * @param start 탐색의 출발 학생번호
     */
    private static void gtBFS(int start) {
 
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        q.add(start);
        visited[start] = true;
        
        while(!q.isEmpty()) {
            
            int k = q.poll();
            for (int i = 1; i <= N; i++) {
                // 나보다 키가 크고 아지 확인하지 않은 친구 
                if (adj[k][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                    gtCnt++;
                }
            }
        }
 
    }
 
    /**
     *  자신보다 키가 작은 학생을 찾아보자.
     * @param start 탐색의 출발 학생번호
     */
    private static void ltBFS(int start) { 
 
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[N + 1];
        q.add(start);
        visited[start] = true;
        
        while(!q.isEmpty()) {
            
            int k = q.poll();
            for (int i = 1; i <= N; i++) {
                // 나보다 키가 작고 아지 확인하지 않은 친구 
                if (adj[i][k] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                    ltCnt++;
                }
            }
        }
 
    }
}
 

#. Code_dfs_optim

DFS는 BFS와 유사하다.

단, BFS처럼 visit 상태를 각 학생마다 초기화해주지 않고

visit 상태를 매개변수로 들고 다닌다.

다른 방법으로는

친구들의 관계를 한 배열에 저장하지 않고

자신보다 큰 친구들의 정보를 저장한 배열

자신보다 작은 친구들의 정보를 저장한 배열 나눠서 저장하여

유사한 함수를 하나로 사용할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution5643_dfs2 {
 
    static int N, M, adj[][], radj[][];
    static int cnt;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            N = Integer.parseInt(br.readLine()); // 학생 수 : 정점 수
            M = Integer.parseInt(br.readLine()); // 관계 수 : 간선 수
            adj = new int[N + 1][N + 1]; // 자신보다 큰 관계
            radj = new int[N + 1][N + 1]; // 자신보다 작은 관계
            
            int i, j;
            for (int m = 1; m <= M; m++) {
                st = new StringTokenizer(br.readLine(), " ");
 
                i = Integer.parseInt(st.nextToken());
                j = Integer.parseInt(st.nextToken());
 
                radj[j][i] = adj[i][j] = 1;
            }
 
            int res = 0;
            for (int k = 1; k <= N; k++) {
                // 자신보다 크거나 작은 친구의 수
                cnt = 0;
                // 자신보다 큰 친구를 찾으러
                dfs(k, adj, new boolean[N + 1]);
                // 자신보다 작은 친구를 찾으러
                dfs(k, radj, new boolean[N + 1]);
                // 자신보다 크거나 작은 친구들이 N - 1 명이라면 자신이 몇 번째인지 알 수 있음
                if (cnt == N - 1) res++;
            }
 
            System.out.println("#" + tc + " " + res);
        }
 
    }
 
    /**
     * 자신보다 크거나/작은 학생을 따라 탐색
     * 
     * @param n       현재 기준이 되는 학생번호
     * @param visited 현재까지 확인한 친구 체크
     */
    private static void dfs(int n, int[][] adj, boolean[] visited) {
 
        visited[n] = true;
 
        for (int i = 1; i <= N; i++) {
            // 나보다 크고 확인하지 않은 치구
            if (adj[n][i] == 1 && !visited[i]) {
                cnt++;
                dfs(i, adj, visited);
            }
        }
 
    }
 
}
 

#. Code_dfs_optim_2

dfs를 한 번만 호출하여 해결하는 방법

자신보다 키가 큰 학생을 탐색하면서 작은 학생 정보로 확인

            1  2  3  4  5  6

gtCnt : [0, 4, 0, 3, 2, 3, 0]

ltCnt : [0, 0, 4, 0, 3, 1, 4]

sum   : [0, 4, 4, 3, 5, 4, 4]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution5643_dfs3 {
 
    static int N, M, adj[][];
    static int[] gtCnt, ltCnt;
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
 
            N = Integer.parseInt(br.readLine()); // 학생 수 : 정점 수
            M = Integer.parseInt(br.readLine()); // 관계 수 : 간선 수
 
            adj = new int[N + 1][N + 1];
            // idx번 학생보다 키가 큰 친구의 수와 작은 친구의 수를 각각 저장
            gtCnt = new int[N + 1];
            ltCnt = new int[N + 1];
            
            int i, j;
            for (int m = 1; m <= M; m++) {
                st = new StringTokenizer(br.readLine(), " ");
                
                i = Integer.parseInt(st.nextToken());
                j = Integer.parseInt(st.nextToken());
                
                adj[i][j] = 1;
            }
 
            int res = 0;
            for (int k = 1; k <= N; k++) {
                dfs(k, k, new boolean[N + 1]);
            }
            // 자신보다 크거나 작은 친구들이 N-1 명이라면
            for (int k = 1; k <= N; k++) {
                if(gtCnt[k] + ltCnt[k] == N - 1) res++;
            }
            
            System.out.println("#" + tc + " " + res);
        }
 
    }
 
    /**
     * src보다 큰 학생을 따라 탐색하며 src 자신이 누구보다 크고/작으지 판단
     * @param src 출발 학생 번호
     * @param cur 현재 학생 번호
     * @param visited 방문 체크
     */
    private static void dfs(int src, int cur, boolean[] visited) { 
 
        visited[cur] = true; // src < cur
        
        for (int i = 1; i <= N; i++) {
            // 나보다 크고 확인하지 않은 친구
            if(adj[cur][i] == 1 && !visited[i]) { // src < cur < i
                gtCnt[src]++;
                ltCnt[i]++;
                dfs(src, i, visited);
            }
        }
 
    }
    
}
 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class BOJ2458 {
 
    static int N, M, taller[], shorter[];
    static ArrayList<Integer>[] adj;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        taller = new int[N + 1];
        shorter = new int[N + 1];
        adj = new ArrayList[N + 1];
        
        for (int i = 1; i <= N; i++) {
            adj[i] = 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());
            
            adj[a].add(b);
        }
        
        for (int i = 1; i <= N; i++) {
            process(i, i, new boolean[N + 1]);
        }
        
        int res = 0;
        for (int i = 1; i <= N; i++) {
            if(taller[i] + shorter[i] == N - 1) res++;
        }
        
        System.out.println(res);
    }
 
    private static void process(int start, int now, boolean[] visited) {
        
        visited[now] = true;
        
        for (Integer std : adj[now]) {
            if(visited[std]) continue;
            taller[start]++;
            shorter[std]++;
        
            process(start, std, visited);
        }
    }
}
 

#. Code_dfs_memoization

메모이제이션을 적용한 방법은 나중에 다시 풀 때 되새겨봐야겠다 ㅠ_ㅠ

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
/**
 * @author taeheekim
 */
public class Solution5643_dfs_memo {
 
    static int N, M, adj[][];
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        
        int T = Integer.parseInt(in.readLine().trim());
        for (int t = 1; t <= T; ++t) {
            N = Integer.parseInt(in.readLine());
            M = Integer.parseInt(in.readLine());
            // 0행, 0열 메모 목적으로 1씩 크기 늘림 
            // (각행 0열 : 자신보다 큰 대상 개수, 0행 각열 : 자신보다 작은 대상 개수)
            adj = new int[N + 1][N + 1];
            
            for (int i = 0; i <= N; ++i) {
                adj[i][0] = -1;
            }
            
            for (int m = 0; m < M; ++m) {
                StringTokenizer st = new StringTokenizer(in.readLine(), " ");
                
                int i = Integer.parseInt(st.nextToken());
                int j = Integer.parseInt(st.nextToken());
                
                adj[i][j] = 1;
            }
            
            int answer = 0;
            for (int k = 1; k <= N; ++k) {
                if (adj[k][0] == -1)
                    gtDfs(k);
            }
 
            for (int i = 1; i <= N; ++i) {
                for (int j = 1; j <= N; ++j) {
                    adj[0][j] += adj[i][j];
                }
            }
            
            for (int k = 1; k <= N; ++k) {
                if (adj[k][0] + adj[0][k] == N - 1)
                    answer++;
            }
            
            System.out.println("#" + t + " " + answer);
        }
    }
 
    private static int gtDfs(int k) {
        
        int cnt = 0;
        for (int i = 1; i <= N; ++i) {
            
            // i가 나보다 크고
            if (adj[k][i] == 1) { 
                // 아직 i가 i 자신 보다 큰 대상을 탐색하지 않았다면 탐색
                if (adj[i][0] == -1) {
                    gtDfs(i);
                }
                
                // 탐색 후 i보다 큰 대상이 존재하면 그 대상들은 결국 k보다도 큰 대상이 됨
                if (adj[i][0] > 0) { 
                    for (int j = 1; j <= N; ++j) {
                        // i보다 j가 크다면 결국 j는 k보다도 크게 됨. 따라서 인접행렬에 마킹
                        if (adj[i][j] == 1) {
                            adj[k][j] = 1;
                        }
                    }
                }
            }
        }
        // 탐색을 마친 후 자신보다 큰 대상들을 모두 카운트
        for (int j = 1; j <= N; ++j) {
            if (adj[k][j] == 1) {
                cnt++;
            }
        }
        // 카운트 결과(자신보다 큰 대상의 개수)를 자신의 인접행렬 0열의 위치에 저장
        return adj[k][0] = cnt; 
    }
 
}
 

#. Code_dfs_floyd-warshall

floyd warshall로 해결한 방법도 나중에 다시 풀 때 되새겨보자 !!

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
 
/**
 * @author iccack
 */
 
public class Solution5643_floyd_warshall {
 
    static int INF = 987654321;
    static int N, M, res = 0, adj[][], manCount[];
    static boolean[] v;
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        for (int t = 1; t <= T; t++) {
            
            N = sc.nextInt();
            M = sc.nextInt();
            adj = new int[N + 1][N + 1];
            // 초기는 무한대
            for (int i = 0; i <= N; i++) {
                Arrays.fill(adj[i], INF);
            }
            // 행의 학생이 열의 학생보다 키가 작다.
            for (int i = 0; i < M; i++) {
                adj[sc.nextInt()][sc.nextInt()] = 1; 
            }
            // 서로 관련 있는 사람들을 알수있는 것 변경하기
            for (int k = 1; k <= N; k++) { // 경유지
                for (int i = 1; i <= N; i++) { // 출발지
                    for (int j = 1; j <= N; j++) { // 도착지
                        if (adj[i][j] > adj[i][k] + adj[k][j]) {
                            adj[i][j] = adj[i][k] + adj[k][j];
                        }
                    }
                }
            }
 
            int[] isKnows = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (adj[i][j] != INF) {
                        isKnows[i]++;
                        isKnows[j]++;
                    }
                }
            }
            
            res = 0;
            for (int i = 1; i <= N; i++) {
                if (isKnows[i] == N - 1) {
                    res++;
                }
            }
 
            System.out.println("#" + t + " " + res);
        }
    }
}