<stdio.han>

[문제 링크]

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

[난이도]

- Gold 5

[알고리즘]

- 백트래킹

[코드]

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

public class Main {
    static int N, M;
    static ArrayList<ArrayList<Integer>> adj;
    static boolean[] visited;
    static boolean found = false;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        adj = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            adj.add(new ArrayList<>()); // 정점의 수만큼 생성
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            adj.get(a).add(b); // 양방향 간선
            adj.get(b).add(a); // 양방향 간선
        }

        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            if (!found) { // ABCDE가 존재하면 true 발견하지 못했다면 false
                dfs(i, 0);
            }
        }

        System.out.println(found ? 1 : 0);
    }

    static void dfs(int node, int depth) {
        if (depth == 4) { // depth가 4면 ABCDE가 서로 연결되어있다는 뜻
            found = true;
            return;
        }

        visited[node] = true;

        for (int next : adj.get(node)) {
            if (!visited[next]) { // 중복방문을 방지
                dfs(next, depth + 1);
                if (found) return;
            }
        }

        visited[node] = false; // 완전탐색을위해 다시 false로 변경
    }
}

[풀이]

이중 ArrayList로 인정리스트인 Adjacency list를 선언해준후.

각 정점을 기준으로 dfs를 반복해 depth가 4인경우를 찾아준다.

depth가 4일경우 ABCDE가 친구인 경우이다.

찾았다면 1을 못찾았다면 0을 출력한다.

[문제 링크]

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

[난이도]

- Gold 4

[알고리즘]

- BFS

[코드]

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

public class Main {
    static int N, M;
    static int[][] map;
    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());

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

        map = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int year = 0;
        while (true) {
            year++;
            // 1년 경과 후 빙산의 높이를 줄입니다.
            int[][] nextMap = new int[N][M];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (map[i][j] > 0) {
                        int count = 0;
                        for (int d = 0; d < 4; d++) {
                            int ni = i + dx[d];
                            int nj = j + dy[d];
                            if (map[ni][nj] == 0) {
                                count++;
                            }
                        }
                        nextMap[i][j] = Math.max(0, map[i][j] - count);
                    }
                }
            }
            map = nextMap;

            // 빙산 덩어리 개수를 셉니다.
            int count = countIcebergs();
            if (count == 0) {
                // 모든 빙산이 녹음
                System.out.println(0);
                break;
            } else if (count > 1) {
                // 두 개 이상의 덩어리로 분리됨
                System.out.println(year);
                break;
            }
        }
    }

    static int countIcebergs() {
        visited = new boolean[N][M];
        int count = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] > 0 && !visited[i][j]) {
                    bfs(i, j);
                    count++;
                }
            }
        }

        return count;
    }

    static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

            for (int d = 0; d < 4; d++) {
                int nx = cx + dx[d];
                int ny = cy + dy[d];

                if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] > 0 && !visited[nx][ny]) {
                    queue.add(new int[] {nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

[풀이]

문제를 하나하나 풀어 여러 단계로 나누어보면 간단한문제이다. 

1. 1년이 지난후의 지도를 새로 작성한다.

2. 새로운 지도의 빙산개수를 센다.

3. 빙산개수가 0개 혹은 2개이상일 경우 종료한다.

4. 빙산개수가 1개일 경우 1~2를 반복한다.

[문제 링크]

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

[난이도]

-Gold 5

[알고리즘]

- BFS

[코드]

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

public class Main {
    static int max = 100000;
    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 K = Integer.parseInt(st.nextToken());

        boolean[] visited = new boolean[max + 1];

        // BFS를 위한 큐 초기화
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{N, 0});

        int answer = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int current = tmp[0]; // 현재 위치
            int time = tmp[1];
            visited[current] = true;

            // 동생의 위치에 도달하면 종료
            if (current == K) {
                answer = Math.min(answer, time);
            }

            // 가능한 이동
            if (current * 2 <= max && !visited[current * 2]) {
                queue.offer(new int[]{current * 2, time});
            }
            if (current + 1 <= max && !visited[current + 1]) {
                queue.offer(new int[]{current + 1, time + 1});
            }
            if (current - 1 >= 0 && !visited[current - 1]) {
                queue.offer(new int[]{current - 1, time + 1});
            }
        }
        System.out.println(answer);
    }
}

[풀이]

순간이동할때와 걸어서 이동할때 모두를 고려해서 계산해야 한다.

[문제 링크]

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

[난이도]

- Gold 5

[알고리즘]

- BFS

[코드]

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

public class Main {
    static int L, W;
    static char[][] graph;
    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());

        L = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        graph = new char[L][W];
        Queue<int[]> LandPos = new LinkedList<>();
        for (int i = 0; i < L; i++) {
            String input = br.readLine();
            for (int j = 0; j < W; j++) {
                graph[i][j] = input.charAt(j);
                if (graph[i][j] == 'L') {
                    LandPos.add(new int[]{i, j});
                }
            }
        }

        int Treasure = 0;
        while (!LandPos.isEmpty()) {
            int[] Land = LandPos.poll();
            int LandX = Land[0];
            int LandY = Land[1];
            Treasure = Math.max(Treasure, bfs(LandX, LandY));
        }
        System.out.println(Treasure);
    }

    static int bfs(int LandX, int LandY) {
        int max = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{LandX, LandY, 0});
        boolean[][] visited = new boolean[L][W];
        visited[LandX][LandY] = true;
        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int x = tmp[0];
            int y = tmp[1];
            int count = tmp[2];
            max = Math.max(max, count);
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < L && ny >= 0 && ny < W) {
                    if (!visited[nx][ny]) {
                        if (graph[nx][ny] == 'L') {
                            visited[nx][ny] = true;
                            queue.add(new int[]{nx, ny, count + 1});
                        }
                    }
                }
            }
        }
        return max;
    }
}

[풀이]

입력을 받을 때 모든 육지인 좌표를 큐에 담아둔 후, 큐에서 하나씩 꺼내며 해당 좌표를 시작으로 4방탐색을 반복해서(육지의 개수만큼) 실행해야 한다. 4방탐색을 하며 한칸 이동할 때 마다 count를 1씩 증가시키고 그 count의 최대값 return 해준다. return 해준 값들 중 최대값을 다시 찾아 출력해준다.

[문제 링크]

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

[난이도]

- Silver 1

[알고리즘]

- BFS

[코드]

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());


        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        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.get(u).add(v);
            graph.get(v).add(u);
        }

        int KB[] = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            int[] distance = new int[N + 1];
            Arrays.fill(distance, -1);
            distance[i] = 0;
            while (!queue.isEmpty()) {
                int current = queue.poll();
                for (int next : graph.get(current)) {
                    if (distance[next] == -1) {
                        distance[next] = distance[current] + 1;
                        queue.add(next);
                    }
                }
            }
            int sum = 0;
            for (int j = 1; j < N + 1; j++) {
                sum += distance[j];
            }
            KB[i] = sum;
        }

        int min = Integer.MAX_VALUE;
        int answer = 0;
        for (int i = 1; i < N + 1; i++) {
            if (KB[i] < min) {
                min = KB[i];
                answer = i;
            }
        }
        System.out.println(answer);
    }
}

[풀이]

이중 list를 선언해 각 정점과 양방향으로 연결된 정점을 초기화해준다.

정점과 연결된 다른 정점과의 거리를 distance 배열에 추가한다. 이 로직을 N번 반복해 각 정점을 기준으로 계산해준다.

            Queue<Integer> queue = new LinkedList<>();
            queue.add(i);
            int[] distance = new int[N + 1];
            Arrays.fill(distance, -1);
            distance[i] = 0;
            while (!queue.isEmpty()) {
                int current = queue.poll();
                for (int next : graph.get(current)) {
                    if (distance[next] == -1) {
                        distance[next] = distance[current] + 1;
                        queue.add(next);
                    }
                }
            }

계산한 케빈베이컨 수중 가장 작은값의 인덱스를 출력해준다.

        for (int i = 1; i < N + 1; i++) {
            if (KB[i] < min) {
                min = KB[i];
                answer = i;
            }
        }

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- BFS

[코드]

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 K = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }

        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.get(u).add(v); // 단방향 간선
        }

        int[] distance = new int[N + 1];
        Arrays.fill(distance, -1);
        distance[X] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(X);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            for (int next : graph.get(current)) {
                if (distance[next] == -1) { // 방문한 노드와 방문하지 않는 노드를 체크하는 용도로 사용
                    distance[next] = distance[current] + 1; // 전 노드까지의 거리 + 1
                    queue.add(next);
                }
            }
        }

        boolean found = false;
        for (int i = 1; i <= N; i++) {
            if (distance[i] == K) { // 거리가 K인것만 출력
                System.out.println(i);
                found = true;
            }
        }

        if (!found) {
            System.out.println(-1);
        }
    }
}

[풀이]

이중 list로 노드와 간선을 구성하고 큐로 시작노드와 연결된 노드를 찾으며 거리를 계산한다.

[문제 링크]

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

[난이도]

- Silver 2

[알고리즘]

- BFS

[코드]

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));
        int n = Integer.parseInt(br.readLine());

        List<List<Integer>> tree = new ArrayList<>(); // 트리 선언
        for (int i = 0; i < n + 1; i++) {
            tree.add(new ArrayList<>()); // 자식노드가 없는 정점 n+1개 생성
        }

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            tree.get(u).add(v);
            tree.get(v).add(u);
        }

        int[] parent = new int[n + 1]; // 각 노드의 부모를 저장
        boolean[] visited = new boolean[n + 1]; // 노드 방문 여부를 체크
        Queue<Integer> queue = new LinkedList<>(); // 큐를 사용해 bfs로직 수행
        queue.add(1); // 루트노드는 1
        visited[1] = true; // 루트노드는 방문함

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에 담긴 노드를 선택
            for (int neighbor : tree.get(node)) { // 선택한 노드와 연결된 모든 노드를 탐색
                if (!visited[neighbor]) { // 선택한 노드와 연결된 노드가 방문하지 않았다면 진행
                    visited[neighbor] = true; // 방문한것으로 체크
                    parent[neighbor] = node; // 선택한 노드와 연결된 노드는 선택한 노드의 자식임
                    queue.add(neighbor); // 큐에 추가
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 2; i <= n; i++) { // 2번노드부터 부모노드를 출력
            sb.append(parent[i]).append('\n');
        }

        System.out.print(sb);
    }
}

[풀이]

트리구조, 노드 탐색문제는 많이 나오기 때문에 트리구조를 선언하는법, 자식노드를 추가하는법 등을 알아두어야 한다고 생각한다. 

2중 list를 활용해 트리구조를 선언 한다. 무엇이 부모, 자식 관계가 없는 단순 쌍방으로 연결된 구조이다.

List<List<Integer>> tree = new ArrayList<>(); // 트리 선언

for문을 활용해 정점를 생성한다. list구조이기 때문에 가변적으로 연결된 정점을 추가할 수 있다.

        for (int i = 0; i < n + 1; i++) {
            tree.add(new ArrayList<>()); // 정점 n+1개 생성
        }

양방향으로 연결된 간선이므로 각 정점에 서로 추가해준다.

        for (int i = 0; i < n - 1; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            tree.get(u).add(v);
            tree.get(v).add(u);
        }

parent[n] 는 n정점의 부모노드의 정보를 담은 배열. ex) parent[2] = 4, 2번 정점의 부모노드는 4임.

이미 방문한 노드는 재방문하면 안되므로 visited배열로 체크해준다.

루트노드는 1로 문제에서 정해주었다. 루트노드부터 bfs를 시작하기위해 큐에 담아준다.

        int[] parent = new int[n + 1]; // 각 노드의 부모를 저장
        boolean[] visited = new boolean[n + 1]; // 노드 방문 여부를 체크
        Queue<Integer> queue = new LinkedList<>(); // 큐를 사용해 bfs로직 수행
        queue.add(1); // 루트노드는 1
        visited[1] = true; // 루트노드는 방문함

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에 담긴 노드를 선택
            for (int neighbor : tree.get(node)) { // 선택한 노드와 연결된 모든 노드를 탐색
                if (!visited[neighbor]) { // 선택한 노드와 연결된 노드가 방문하지 않았다면 진행
                    visited[neighbor] = true; // 방문한것으로 체크
                    parent[neighbor] = node; // 선택한 노드와 연결된 노드는 선택한 노드의 자식임
                    queue.add(neighbor); // 큐에 추가
                }
            }
        }

[문제 링크]

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

[난이도]

- Silver 1 

[알고리즘]

- DP

[코드]

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));

        int n = Integer.parseInt(br.readLine());
        int[][] triangle = new int[n][]; // 2차원은 가변적으로 선언
        int[][] dp = new int[n][]; // 2차원은 가변적으로 선언

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            triangle[i] = new int[i + 1];
            dp[i] = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                triangle[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 초기값 설정
        dp[0][0] = triangle[0][0];

        // dp 배열 채우기
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0) { //
                    dp[i][j] = dp[i - 1][j] + triangle[i][j];
                } else if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
                }
            }
        }

        // dp배열의 마지막 열중 최대값 출력
        int maxSum = 0;
        for (int j = 0; j < n; j++) {
            maxSum = Math.max(maxSum, dp[n - 1][j]);
        }

        System.out.println(maxSum);
    }
}

[풀이]

dp 2차원 배열은 정사각형일 필요가 없으므로 입력받을 때 마다 2차원배열의 2차원의 크기를 i+1 로 초기화 해준다.

        int[][] triangle = new int[n][]; // 2차원은 가변적으로 선언
        int[][] dp = new int[n][]; // 2차원은 가변적으로 선언

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            triangle[i] = new int[i + 1];
            dp[i] = new int[i + 1];
            for (int j = 0; j <= i; j++) {
                triangle[i][j] = Integer.parseInt(st.nextToken());
            }
        }

dp배열의 점화식은 아래와 같다.

dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];

dp[i][j] 는 dp[i-1][j-1]와 dp[i-1][j] 두 수를 비교해 둘중 큰 값을 선택한다. 하지만 여기서 문제가있다.

삼각형중 가장 왼쪽의 수와 가장 오른쪽의 수는 두 수를 비교할 수가 없다.

가장 왼쪽의 수는 비교할 수가 하나밖에없어 무조건 dp[i-1][j]를 선택해야만 한다. 그래서 따로 조건문을 만들어준다.

		if (j == 0) { //
                    dp[i][j] = dp[i - 1][j] + triangle[i][j];
                }

삼각형의 가장 오른쪽의 수도 비교할 수가 하나밖에 없기때문에 무조건 dp[i-1][j-1]를 선택해야만 한다.

		else if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                }