Union-Find, DFS, BFS

UnionFind

package basic.graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// makeSet() - 1차원 배열을 서로소 집합 관계 표현
// findSet(x) - x의 대표 원소를 찾아 return
// union(x,y) - x의 집합과 y의 집합 합침

public class UnionFind {
    static int v, e; // 정점, 간선
    static int[] parent; // 정점들의 집합 관계 표현
//    static int[] parent = {0,1,1,2, 4, 5,5};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        v=Integer.parseInt(st.nextToken());
        e=Integer.parseInt(st.nextToken());

        parent = new int[v+1]; // 0은 dummy로 사용 x

        // 각 정점 모두가 최초 서로소 표현
        makeSet();

        // 간선 정보를 이용해 두 정점 연결
//        System.out.println(findSet(3));
//        System.out.println(findSet(2));
//        System.out.println(findSet(1));
//        System.out.println(findSet(4));
//        System.out.println(findSet(5));
//        System.out.println(findSet(6));
//        System.out.println(Arrays.toString(parent));
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()); // 정점 x
            int y = Integer.parseInt(st.nextToken()); // 정점 y

            // 두 x, y 를 연결할 때
            // 두 원소 x, y 가 포함된 집합을 합집합으로 만들 때
            // 무조건 합치지 않고 사이클이 발생되는 경우를 제외
            if( findSet(x) == findSet(y) ) { // 이미 하나의 집합이다. 합치면 사이클 발생!!
                System.out.println(x + ", " + y + " 사이클 발생!");
                System.out.println(Arrays.toString(parent));
                return;
            }else {
                union(x, y);
                System.out.println(x + ", " + y + " union!");
                System.out.println(Arrays.toString(parent));
            }
        }

        System.out.println("사이클 발생 X");
    }

    static void makeSet(){
        for(int i=1;i<=v;i++){
            parent[i] = i;
        }
    }

    static int findSet(int x){
        System.out.println(x+"의 부모는 "+parent[x]);
        return parent[x]==x ? x : (parent[x]=findSet(parent[x]));
    }

    static void union(int x, int y){
        int px = findSet(x);
        int py = findSet(y);
        if(px<py) parent[py] = px;
        else parent[px] = py;
    }
}
/*
3 3
1 2
1 3
2 3

7 6
1 2
1 5
5 6
2 3
3 4
6 7
*/

DFS, BFS

package basic.dfsbfs;

import java.util.ArrayDeque;

public class DFS_BFS_2DIM {
    static int n, m;
    static int[][] map = {
            // 행, 렬 0인 부분 - dummy
            {0,  0,  0,  0,  0,  0,  0},
            {0, 11, 12, 13, 14, 15, 16},
            {0, 21, 22, 23, 24, 25, 26},
            {0, 31, 32, 33, 34, 35, 36},
            {0, 41, 42, 43, 44, 45, 46},
            {0, 51, 52, 53, 54, 55, 56},
            {0, 61, 62, 63, 64, 65, 66},
    };
    static int[] dx = {0,0,-1,1};
    static int[] dy = {-1,1,0,0};
    static boolean[][] vis;
    public static void main(String[] args) throws Exception {
        n = map.length;
        m = map[0].length;
        vis = new boolean[n][m];

       bfs(3,3);
//        dfs(3,3);
    }

    static void bfs(int x, int y){
        ArrayDeque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{x,y});
        vis[x][y] = true;

        while(!q.isEmpty()){
            var c = q.poll();
            System.out.println(map[c[0]][c[1]]);

            for(int d=0;d<4;d++){
                int nx = c[0]+dx[d];
                int ny = c[1]+dy[d];

                if(nx<1 || nx>=n || ny<1 || ny >=m || vis[nx][ny]) continue;
                vis[nx][ny] = true;
                q.add(new int[]{nx,ny});
            }
        }
    }
    static class Node{
        int x, y;
        Node(int x, int y){
            this.x=x; this.y=y;
        }
        @Override
        public String toString(){
            return "Node [y="+y+", x="+x+"]";
        }
    }

    static void dfs(int x, int y){
        vis[x][y] = true;
        System.out.println(map[x][y]);

        for(int d=0;d<4;d++){
            int nx = x+dx[d];
            int ny = y+dy[d];

            if(nx<1 || nx >=n || ny<1 || ny>=m || vis[nx][ny]) continue;
            dfs(nx, ny);
        }
    }
}