<stdio.han>

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. 큐가 빌때까지 반복한다.

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

[난이도]

- Silver 4

[알고리즘]

- 부르트 포스

[코드]

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

public class Main {

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

        String before = br.readLine();
        String after = br.readLine();
        int beforeMin = Integer.parseInt(before.substring(3));
        int afterMin = Integer.parseInt(after.substring(3));
        int beforeHour = Integer.parseInt(before.substring(0, 2));
        int afterHour = Integer.parseInt(after.substring(0, 2));

        int answer = 0;
        while (beforeMin != afterMin) {
            beforeMin++;
            answer++;
            if (beforeMin == 60) {
                beforeMin -= 60;
                beforeHour++;
                if (beforeHour == 24) {
                    beforeHour-=24;
                }
            }
        }
        while (beforeHour != afterHour) {
            beforeHour++;
            answer++;
            if (beforeHour == 24) {
                beforeHour-=24;
            }
        }
        System.out.println(answer);

    }
}

[풀이]

bfs 알고리즘으로 풀어야하는데 어떻게 푸는지도 모르겠고 부르트 포스로 풀어버렸다.

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

[난이도]

- Silver 4

[알고리즘]

- 부르트 포스

[코드]

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

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 0;
        for (int i = 0; i < N; i++) {
            int sum = arr[i];
            int j=i;
            while (sum <= M) {
                if (sum == M) { // sum 이 N이 될경우 정답을 1 증가
                    answer++;
                    break;
                }
                j++;
                if (j >= N) { // j가 arr 인덱스를 넘어갈 경우 break
                    break;
                }
                sum+=arr[j];
            }
        }
        System.out.println(answer);
    }
}

[풀이]

1.i=0부터 arr[i] + arr[i+1] +... + arr[j-1] + arr[j] 를 구한다.

2. arr[i] + arr[i+1] +... + arr[j-1] + arr[j] 가 M일경우 i를 1 증가시키고 answer를 1증가시킨다.

3. answer 출력

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

[난이도]

- Silver 4

[알고리즘]

- bfs

[코드]

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

public class Main {
    static int N;
    static int[] dx = {1, 0}; // 아래, 오른쪽
    static int[] dy = {0, 1}; // 아래, 오른쪽
    static int[][] graph;
    static boolean[][] visited;
    static Queue<int[]> queue = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        graph = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < N; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        queue.add(new int[]{0, 0});
        visited[0][0] = true;

        bfs();

    }
    static void bfs() {
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            if (graph[x][y] == -1) {
                System.out.println("HaruHaru");
                return;
            }
            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i] * graph[x][y];
                int ny = y + dy[i] * graph[x][y];
                if (nx < N && ny < N && !visited[nx][ny]) { // graph 범위 내라면
                    queue.add(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        System.out.println("Hing");
    }
}

[풀이]

이동은 아래 혹은 오른쪽으로 밖에 이동하지 못하기 때문에 처음에는 방문한지역을 체크하는 visited 배열을 사용하지 않았었다. 하지만 게임판의 숫자는 0이상 100이하여서 0이 적혀있을 경우 제자리를 계속 방문하게 되어 메모리 초과가 발생하기 때문에 이를 해결하기위해 visited 배열을 추가했다.

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

[난이도]

- Silver 4

[알고리즘]

- bfs

[코드]

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

public class Main {
    static int R, C;
    static char[][] graph;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        graph = new char[R][C];
        visited = new boolean[R][C];
        int answer = 0;

        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i][j] = input.charAt(j);
            }
        }
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (graph[i][j] == '#') { // if graph[i][j] is grass
                    if (!visited[i][j]) {
                        bfs(i, j);
                        answer++;
                    }
                }
            }
        }
        System.out.println(answer);
    }

    static void bfs(int r, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{r, c});
        visited[r][c] = true;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < R && ny >= 0 && ny < C) { // if 'nx' and 'ny' are inside of map
                    if (!visited[nx][ny]) { // and have never visited
                        if (graph[nx][ny] == '#') {
                            visited[nx][ny] = true; // turn visited[nx][ny] true
                            queue.add(new int[]{nx, ny}); // add queue
                        }
                    }
                }
            }
        }
    }
}

[풀이]

1. Using a double for loop, we check if graph[i][j] represents grass and has not been visited before. If so, we perform bfs(i, j).

2. Upon visiting, we mark the location as visited by setting it to true and explore adjacent grass patches using the 4-directional search logic.

3. Finally, we print the numbber of grass clumps.

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

[난이도]

- Silver 4

[알고리즘]

- bfs

[코드]

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

public class Main {
    static char[][] graph = new char[10][10];
    static boolean[][] visited = new boolean[10][10];
    static int[] dx = {-1, 1, 0, 0}; // 상, 하, 좌, 우
    static int[] dy = {0, 0, -1, 1}; // 상, 하, 좌, 우
    static Queue<int[]> queue = new LinkedList<>();
    static int answer = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        for (int i = 0; i < 10; i++) {
            String input = br.readLine();
            for (int j = 0; j < 10; j++) {
                graph[i][j] = input.charAt(j);
                if (graph[i][j] == 'L') {
                    queue.add(new int[]{i, j, 0});
                    visited[i][j] = true;
                }
            }
        }

        bfs();
        System.out.println(answer - 1); // B 제외하고 출력해줘야함


    }

    static void bfs() {
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int cows = tmp[2];
            if (graph[x][y] == 'B') {
                answer = Math.min(answer, cows);
            }
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < 10 && ny >= 0 && ny < 10) { // graph 내부안에서만 가능
                    if (!visited[nx][ny]) { // 방문하지 않은 지역
                        if (graph[nx][ny] != 'R') { // 돌이 있을 경우 돌아가야함
                            visited[nx][ny] = true; // 방문한곳으로 표시
                            queue.add(new int[]{nx, ny, cows + 1}); // 소의 개수를 1씩 늘림
                        }
                    }
                }
            }
        }
    }
}

[풀이]

Queue에 x와 y의 좌표뿐만아니라 소의 개수를 1씩 늘리면서 큐에담아주어야 B까지 도착했을 때의 소의 개수를 알 수가 있다.

수집기(collector) : 스트림의 최종 연산(terminal operation) 중 하나로, 스트림의 요소를 수집하여 다양한 형태로 결과를 생성하거나 반환하는 역할을 한다.  

1. toList(): 스트림의 요소를 리스트로 수집한다.
2. toSet(): 스트림의 요소를 집합(Set)으로 수집한다.
3. toMap(): 스트림의 요소를 맵(Map)으로 수집한다.
4. joining(): 문자열 요소를 하나의 문자열로 연결한다.
5. groupingBy(): 지정된 기준에 따라 스트림의 요소를 그룹화한다.

스트림과 수집기를 사용한 예시

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        List<String> words = Arrays.asList("apple", "banana", "grape", "watermelon", "orange");

        // 길이가 5 이상인 단어들을 대문자로 변환하여 리스트로 수집
        List<String> result = words.stream()
                                   .filter(word -> word.length() >= 5) // 길이가 5 이상인 단어 필터링
                                   .map(String::toUpperCase)           // 대문자로 변환
                                   .collect(Collectors.toList());      // 리스트로 수집

        // 결과 출력
        System.out.println("Result: " + result);
    }
}

핵심 정리 : 스트림 파이프라인 프래그래밍의 핵심은 부작용 없는 함수 객체에 있다. 스트림뿐 아니라 스트림 관련 객체에 건네지는 모든 함수 객체가 부작용이 없어야 한다. 종단 연산 중 forEach는 스트림이 수행한 계산 결과를 보고할 때만 이용해야 한다. 계산 자체에는 이용하지 말자. 스트림을 올바로 사용하려면 수집기를 잘 알아둬야 한다. 가장 중요한 수집기 팩터리는 toList, toSet, toMap, groupingBy, joining이다.

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

[난이도]

- Silver 4

[알고리즘]

- 부르트 포스

[코드]

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

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

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

        if (N < 100) {
            System.out.println(N);
        } else {
            int answer = 99;
            for (int i = 100; i <= N; i++) {
                int hundreds = i / 100; // 100의 자리
                int tens = (i / 10) % 10; // 10의 자리
                int units = (i % 10); // 1의 자리
                if ((hundreds - tens) == (tens - units)) {
                    answer++;
                }
            }
            System.out.println(answer);
        }
    }
}

[풀이]

N이 99이하일 경우에는 모든 수가 등차수열을 이룬다.

N이 100이상일 경우에는 (100의 자리 - 10의 자리) == (10의 자리 1의 자리) 일 경우에 등차수열을 이룬다 라고 말할 수 있다.