2023.10.11.WED

[ 백준 ]

[ 2606번 바이러스 ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    static List<Integer>[] A;
    static boolean visited[];

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

        int n = Integer.parseInt(br.readLine());

        A = new List[n+1];
        for(int i=0; i<n+1; i++){
            A[i] = new ArrayList<>();
        }

        int m = Integer.parseInt(br.readLine());
        for(int i=0; i<m; i++){
            String[] split = br.readLine().split(" ");
            int s = Integer.parseInt(split[0]);
            int e = Integer.parseInt(split[1]);

            A[s].add(e);
            A[e].add(s);
        }

        visited = new boolean[n+1];
        System.out.println(BFS(1));
    }

    static int BFS(int x){
        visited[x] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(x);

        int answer = 0;

        while(queue.size()>0){
            int poll = queue.poll();
            for(int p : A[poll]){
                if(!visited[p]){
                    visited[p] = true;
                    queue.add(p);
                    answer++;
                }
            }
        }

        return answer;
    }
}

[ 1012번 유기농 배추 ]

: 에러나서 보니, dx, dy 더해준 후에 새로운 X, Y의 범위가 유효한지 조건문으로 검사하는 것을 빼먹었었음.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    static int[][] matrix;
    static boolean[][] visited;
    static int t, m, n, k;
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static List<int[]> list;

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

        t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            String[] split = br.readLine().split(" ");
            m = Integer.parseInt(split[0]);
            n = Integer.parseInt(split[1]);
            k = Integer.parseInt(split[2]);

            matrix = new int[m][n];
            list = new ArrayList<>();

            for (int j = 0; j < k; j++) {
                String[] spot = br.readLine().split(" ");
                int x = Integer.parseInt(spot[0]);
                int y = Integer.parseInt(spot[1]);
                matrix[x][y] = 1;
                list.add(new int[]{x, y});
            }

            visited = new boolean[m][n];
            System.out.println(BFS());
        }
    }

    static int BFS() {
        int answer = 0;

        for (int i = 0; i < list.size(); i++) {
            int[] now = list.get(i);
            int x = now[0];
            int y = now[1];

            if (!visited[x][y]) {
                visited[x][y] = true;
                answer++;

                Queue<int[]> queue = new LinkedList<>();
                queue.add(now);

                while (queue.size() > 0) {
                    int[] poll = queue.poll();
                    for (int j = 0; j < 4; j++) {
                        int X = poll[0] + dx[j];
                        int Y = poll[1] + dy[j];
                        if (X >= 0 && Y >= 0 && X < m && Y < n){
                            if (matrix[X][Y] == 1 && !visited[X][Y]) {
                                visited[X][Y] = true;
                                queue.add(new int[]{X, Y});
                            }
                        }
                    }
                }
            }
        }

        return answer;
    }
}

[ 느낀 점 ]

dp 어려워서 일단 BFS로 넘어왔다.
BFS 기본 문제는 풀 수 있음. 근데 응용하면 좀 막힘..ㅋㅋㅋㅋ
재귀에 약하므로 DFS는 해봐야 알 듯,,

알고리즘 어려워도 계속 해보는 수밖엔~~