<stdio.han>

https://www.acmicpc.net/problem/1012

[난이도]

- Silver 3

[알고리즘]

- bfs

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] visited;
    static int[][] graph;
    static int N, M, answer = 0;

    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int T = Integer.parseInt(st.nextToken());
        for (int i = 0; i < T; i++) { // T번 반복
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            graph = new int[N][M];
            visited = new boolean[N][M];
            ArrayList<int[]> list = new ArrayList<>();
            answer = 0;
            for (int j = 0; j < K; j++) { // 양배추 K개의 위치
                st = new StringTokenizer(br.readLine(), " ");
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                graph[X][Y] = 1;
                if (graph[X][Y] == 1) {
                    list.add(new int[]{X, Y});
                }
            }
            for (int k = 0; k < list.size(); k++) {
                int[] tmp = list.get(k);
                int x = tmp[0];
                int y = tmp[1];
                if (!visited[x][y]) { // 이미 체크한 양배추가 아닐 경우에만 bfs메서드 실행
                    bfs(x, y);
                    answer++;
                }
            }
            System.out.println(answer);

        }
        bw.flush();
        bw.close();
        br.close();
    }

    static void bfs(int x, int y) {
        visited[x][y] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp[0] + dx[i];
                int ny = tmp[1] + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (graph[nx][ny] == 1) {
                        if (!visited[nx][ny]) {
                            visited[nx][ny] = true;
                            queue.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
        }
    }
}

[풀이]

1. 각 양배추의 위치를 저장한다.

2. 방문하지 않은 양배추일 경우에는 bfs메서드를 실행한다.

3. bfs 메서드 : 4방탐색을 하며 양배추끼리 이어져있는지 확인한다.

병렬화를 사용하면 여러 프로세스 또는 스레드를 동시에 실행하여 작업을 처리한다. 이렇게 함으로써 여러 프로세서 또는 코어를 활용하여 작업을 분산시키고 병렬적으로 실행함으로써 전체 작업을 효율적으로 처리할 수 있다. 하지만 스트림 병렬화는 절대 시도조차 하지 말자.

데이터 소스가 Stream.iterate 거나 중간 연산으로 limit을 쓰면 파이프라인 병렬화로는 성능 개선을 기대할 수 없다. Stream.iterate 메서드는 무한한 요소 시퀀스를 생성하므로 병렬 처리가 어렵다. 또한 limit 메서드는 요소의 수를 제한하기 때문에 요소를 나누어 병렬 처리하는 것이 어려워진다. 이러한 상황에서는 파이프라인 병렬화로 성능 향상을 기대하기 어렵다.

스트림을 잘못 병렬화하면 (응답 불가를 포함해) 성능이 나빠질 뿐만 아니라  결과 자체가 잘못되거나 예상 못한 동작이 발생할 수 있다.

조건일 잘 갖춰지면 병렬화해 프로세스 코어 수에 비례하는 성능 향상을 만들 수 있지만, 그런 조건은 없다고 봐도 될 것같다.(개인적인생각)

핵심 정리 : 계산도 올바로 수행하고 성능도 빨라질 거라는 확신 없이는 스트림 파이프라인 병렬화는 시도조차 하지 말라. 스트림을 잘못 병렬화하면 프로그램을 오동작하게 하거나 성능을 급격히 떨어뜨린다. 병렬화하는 편이 낫다고 믿더라도, 수정 후의 코드가 여전히 정확한지 확인하고 운영 환경과 유사한 조건에서 수행해보며 성능지표를 유심히 관찰하라. 그래서 계산도 정확하고 성능도 좋아졌음이 확실해졌을 때, 오직 그럴 때만 병렬화 버전 코드를 운영 코드에 반영하라.

그냥 스트림 병렬화는 하지말자.

컬렉션(Collection):

• 일련의 객체를 저장하고 관리하는 자료구조.
• 주요 컬렉션 인터페이스에는 List, Set, Queue 등이 있으며, 각각 ArrayList, LinkedList, HashSet, TreeSet, PriorityQueue 등의 구현체가 있다.
• 컬렉션은 데이터를 저장하고 필요할 때 검색, 추가, 삭제 등의 작업을 수행할 수 있다.
• 컬렉션은 데이터의 저장 순서가 보장될 수 있고, 중복된 요소를 허용할 수도 있다.

스트림(Stream):

• 데이터를 처리하는 파이프라인 형태의 API.
• 자료 처리 연산을 지원하며, 이를 이용하여 데이터를 필터링, 매핑, 정렬, 그룹화하는 등의 작업을 수행할 수 있다.
• 스트림은 컬렉션, 배열, 파일 등의 데이터 소스에서 데이터를 가져와서 연속된 연산을 수행한다.
• 스트림은 데이터 소스를 변경하지 않고, 중간 연산과 최종 연산으로 구성되어 있다.
• 스트림은 데이터를 한 번만 처리할 수 있으며, 처리된 결과는 다시 스트림으로 반환되거나 최종 결과로 수집된다.

원소 시퀀스 : 데이터의 순서가 중요한 시퀀스 형태를 말한다. 이 시퀀스는 각각의 요소가 순서대로 나열되어 있으며, 각 요소는 고유한 위치(인덱스)를 가지고 있다. 대부분의 컬렉션과 배열은 원소 시퀀스로 간주될 수 있다.

Iterable : Java에서 컬렉션을 표현하기 위한 인터페이스다. 이 인터페이스는 컬렉션의 요소를 반복하는 데 사용된다.

핵심 정리 : 원소 시퀀스를 반환하는 메서드를 작성할 때는, 이를 스트림으로 처리하기를 원하는 사용자와 반복으로 처리하길 원하는 사용자가 모두 있을 수 있음을 떠올리고, 양쪽을 다 만족시키려 노력하자. 컬렉션을 반환할 수 있다면 그렇게 하라. 반환 전부터 이미 원소들을 컬렉션에 담아 관리하고 있거나 컬렉션을 하나 더 만들어도 될 정도로 원소 개수가 적다면 ArrayList 같은 표준 컬렉션 담아 반환하라. 그렇지 않으면 (반환할 시퀀스가 크지만 표현을 간결하게 할 수 있다면) 전용 컬렉션을 구현할지 고민하라. 컬렉션을 반환하는 게 불가능하면 스트림과 Iterable 중 더 자연스러운 것을 반환하라. 만약 나중에 Stream 인터페이스가 Iterable을 지원하도록 자바가 수정된다면, 그때는 안심하고 스트림을 반환하면 될 것이다(스트림 처리와 반복 모두에 사용할 수 있으니).

https://www.acmicpc.net/problem/25418

[난이도]

- Silver 3

[알고리즘]

- bfs

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int A, K, answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        A = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        bfs();
    }
    static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{A, 0});
        boolean[] visited = new boolean[K + 1];
        visited[A] = true;
        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            if (tmp[0] == K) {
                System.out.println(tmp[1]);
                return;
            }
            // 연산 1과 연산 2를 둘다 시행한다
            if (tmp[0] * 2 <= K) { // 연산 2
                visited[tmp[0] * 2] = true;
                queue.offer(new int[]{tmp[0] * 2, tmp[1] + 1});
            }
            if (!visited[tmp[0] + 1]) { // 연산 1, // 연산 2로 수행한 수가 연산 1보다 더 적은 연산횟수이기 때문에 이미 연산 2로 수행한 수라면 패스
                queue.offer(new int[]{tmp[0] + 1, tmp[1] + 1});
            }
        }
    }
}

[풀이]

1. 연산 2와 연산 1을 둘다 시행한다.

2. 연산 2가 가능하다면 연산 2를 시행하고. 연산 후의 숫자를 true로 체크한다.

3. 연산 1은 연산 2로 수행한 수가 연산 1보다 무조건 더 적은 연산횟수를 가지기 때문에 이미 연산 2로 수행한 수라면(!visited[tmp[0])라면 패스

제대로 풀이방법이 떠오르지 않았다. 비슷한 문제를 푼적이 있는데 DP로 푸는방법이 훨씬 간단했던것같다.

https://www.acmicpc.net/problem/2606

[난이도]

- Silver 3

[알고리즘]

- bfs

[코드]

import java.io.*;
import java.util.*;

public class Main {
    static int[][] graph;
    static boolean[] visited;
    static int n,m, answer = 0;


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        graph = new int[n + 1][n + 1]; // 0부터 시작이 아닌 1부터 시작이기 때문 n + 1
        visited = new boolean[n + 1];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph[u][v] = graph[v][u] = 1; // 양방향간선
        }

        bfs();
        System.out.println(answer);


    }
    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1); // 1부터 시작
        visited[1] = true; // 방문한 곳은 true
        while (!queue.isEmpty()) {
            int tmp = queue.poll();
            for (int i = 1; i <= n; i++) {
                if (graph[tmp][i] == 1 && !visited[i]) { // 현재번호와 연결된곳이면서 방문하지 않은 장소
                    queue.offer(i);
                    visited[i] = true;
                    answer ++;
                }
            }
        }
    }
}

[풀이]

1. 큐에 1을 담는다. (1번과 연결된것을 찾기 위함)

2. 큐에 담긴 번호와 연결된 노드이면서 방문하지않은 노드일 경우 큐에 연결된 노드를 담는다.

3. 큐가 빌때까지 반복한다.