매일 Algorithm

백준 2178번 (그래프 탐색)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class problem219 {
    // 우 / 좌
    static int[] dx = {0, 1, 0, -1};
    // 하 / 상
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visit;
    static int[][] maze;
    static int n, m;

    public static void main(String[] args) {


        Scanner in = new Scanner(System.in);
        n = in.nextInt(); // 열
        m = in.nextInt(); // 행

        // 행과 열 배열 지정
        maze = new int[n][m];
        visit = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            String st = in.next();
            for (int j = 0; j < m; j++) {
                // 정수값으로 변환후 저장
                maze[i][j] = st.charAt(j) - '0';
            }
        }
        visit[0][0] = true; //시작점
        BFS(0, 0);
        // 인덱스는 0부터 시작하기때문 -1
        System.out.print(maze[n - 1][m - 1]);
    }

    private static void BFS(int i, int j) {
        // 값이 2개가 들어옴으로 int[]로 선언
        Queue<int[]> q = new LinkedList<>();
        // 처음 시작점을 넣어준다.
        q.add(new int[]{i, j});
        // BFS를 실행할수 없을때 까지.
        while (!q.isEmpty()) {
            int[] now = q.poll();
            int nowX = now[0];
            int nowY = now[1];
            // 상 하 좌 우 탐색 (4로지정)
            for (int p = 0; p < 4; p++) {
                int x = nowX + dx[p];
                int y = nowY + dy[p];
                // 정의한 배열의 범위를 넘는경우
                if (x >= 0 && y >= 0 && x < n && y < m) {
                    // 배열의 값이 0, 방문한 경우
                    if (maze[x][y] != 0 && !visit[x][y]) {
                        // 다음에 갈 노드를 설정
                        q.add(new int[]{x, y});
                        visit[x][y] = true;
                        // 지나온 depth의 값을 저장하기위해 +1을 하여 저장한다.
                        maze[x][y] = maze[nowX][nowY] + 1;

                    }
                }
            }
        }

    }
}

백준 2606번 (그래프 탐색)

import java.util.Scanner;

public class problem220 {
    static int n;
    static int m;
    static boolean[][] arr;
    static boolean[] visit;
    static int x;
    static int y;
    static int result;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        m = in.nextInt();

        // 배열 초기화 (n까지 인덱스)
        arr = new boolean[n + 1][n + 1];
        visit = new boolean[n + 1];

        for (int i = 0; i < m; i++) {
            x = in.nextInt();
            y = in.nextInt();
            // 네트워크상 연결되어있다.
            arr[x][y] = arr[y][x] = true;
        }

        // 1번 노드부터 시작함
        DFS(1);
        System.out.print(result - 1);


    }
    private static void DFS(int a) {
        result++;
        visit[a] = true;
        for (int i = 1; i <= n; i++) {
            // 방문 하지 않았고, arr 배열의 값이 있을경우
            if (!visit[i] && arr[a][i]) {
                DFS(i);
            }
        }
    }
}

백준 10026번 (그래프 탐색)

import java.util.Scanner;

public class problem221 {
    static int n;
    static String str;
    static char[][] arr;
    static boolean[][] visit;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        // 배열 초기화
        arr = new char[n + 1][n + 1];
        visit = new boolean[n + 1][n + 1];

        for (int i = 0; i < n; i++) {
            str = in.next();
            for (int j = 0; j < n; j++) {
                arr[i][j] = str.charAt(j); // R R R B B 문자 저장
            }
        }
        // 적록색약이 아닌경우
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j]) {
                    DFS(i, j);
                    count++;
                }
            }
        }
        int normalCount = count;
        count = 0; // 초기화

        // 적록색약 인경우
        visit = new boolean[n+1][n+1];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(arr[i][j] == 'R'){
                    arr[i][j] = 'G'; // R을 G로 바꿔준다.
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!visit[i][j]) {
                    DFS(i, j);
                    count++;
                }
            }
        }
        int aCount = count;


        System.out.print(normalCount + " " + aCount);
    }

    private static void DFS(int a, int b) {
        visit[a][b] = true;
        char ch = arr[a][b];
        for(int i = 0; i < 4; i++){
            int nowX = a + dx[i];
            int nowY = b + dy[i];
            if(nowX >= 0 && nowY >= 0 && nowX < n && nowY < n ){
                // 방문하지 않은 노드이면서, 알파벳이 이어지는지 확인.
                if(!visit[nowX][nowY] && arr[nowX][nowY] == ch){
                    DFS(nowX,nowY);
                }
            }
        }
    }
}