[알고리즘 문제풀이] 그래프

12-경로탐색(DFS)

🚩 내 코드

public class 경로탐색_dfs {
    static  int n;
    static  int m;
    static  int [][] graph;
    static  int [] ch;
    static  int answer;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = Integer.parseInt(scanner.next()); // 정점 수
        m = Integer.parseInt(scanner.next()); // 간선 수
        graph = new int[n+1][n+1];
        ch = new int[n+1];
        answer = 0;

        for(int i=0; i<m; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph[a][b] = 1;
        }
        ch[1] = 1;
        dfs(1);
        System.out.println(answer);
    }
    private static void dfs(int v) {
        if(v==n){
            answer++;
        }else{
            for(int i=1; i<=n; i++){
                if(graph[v][i]==1 && ch[i]==0){
                    ch[i] = 1;
                    dfs(i);
                    ch[i] = 0; // 방문체크 풀어주기
                }
            }
        }
    }
}

💡 푼 방식

노드+1 만큼의 이차원배열을 만든 후, 연결되는 곳에 1을 넣는것으로 처음 설정을 해준다. (1과 3이 연결이라면 graph[1][3] = 1이렇게) 방향성이 있으므로, 꼭 첫번째꺼에서 두번째꺼 순서를 따져줘야함. (graph[3][1] = 1 이러면 방향이 반대라 안된다는 거임;;)
숫자 1부터 시작. ch[1]에 1을 넣어주어서 방문체크.(글랜체크 아님 ㅎ~)

이렇게 for문으로 각 노드와 연결된 노드를 찾아주고, 또 그 노드에서 다른 노드로 연결된걸 찾아주고,, 그게 5까지 가는지 확인해야하므로 dfs를 사용하였다.

📚 알게 된 정보

해당 노드를 방문체크를 하고 그 노드를 dfs넣은 후, 방문체크를 풀어줘야한다.

12-경로탐색(인접리스트)

위와 같은 문제지만, 노드가 10000개 이렇게 들어와버리면, 행렬로 풀기에는 너무 비효율적이다. 이번엔 다른방법..으로

🚩 내 코드

public class 경로탐색_인접리스트 {
    static  int n;
    static  int m;
    static ArrayList<ArrayList<Integer>> graph;
    static  int [] ch;
    static  int answer;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = Integer.parseInt(scanner.next()); // 정점 수
        m = Integer.parseInt(scanner.next()); // 간선 수
        graph = new ArrayList<>();
        ch = new int[n+1];
        answer = 0;
        for(int i=0; i<=n; i++){ 
            graph.add(new ArrayList<>());// 정수를 저장할 수 있는 객체 생성.
        }
        for(int i=0; i<m; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph.get(a).add(b);
        }
        ch[1]=1;
        dfs(1);
        System.out.println(answer);
        
    }
    private static void dfs(int v) {
        if(v==n){
            answer++;
        }else{
            for(int nv : graph.get(v)){ // v노드에 연결된 arraylist
                if(ch[nv]==0){
                    ch[nv] = 1;
                    dfs(nv);
                    ch[nv] = 0;
                }
            }
        }
    }
}

💡 푼 방식

ArrayList에 노드를 넣어주고, 그 노드에 연결된 노드 또한 넣어줘야하므로

ArrayList<ArrayList<Integer>> graph

로 생성해주었다.
위 방식으로 for문 도는거 대신에 각 노드들의 arrayList만 돌면 된다.

📚 알게 된 정보

ArrayList<ArrayList<Integer>> graph

13-그래프 최단 거리

🚩 내 코드

public class 그래프최단거리 {
    static int n,m;
    static int[] ch,dis;
    static ArrayList<ArrayList<Integer>> graph;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = Integer.parseInt(scanner.next()); // 정점 수
        m = Integer.parseInt(scanner.next()); // 간선 수
        graph = new ArrayList<>();
        ch = new int[n+1];

        for(int i =0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<m; i++){
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph.get(a).add(b);
        }
        bfs(1);
        for(int i=1; i<dis.length; i++){
            System.out.println(dis[i]);
        }
    }

    private static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        ch[v] = 1;
        dis[v] = 0;
        queue.offer(v);
        while(!queue.isEmpty()){
            int cv = queue.poll();
            for(int nv : graph.get(cv)){
                if(ch[nv] == 0){
                    ch[nv]=1;
                    queue.offer(nv);
                    dis[nv] = dis[cv]+1;
                }
            }
        }
    }
}

💡 푼 방식

최단이니까 bfs로 풀었다.
각 노드로 가는 회수는 dis배열에 넣었고,

dis[nextnode] = dis[currentnode]+1

로 회수를 세주었다.

📚 알게 된 정보