<stdio.han>

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까지 도착했을 때의 소의 개수를 알 수가 있다.