DFS와 BFS(2606, 1012)

[바이러스 _ 2606]

 

 

 

* 로직

• 인접행렬로 각 노드를 연결한다
• 1번 노드부터 시작되기 때문에 해당 노드부터 DFS를 진행한다
• 인접한 노드를 찾고 마킹을 하게되면 count를 늘린다
• count를 출력한다 (단, 1번 노드도 count에 포함되었기 때문에 결과는 count-1을 출력한다)

 

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

public class Problem_2606 {

    static int nodeSize;
    static int[][] matrix;
    static boolean[] checked;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        nodeSize = Integer.parseInt(br.readLine());
        int t = Integer.parseInt(br.readLine());
        checked = new boolean[nodeSize +1];
        matrix = new int[nodeSize +1][nodeSize +1];

        //인접행렬
        for(int i=0; i<t; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            matrix[v1][v2] = 1;
            matrix[v2][v1] = 1;
        }

        //doDfs
        int infectedNode = 1;
        doDfs(infectedNode);

        System.out.println(count-1);
    }

    private static void doDfs(int index) {
        checked[index] = true;
        count++;

        for(int i=1; i<=nodeSize; ++i){
            if(!checked[i] && matrix[index][i] == 1){
                doDfs(i);
            }
        }
    }
}

 

 

[유기농 배추 _ 1012]

 

 

 

* 로직

• 맵을 돌면서 배추를 발견하면 해당 배추를 기준으로 인접한 배추들을 모두 마킹한다 (BFS)
• 인접한 배추 탐색이 끝나면 지렁이 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;

class Position_1012 {
    public int y,x;

    public Position_1012(int y, int x) {
        this.y = y;
        this.x = x;
    }
}

public class Problem_1012 {

    static int N, M;
    static int[][] map;
    static boolean[][] checked;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int testCase = Integer.parseInt(br.readLine());
        int t = 1;
        while (t <= testCase){
            String config = br.readLine();
            st = new StringTokenizer(config, " ");
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            map = new int[N][M];

            int plantNum = Integer.parseInt(st.nextToken());

            for(int i=0; i<plantNum; ++i){
                String input = br.readLine();
                st = new StringTokenizer(input, " ");

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                map[y][x] = 1;
            }

            checked = new boolean[N][M];
            int count = 0;
            for(int i=0; i<N; ++i){
                for(int j=0; j<M; ++j){
                    if(!checked[i][j] && map[i][j] == 1){
                        doBfs(i, j);
                        count++;
                    }
                }
            }

            System.out.println(count);
            t++;
        }
    }

    private static void doBfs(int y, int x) {
        Queue<Position_1012> queue = new LinkedList<>();
        queue.offer(new Position_1012(y, x));
        checked[y][x] = true;

        while (!queue.isEmpty()){
            Position_1012 q = queue.poll();

            for(int i=0; i<4; ++i){
                int moveY = q.y + dy[i];
                int moveX = q.x + dx[i];

                if(isRanged(moveY, moveX) && !checked[moveY][moveX] && map[moveY][moveX] == 1){
                    queue.offer(new Position_1012(moveY, moveX));
                    checked[moveY][moveX] = true;
                }
            }
        }
    }

    private static boolean isRanged(int y, int x) {
        if(y >=0 && y<N && x>=0 && x<M) return true;
        return false;
    }
}