[Coding Test] SWEA(2)

1. 명진이와 동휘의 숫자 맞추기 (9611) - D3

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

public class P9611_명진이와동휘의숫자맞추기 {

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

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

        for (int test_case = 1; test_case <= Q; test_case++) {
            int[] visit = new int[10];

            int N = Integer.parseInt(br.readLine());
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
                String str = st.nextToken();

                if (str.equals("NO")) {
                    visit[a] = -1;
                    visit[b] = -1;
                    visit[c] = -1;
                    visit[d] = -1;
                } else if (str.equals("YES")) {
                    if (visit[a] != -1) {
                        visit[a]++;
                    }
                    if (visit[b] != -1) {
                        visit[b]++;
                    }
                    if (visit[c] != -1) {
                        visit[c]++;
                    }
                    if (visit[d] != -1) {
                        visit[d]++;
                    }
                }
            }

            int max = 0;
            for (int i = 0; i < 10; i++) {
                if (visit[max] < visit[i]) {
                    max = i;
                }
            }

            bw.write("#" + test_case + " " + max + "\n");
        }

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

---

2. View (1206) - D3

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

public class P1206_View {

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            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 = 2; i < N - 2; i++) {
                int leftMax = Math.max(arr[i - 1], arr[i - 2]);
                int rightMax = Math.max(arr[i + 1], arr[i + 2]);
                int max = Math.max(leftMax, rightMax);

                if (arr[i] > max) {
                    answer += (arr[i] - max);
                }
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

---

3. 최대 상금 (1244) - D3

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

public class P1244_최대상금 {
    static int chance;
    static int answer;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            char[] ch = st.nextToken().toCharArray();
            chance = Integer.parseInt(st.nextToken());
            if (ch.length < chance) {
                chance = ch.length;
            }
            answer = 0;
            dfs(ch, 0);
            bw.write("#" + test_case + " " + answer + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(char[] ch, int depth) {
        if (depth >= chance) {
            String str = "";
            for (int i = 0; i < ch.length; i++) {
                str += ch[i];
            }

            answer = Math.max(answer, Integer.parseInt(str));
            return;
        }

        for (int i = 0; i < ch.length - 1; i++) {
            for (int j = i + 1; j < ch.length; j++) {
                char temp = ch[i];
                ch[i] = ch[j];
                ch[j] = temp;

                dfs(ch, depth + 1);

                char temp1 = ch[i];
                ch[i] = ch[j];
                ch[j] = temp1;
            }
        }
    }
}

---

4. Flatten (1208) - D3

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

public class P1208_Flatten {
    static int chance;
    static int answer;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            int[] arr = new int[100];

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

            while (N > 0) {
                int max = 0;
                int min = 0;

                for (int i = 0; i < 100; i++) {
                    if (arr[max] < arr[i]) {
                        max = i;
                    }

                    if (arr[min] > arr[i]) {
                        min = i;
                    }
                }
                arr[max]--;
                arr[min]++;
                N--;
            }

            int max = 0;
            int min = 0;

            for (int i = 0; i < 100; i++) {
                if (arr[max] < arr[i]) {
                    max = i;
                }

                if (arr[min] > arr[i]) {
                    min = i;
                }

            }

            int answer = arr[max] - arr[min];
            bw.write("#" + test_case + " " + answer + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

---

5. N-Queen (2806) - D3

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

public class P2806_Queen {
    static int N;
    static int answer;
    static int[] arr;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            arr = new int[N];
            answer = 0;

            dfs(0);

            bw.write("#" + test_case + " " + answer + " \n");
        }

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

    public static void dfs(int depth) {
        if (depth >= N) {
            answer++;
            return;
        }

        for (int i = 0; i < N; i++) {
            arr[depth] = i;
            if (isPossible(depth)) {
                dfs(depth + 1);
            }
        }
    }

    public static boolean isPossible(int depth) {
        for (int i = 0; i < depth; i++) {
            if (arr[i] == arr[depth]) {
                return false;
            }

            if (Math.abs(i - depth) == Math.abs(arr[i] - arr[depth])) {
                return false;
            }
        }

        return true;
    }
}

---

6. 백만 장자 프로젝트 (1859) - D2

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

public class P1859_백만장자프로젝트 {
    static int N;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            int[] arr = new int[N];

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

            long answer = 0;
            int cnt = 0;
            int start = 0;
            int end = 0;

            while (cnt < N) {
                end = max(start, arr);
                for (int i = start; i <= end; i++) {
                    cnt++;
                    answer += arr[end] - arr[i];
                }
                start = end + 1;
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

    public static int max(int start, int[] arr) {
        int max = start;
        for (int i = start; i < N; i++) {
            if (arr[max] <= arr[i]) {
                max = i;
            }
        }

        return max;
    }
}

---

7. 달팽이 숫자 (1954) - D2

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

public class P1954_달팽이숫자 {
    static int N;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            int[][] arr = new int[N][N];

            int x = 0;
            int y = 0;

            int cnt = 1;
            int value = 1;
            while (value <= N * N) {
                if (cnt == 1) {
                    while (true) {
                        if (y >= N) {
                            y--;
                            x++;
                            break;
                        }

                        if (arr[x][y] != 0) {
                            y--;
                            x++;
                            break;
                        }

                        arr[x][y] = value;
                        value++;
                        y++;
                    }
                } else if (cnt == 2) {
                    while (true) {
                        if (x >= N) {
                            x--;
                            y--;
                            break;
                        }

                        if (arr[x][y] != 0) {
                            x--;
                            y--;
                            break;
                        }

                        arr[x][y] = value;
                        value++;
                        x++;
                    }
                } else if (cnt == 3) {
                    while (true) {
                        if (y < 0) {
                            y = 0;
                            x--;
                            break;
                        }

                        if (arr[x][y] != 0) {
                            y++;
                            x--;
                            break;
                        }

                        arr[x][y] = value;
                        value++;
                        y--;
                    }
                } else if (cnt == 4) {
                    while (true) {
                        if (x < 0) {
                            x = 0;
                            y++;
                            break;
                        }

                        if (arr[x][y] != 0) {
                            x++;
                            y++;
                            break;
                        }

                        arr[x][y] = value;
                        value++;
                        x--;
                    }
                }

                cnt++;
                if (cnt == 5) {
                    cnt = 1;
                }
            }

            bw.write("#" + test_case + "\n");
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    bw.write(arr[i][j] + " ");
                }
                bw.write("\n");
            }
        }

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

    public static int max(int start, int[] arr) {
        int max = start;
        for (int i = start; i < N; i++) {
            if (arr[max] <= arr[i]) {
                max = i;
            }
        }

        return max;
    }
}

---

8. 최빈수 구하기 (1204) - D2

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

public class P1204_최빈수구하기 {

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            int t = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine());

            int[] arr = new int[101];
            for (int i = 0; i < 1000; i++) {
                arr[Integer.parseInt(st.nextToken())]++;
            }

            int max = 0;
            for (int i = 0; i <= 100; i++) {
                if (arr[max] <= arr[i]) {
                    max = i;
                }
            }

            bw.write("#" + t + " " + max + "\n");
        }

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

---

9. 보급로 (1249) - D4

1. bfs

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

class P1249_보급로 {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static int N;
    static int[][] arr;
    static int[][] sum;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            arr = new int[N][N];
            sum = new int[N][N];

            for (int i = 0; i < N; i++) {
                char[] ch = br.readLine().toCharArray();
                for (int j = 0; j < ch.length; j++) {
                    arr[i][j] = (char) (ch[j] - '0');
                }
            }

            for (int i = 0; i < N; i++) {
                Arrays.fill(sum[i], Integer.MAX_VALUE);
            }

            sum[0][0] = 0;
            bfs();
            bw.write("#" + test_case + " " + sum[N - 1][N - 1] + "\n");
        }

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

    public static void bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int x = now[0] + dx[i];
                int y = now[1] + dy[i];

                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (sum[x][y] > sum[now[0]][now[1]] + arr[x][y]) {
                        sum[x][y] = sum[now[0]][now[1]] + arr[x][y];
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
    }
}

2. dfs

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

class P1249_보급로 {
    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, -1, 1, 0};
    static int N;
    static int answer;
    static int[][] arr;
    static int[][] sum;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            arr = new int[N][N];
            sum = new int[N][N];

            for (int i = 0; i < N; i++) {
                char[] ch = br.readLine().toCharArray();
                for (int j = 0; j < ch.length; j++) {
                    arr[i][j] = (char) (ch[j] - '0');
                }
            }

            for (int i = 0; i < N; i++) {
                Arrays.fill(sum[i], Integer.MAX_VALUE);
            }

            answer = Integer.MAX_VALUE;
            sum[0][0] = 0;
            dfs(0, 0);
            bw.write("#" + test_case + " " + sum[N - 1][N - 1] + "\n");
        }

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

    public static void dfs(int a, int b) {
        if (a == N - 1 && b == N - 1) {
            answer = Math.min(answer, sum[a][b]);
            return;
        }

        if (answer < sum[a][b]) {
            return;
        }

        for (int i = 0; i < 4; i++) {
            int x = a + dx[i];
            int y = b + dy[i];

            if (x >= 0 && y >= 0 && x < N && y < N) {
                if (sum[x][y] > sum[a][b] + arr[x][y]) {
                    sum[x][y] = sum[a][b] + arr[x][y];
                    dfs(x, y);
                }
            }
        }
    }
}

---

10. 가능한 시험 점수 (3752) - D4

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

class P3752_가능한시험점수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = new int[N];

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

            HashSet<Integer> set = new HashSet<>();
            set.add(0);

            for (int i = 0; i < N; i++) {
                HashSet<Integer> newSet = new HashSet<>();
                for (int num : set) {
                    newSet.add(num + arr[i]);
                }

                set.addAll(newSet);
            }

            bw.write("#" + test_case + " " + set.size() + "\n");
        }

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

---

11. 격자판의 숫자 이어 붙이기 (2819) - D4

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

class P2819_격자판의숫자이어붙이기 {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static HashSet<Integer> set;
    static int[][] arr;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            arr = new int[4][4];
            set = new HashSet<>();
            for (int i = 0; i < 4; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 4; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    dfs("", i, j, 0);
                }
            }

            bw.write("#" + test_case + " " + set.size() + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    public static void dfs(String str, int a, int b, int depth) {
        if (depth == 7) {
            set.add(Integer.parseInt(str));
            return;
        }

        for (int i = 0; i < 4; i++) {
            int x = a + dx[i];
            int y = b + dy[i];

            if (x >= 0 && y >= 0 && x < 4 && y < 4) {
                dfs(str + String.valueOf(arr[a][b]), x, y, depth + 1);
            }
        }
    }
}

---

12. 농작물 수확하기 (2805) - D3

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

class P2805_농작물수확하기 {

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            int[][] arr = new int[N][N];

            for (int i = 0; i < N; i++) {
                char[] ch = br.readLine().toCharArray();

                for (int j = 0; j < ch.length; j++) {
                    arr[i][j] = (char) (ch[j] - '0');
                }
            }

            int mid = N / 2;
            int answer = 0;

            int start = mid;
            int end = mid;

            for (int i = 0; i <= mid; i++) {
                for (int j = start; j <= end; j++) {
                    answer += arr[i][j];
                }
                if (i == mid) {
                    continue;
                }
                start--;
                end++;
            }

            start++;
            end--;

            for (int i = mid + 1; i < N; i++) {
                for (int j = start; j <= end; j++) {
                    answer += arr[i][j];
                }
                start++;
                end--;
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

---

13. 햄버거 다이어트 (5215) - D3

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

class P5215_햄버거다이어트 {
    static int N;
    static int L;
    static int[][] arr;
    static boolean[] visited;
    static int answer;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            L = Integer.parseInt(st.nextToken());

            visited = new boolean[N];
            arr = new int[N][2];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                arr[i][0] = Integer.parseInt(st.nextToken());
                arr[i][1] = Integer.parseInt(st.nextToken());
            }

            answer = 0;
            dfs(0, 0, 0);

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

    public static void dfs(int idx, int score, int cal) {
        if (cal > L) {
            return;
        }

        if (idx == N) {
            answer = Math.max(answer, score);
            return;
        }

        dfs(idx + 1, score + arr[idx][0], cal + arr[idx][1]);
        dfs(idx + 1, score, cal);
    }
}

---

14. Ladder1 (1210) - D4

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

class P1210_Ladder1 {
    static int[] dx = {0, 0, 1};
    static int[] dy = {1, -1, 0};
    static int[][] arr;
    static boolean[][] visited;
    static int answer;
    static int result;

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            int t = Integer.parseInt(br.readLine());
            arr = new int[100][100];
            for (int i = 0; i < 100; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < 100; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            answer = 0;
            result = -1;
            for (int i = 0; i < 100; i++) {
                if (arr[0][i] == 1) {
                    visited = new boolean[100][100];
                    visited[0][i] = true;
                    dfs(0, i);

                    if (result != -1) {
                        answer = i;
                        break;
                    }
                }
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

    public static void dfs(int a, int b) {

        if (a == 99) {
            if (arr[a][b] == 2) {
                result = 2;
            }
        }

        for (int i = 0; i < 3; i++) {

            int x = a + dx[i];
            int y = b + dy[i];

            if (x >= 0 && y >= 0 && x < 100 && y < 100) {
                if (!visited[x][y] && arr[x][y] == 1 || arr[x][y] == 2) {
                    visited[x][y] = true;
                    dfs(x, y);
                    break;
                }
            }
        }
    }
}

---

15. 원재의 메모리 복구하기 (1289) - D3

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

class P1289_원재의메모리복구하기 {

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            char[] ch = br.readLine().toCharArray();
            int answer = 0;
            char now = '0';
            for (int i = 0; i < ch.length; i++) {
                if (ch[i] != now) {
                    answer++;
                    now = ch[i];
                }
            }
            bw.write("#" + test_case + " " + answer + "\n");
        }

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

---

16. 회문1 (1215) - D3

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

class P1215_회문1 {

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            char[][] arr = new char[8][8];

            for (int i = 0; i < 8; i++) {
                arr[i] = br.readLine().toCharArray();
            }

            int answer = 0;

            for (int i = 0; i < 8; i++) {        //가로
                for (int k = 0; k <= 8 - N; k++) {
                    int start = k;
                    int end = start + N;

                    String str = "";
                    for (int j = start; j < end; j++) {
                        str += arr[i][j];
                    }

                    sb = new StringBuilder(str);
                    String reverseStr = sb.reverse().toString();

                    if (str.equals(reverseStr)) {
                        answer++;
                    }

                    sb.setLength(0);
                }
            }

            for (int i = 0; i < 8; i++) {
                for (int k = 0; k <= 8 - N; k++) {
                    int start = k;
                    int end = start + N;

                    String str = "";
                    for (int j = start; j < end; j++) {
                        str += arr[j][i];
                    }

                    sb = new StringBuilder(str);
                    String reverseStr = sb.reverse().toString();

                    if (str.equals(reverseStr)) {
                        answer++;
                    }

                    sb.setLength(0);
                }
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

---

17. Magnetic (1220) - D3

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

class P1220_Magnetic {

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            int[][] arr = new int[N][N];

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

            int answer = 0;
            int now = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {

                    if (arr[j][i] == 1) {
                        now = 1;
                    }

                    if (now == 1 && arr[j][i] == 2) {
                        now = 0;
                        answer++;
                    }
                }
                now = 0;
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

---

18. Sum (1209) - D3

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

class P1209_Sum {

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            int[][] arr = new int[100][100];

            for (int i = 0; i < 100; i++) {
                st = new StringTokenizer(br.readLine());

                for (int j = 0; j < 100; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int answer = 0;

            for (int i = 0; i < 100; i++) {        // 가로
                int sum = 0;

                for (int j = 0; j < 100; j++) {
                    sum += arr[i][j];
                }

                answer = Math.max(answer, sum);
            }

            for (int i = 0; i < 100; i++) {
                int sum = 0;

                for (int j = 0; j < 100; j++) {
                    sum += arr[j][i];
                }

                answer = Math.max(answer, sum);
            }

            int x = 0;
            int y = 0;
            int sum = 0;
            while (x < 100) {
                sum += arr[x][y];
                x++;
                y++;
            }
            answer = Math.max(answer, sum);

            x = 0;
            y = 99;
            sum = 0;
            while (x < 100) {
                sum += arr[x][y];
                x++;
                y--;
            }
            answer = Math.max(answer, sum);

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

---

19. 미로1 (1226) - D4

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

class P1226_미로1 {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    static int N;
    static int[][] arr;
    static boolean[][] visited;
    static int answer;

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            arr = new int[16][16];
            visited = new boolean[16][16];
            answer = 0;

            int a = 0;
            int b = 0;
            for (int i = 0; i < 16; i++) {
                char[] ch = br.readLine().toCharArray();

                for (int j = 0; j < ch.length; j++) {
                    arr[i][j] = ch[j] - '0';
                    if (arr[i][j] == 2) {
                        a = i;
                        b = j;
                    }
                }
            }

            bfs(a, b);
            bw.write("#" + test_case + " " + answer + "\n");
        }

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

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

        while (!queue.isEmpty()) {
            int[] now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int x = now[0] + dx[i];
                int y = now[1] + dy[i];

                if (arr[x][y] == 3) {
                    answer = 1;
                    break;
                }

                if (x >= 0 && y >= 0 && x < 16 && y < 16) {
                    if (!visited[x][y] && arr[x][y] == 0) {
                        visited[x][y] = true;
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
    }
}

---

20. 부분 수열의 합 (2817) - D3

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

class P2817_부분수열의합 {

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = 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;
            ArrayList<Integer> al = new ArrayList<>();
            al.add(0);

            for (int i = 0; i < N; i++) {
                ArrayList<Integer> newAl = new ArrayList<>();

                for (int num : al) {
                    int sum = num + arr[i];
                    if (sum == K) {
                        answer++;
                    }
                    newAl.add(sum);
                }
                al.addAll(newAl);
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

---

21. 혁진이의 프로그램 검증 (1824) - D4

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

class P1824_혁진이의프로그램검증 {
    static char[][] arr;
    static int R;
    static int C;
    static String answer;
    static boolean[][][][] visited;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            R = Integer.parseInt(st.nextToken());
            C = Integer.parseInt(st.nextToken());

            arr = new char[R][C];
            for (int i = 0; i < R; i++) {
                arr[i] = br.readLine().toCharArray();
            }

            visited = new boolean[16][R][C][4];
            answer = "NO";
            dfs(0, 0, 0, 0);

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

    // dir == 0 이면 오른쪽, dir == 1 이면 왼쪽
    // dir == 2 이면 위쪽, dir == 3 이면 아래쪽
    public static void dfs(int value, int x, int y, int dir) {
        if (visited[value][x][y][dir]) {
            return;
        } else {
            visited[value][x][y][dir] = true;
        }
        if (arr[x][y] >= '0' && arr[x][y] <= '9') {
            value = arr[x][y] - '0';
            if (dir == 0) {
                y += 1;
                if (y == C) {
                    y = 0;
                }
            } else if (dir == 1) {
                y -= 1;
                if (y == -1) {
                    y = C - 1;
                }
            } else if (dir == 2) {
                x -= 1;
                if (x == -1) {
                    x = R - 1;
                }
            } else if (dir == 3) {
                x += 1;
                if (x == R) {
                    x = 0;
                }
            }

            dfs(value, x, y, dir);
        } else if (arr[x][y] == '<') {
            y -= 1;
            if (y == -1) {
                y = C - 1;
            }

            dir = 1;
            dfs(value, x, y, dir);
        } else if (arr[x][y] == '>') {
            y += 1;
            if (y == C) {
                y = 0;
            }

            dir = 0;
            dfs(value, x, y, dir);
        } else if (arr[x][y] == '^') {
            x -= 1;
            if (x == -1) {
                x = R - 1;
            }

            dir = 2;
            dfs(value, x, y, dir);
        } else if (arr[x][y] == 'v') {
            x += 1;
            if (x == R) {
                x = 0;
            }

            dir = 3;
            dfs(value, x, y, dir);
        } else if (arr[x][y] == '+') {
            value++;
            if (value == 16) {
                value = 0;
            }

            if (dir == 0) {
                y += 1;
                if (y == C) {
                    y = 0;
                }
            } else if (dir == 1) {
                y -= 1;
                if (y == -1) {
                    y = C - 1;
                }
            } else if (dir == 2) {
                x -= 1;
                if (x == -1) {
                    x = R - 1;
                }
            } else if (dir == 3) {
                x += 1;
                if (x == R) {
                    x = 0;
                }
            }

            dfs(value, x, y, dir);
        } else if (arr[x][y] == '-') {
            value--;
            if (value == -1) {
                value = 15;
            }

            if (dir == 0) {
                y += 1;
                if (y == C) {
                    y = 0;
                }
            } else if (dir == 1) {
                y -= 1;
                if (y == -1) {
                    y = C - 1;
                }
            } else if (dir == 2) {
                x -= 1;
                if (x == -1) {
                    x = R - 1;
                }
            } else if (dir == 3) {
                x += 1;
                if (x == R) {
                    x = 0;
                }
            }

            dfs(value, x, y, dir);
        } else if (arr[x][y] == '@') {
            answer = "YES";
            return;
        } else if (arr[x][y] == '.') {
            if (dir == 0) {
                y += 1;
                if (y == C) {
                    y = 0;
                }
            } else if (dir == 1) {
                y -= 1;
                if (y == -1) {
                    y = C - 1;
                }
            } else if (dir == 2) {
                x -= 1;
                if (x == -1) {
                    x = R - 1;
                }
            } else if (dir == 3) {
                x += 1;
                if (x == R) {
                    x = 0;
                }
            }

            dfs(value, x, y, dir);
        } else if (arr[x][y] == '_') {
            if (value == 0) {
                dir = 0;
            } else {
                dir = 1;
            }

            if (dir == 0) {
                y += 1;
                if (y == C) {
                    y = 0;
                }
            } else if (dir == 1) {
                y -= 1;
                if (y == -1) {
                    y = C - 1;
                }
            } else if (dir == 2) {
                x -= 1;
                if (x == -1) {
                    x = R - 1;
                }
            } else if (dir == 3) {
                x += 1;
                if (x == R) {
                    x = 0;
                }
            }

            dfs(value, x, y, dir);
        } else if (arr[x][y] == '|') {
            if (value == 0) {
                dir = 3;
            } else {
                dir = 2;
            }

            if (dir == 0) {
                y += 1;
                if (y == C) {
                    y = 0;
                }
            } else if (dir == 1) {
                y -= 1;
                if (y == -1) {
                    y = C - 1;
                }
            } else if (dir == 2) {
                x -= 1;
                if (x == -1) {
                    x = R - 1;
                }
            } else if (dir == 3) {
                x += 1;
                if (x == R) {
                    x = 0;
                }
            }

            dfs(value, x, y, dir);
        } else if (arr[x][y] == '?') {
            int a = 0;
            int ay = y + 1;
            if (ay == C) {
                ay = 0;
            }

            int b = 1;
            int by = y - 1;
            if (by == -1) {
                by = C - 1;
            }

            int c = 2;
            int cx = x - 1;
            if (cx == -1) {
                cx = R - 1;
            }

            int d = 3;
            int dx = x + 1;
            if (dx == R) {
                dx = 0;
            }
            if (!visited[value][x][ay][a]) {
                dfs(value, x, ay, a);
            }
            if (!visited[value][x][by][b]) {
                dfs(value, x, by, b);
            }
            if (!visited[value][cx][y][c]) {
                dfs(value, cx, y, c);
            }
            if (!visited[value][dx][y][d]) {
                dfs(value, dx, y, d);
            }
        }
    }
}

---

22. 최장 경로 (2814) - D3

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

class P2814_최장경로 {
    static ArrayList<Integer>[] al;
    static int answer;
    static boolean[] visited;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            visited = new boolean[N + 1];
            al = new ArrayList[N + 1];
            for (int i = 1; i <= N; i++) {
                al[i] = new ArrayList<>();
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                al[x].add(y);
                al[y].add(x);
            }

            answer = 1;
            for (int i = 1; i <= N; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    dfs(i, 1);
                    visited[i] = false;
                }
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

    public static void dfs(int a, int depth) {
        answer = Math.max(answer, depth);

        for (int i : al[a]) {
            if (!visited[i]) {
                visited[a] = true;
                dfs(i, depth + 1);
                visited[a] = false;
            }
        }

    }
}

---

23. 진기의 최고급 붕어빵 (2814) - D3

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

class P1860_진기의최고급붕어빵 {

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());        // 사람수
            int M = Integer.parseInt(st.nextToken());        // 만드는 시간
            int K = Integer.parseInt(st.nextToken());        // 붕어빵 개수

            int[] time = new int[N];        // 손님 도착하는 시간

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

            Arrays.sort(time);

            boolean bl = true;
            int made = 0;            // 만든 붕어빵의 개수
            int cnt = 0;            // 붕어빵 받은 사람 수
            int idxTime = 0;        // time 현재 인덱스
            int lastTime = time[N - 1];

            if (time[0] == 0) {
                bl = false;
            } else {
                for (int i = 1; i <= lastTime; i++) {
                    if (i % M == 0) {
                        made += K;
                    }

                    if (idxTime < N) {
                        if (i == time[idxTime]) {
                            if (made == 0) {
                                bl = false;
                                break;
                            }
                            made--;
                            idxTime++;
                        }
                    } else {
                        bl = false;
                        break;
                    }
                }
            }


            if (bl) {
                bw.write("#" + test_case + " Possible\n");
            } else {
                bw.write("#" + test_case + " Impossible\n");
            }
        }

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

---

24. 암호생성기 (1225) - D3

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

class P1225_암호생성기 {

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            int[] arr = new int[8];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 8; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            int minus = 1;
            boolean bl = true;

            while (true) {
                arr[0] -= minus;
                int temp = arr[0];
                if (temp <= 0) {
                    temp = 0;
                    bl = false;
                }

                for (int i = 1; i < 8; i++) {
                    arr[i - 1] = arr[i];
                }
                arr[7] = temp;

                if (!bl) {
                    break;
                }

                minus++;
                if (minus == 6) {
                    minus = 1;
                }
            }

            bw.write("#" + test_case + " ");
            for (int i = 0; i < 8; i++) {
                bw.write(arr[i] + " ");
            }
            bw.write("\n");
        }

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

---

25. 회문2 (1216) - D3

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

class P1216_회문2 {
    static char[][] arr;

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            int t = Integer.parseInt(br.readLine());
            arr = new char[100][100];

            for (int i = 0; i < 100; i++) {
                arr[i] = br.readLine().toCharArray();
            }

            for (int i = 100; i > 0; i--) {        // 글자수
                if (solve(i)) {
                    bw.write("#" + t + " " + i + "\n");
                    break;
                }
            }
        }

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

    public static boolean solve(int a) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 100; i++) {
            for (int j = 0; j <= 100 - a; j++) {

                String str = "";
                for (int k = j; k < j + a; k++) {        // 가로
                    str += arr[i][k];
                }

                sb.append(str);
                String reverseStr = sb.reverse().toString();

                if (str.equals(reverseStr)) {
                    return true;
                }

                sb.setLength(0);

                str = "";
                for (int k = j; k < j + a; k++) {        // 세로
                    str += arr[k][i];
                }

                sb.append(str);
                reverseStr = sb.reverse().toString();

                if (str.equals(reverseStr)) {
                    return true;
                }

                sb.setLength(0);
            }
        }

        return false;
    }
}

---

26. 파핑파핑 지뢰찾기 (1868) - D4

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

class P1868_파핑파핑지뢰찾기 {
    static char[][] ch;
    static int[][] arr;
    static int N;
    static int answer;
    static boolean[][] visited;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            ch = new char[N][N];
            arr = new int[N][N];
            visited = new boolean[N][N];

            for (int i = 0; i < N; i++) {
                ch[i] = br.readLine().toCharArray();
            }

            numberCheck();

            answer = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && arr[i][j] == 0) {
                        answer++;
                        answerCheck(i, j);
                    }
                }
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j] && arr[i][j] != -1) {
                        answer++;
                    }
                }
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

    public static void answerCheck(int a, int b) {
        visited[a][b] = true;

        if (a - 1 >= 0 && b - 1 >= 0 && !visited[a - 1][b - 1]) {
            if (arr[a - 1][b - 1] != 0) {
                visited[a - 1][b - 1] = true;
            } else {
                answerCheck(a - 1, b - 1);
            }
        }

        if (b - 1 >= 0 && !visited[a][b - 1]) {
            if (arr[a][b - 1] != 0) {
                visited[a][b - 1] = true;
            } else {
                answerCheck(a, b - 1);
            }
        }

        if (a + 1 < N && b - 1 >= 0 && !visited[a + 1][b - 1]) {
            if (arr[a + 1][b - 1] != 0) {
                visited[a + 1][b - 1] = true;
            } else {
                answerCheck(a + 1, b - 1);
            }
        }

        if (a + 1 < N && !visited[a + 1][b]) {
            if (arr[a + 1][b] != 0) {
                visited[a + 1][b] = true;
            } else {
                answerCheck(a + 1, b);
            }
        }

        if (a + 1 < N && b + 1 < N && !visited[a + 1][b + 1]) {
            if (arr[a + 1][b + 1] != 0) {
                visited[a + 1][b + 1] = true;
            } else {
                answerCheck(a + 1, b + 1);
            }
        }

        if (b + 1 < N && !visited[a][b + 1]) {
            if (arr[a][b + 1] != 0) {
                visited[a][b + 1] = true;
            } else {
                answerCheck(a, b + 1);
            }
        }

        if (a - 1 >= 0 && b + 1 < N && !visited[a - 1][b + 1]) {
            if (arr[a - 1][b + 1] != 0) {
                visited[a - 1][b + 1] = true;
            } else {
                answerCheck(a - 1, b + 1);
            }
        }

        if (a - 1 >= 0 && !visited[a - 1][b]) {
            if (arr[a - 1][b] != 0) {
                visited[a - 1][b] = true;
            } else {
                answerCheck(a - 1, b);
            }
        }
    }

    public static void numberCheck() {        // arr 초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (ch[i][j] == '*') {
                    arr[i][j] = -1;
                } else {
                    if (i - 1 >= 0 && j - 1 >= 0) {
                        if (ch[i - 1][j - 1] == '*') arr[i][j]++;
                    }

                    if (j - 1 >= 0) {
                        if (ch[i][j - 1] == '*') arr[i][j]++;
                    }

                    if (i + 1 < N && j - 1 >= 0) {
                        if (ch[i + 1][j - 1] == '*') arr[i][j]++;
                    }

                    if (i + 1 < N) {
                        if (ch[i + 1][j] == '*') arr[i][j]++;
                    }

                    if (i + 1 < N && j + 1 < N) {
                        if (ch[i + 1][j + 1] == '*') arr[i][j]++;
                    }

                    if (j + 1 < N) {
                        if (ch[i][j + 1] == '*') arr[i][j]++;
                    }

                    if (i - 1 >= 0 && j + 1 < N) {
                        if (ch[i - 1][j + 1] == '*') arr[i][j]++;
                    }

                    if (i - 1 >= 0) {
                        if (ch[i - 1][j] == '*') arr[i][j]++;
                    }
                }
            }
        }
    }
}

---

27. Contact (1238) - D4

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

class P1238_Contact {
    static ArrayList<Integer>[] al;
    static int answer;
    static int maxDepth;
    static boolean[] visited;

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int size = Integer.parseInt(st.nextToken());
            int startNumber = Integer.parseInt(st.nextToken());

            visited = new boolean[101];
            al = new ArrayList[101];
            for (int i = 1; i <= 100; i++) {
                al[i] = new ArrayList<Integer>();
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < size / 2; i++) {
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                al[a].add(b);
            }

            answer = -1;
            maxDepth = 0;
            bfs(startNumber, 0);

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

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

        while (!queue.isEmpty()) {
            int[] a = queue.poll();
            int value = a[0];
            int nowDepth = a[1];

            if (maxDepth < nowDepth) {
                maxDepth = nowDepth;
                answer = value;
            } else if (maxDepth == nowDepth) {
                answer = Math.max(answer, value);
            }

            for (int i : al[value]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(new int[]{i, nowDepth + 1});
                }
            }
        }
    }
}

---

28. 정사각형 방 (1861) - D4

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

class P1861_정사각형방 {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};
    static boolean[][] visited;
    static int[][] arr;
    static int N;
    static int maxDepth;
    static int answer;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            arr = 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++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            answer = Integer.MAX_VALUE;
            maxDepth = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    bfs(i, j, 1);
                }
            }

            bw.write("#" + test_case + " " + answer + " " + maxDepth + "\n");
        }

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

    public static void bfs(int xx, int yy, int depth) {
        visited[xx][yy] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{xx, yy, depth});

        while (!queue.isEmpty()) {

            int[] now = queue.poll();
            int a = now[0];
            int b = now[1];
            int nowDepth = now[2];

            if (maxDepth < nowDepth) {
                maxDepth = nowDepth;
                answer = arr[xx][yy];
            } else if (maxDepth == nowDepth) {
                answer = Math.min(answer, arr[xx][yy]);
            }

            for (int i = 0; i < 4; i++) {
                int x = a + dx[i];
                int y = b + dy[i];

                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (!visited[x][y]) {
                        if (arr[x][y] - arr[a][b] == 1) {
                            visited[x][y] = true;
                            queue.add(new int[]{x, y, nowDepth + 1});
                        }
                    }
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visited[i][j] = false;
            }
        }
    }
}

---

29. 재미있는 오셀로 게임 (4615) - D3

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

class P4615_재미있는오셀로게임 {
    static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1};
    static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
    static int N;
    static int[][] arr;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            arr = new int[N + 1][N + 1];

            int mid = N / 2;
            arr[mid][mid] = 2;
            arr[mid + 1][mid + 1] = 2;
            arr[mid][mid + 1] = 1;
            arr[mid + 1][mid] = 1;

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int b = Integer.parseInt(st.nextToken());
                int a = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());

                arr[a][b] = c;
                change(a, b, c);
            }

            int bCount = 0;
            int wCount = 0;
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][j] == 1) {
                        bCount++;
                    } else {
                        wCount++;
                    }
                }
            }

            bw.write("#" + test_case + " " + bCount + " " + wCount + "\n");
        }

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

    public static void change(int a, int b, int col) {
        for (int i = 0; i < 8; i++) {
            boolean bl = true;

            int x = a + dx[i];
            int y = b + dy[i];

            if (x >= 1 && y >= 1 && x <= N && y <= N) {
                while (arr[x][y] != col && arr[x][y] != 0) {
                    x += dx[i];
                    y += dy[i];

                    if (x <= 0 || y <= 0 || x > N || y > N) {
                        bl = false;
                        break;
                    }
                }

                if (bl) {
                    if (i == 0) {
                        for (int k = y + 1; k < b; k++) {
                            arr[a][k] = col;
                        }
                    } else if (i == 1) {
                        int t = y + 1;
                        for (int k = x + 1; k < a; k++) {
                            arr[k][t] = col;
                            t++;
                        }
                    } else if (i == 2) {
                        for (int k = x + 1; k < a; k++) {
                            arr[k][b] = col;
                        }
                    } else if (i == 3) {
                        int t = y - 1;
                        for (int k = x + 1; k < a; k++) {
                            arr[k][t] = col;
                            t--;
                        }
                    } else if (i == 4) {
                        for (int k = y - 1; k > b; k--) {
                            arr[a][k] = col;
                        }
                    } else if (i == 5) {
                        int t = y - 1;
                        for (int k = x - 1; k > a; k--) {
                            arr[k][t] = col;
                            t--;
                        }
                    } else if (i == 6) {
                        for (int k = x - 1; k > a; k--) {
                            arr[k][b] = col;
                        }
                    } else if (i == 7) {
                        int t = y + 1;
                        for (int k = x - 1; k > a; k--) {
                            arr[k][t] = col;
                            t++;
                        }
                    }
                }
            }
        }
    }
}

---

30. 자기방으로 돌아가기 (4408) - D4

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

class P4408_자기방으로돌아가기 {

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            int[][] arr = new int[N][2];
            int[] path = new int[201];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                arr[i][0] = Integer.parseInt(st.nextToken());
                arr[i][1] = Integer.parseInt(st.nextToken());

                if (arr[i][0] > arr[i][1]) {
                    int temp = arr[i][0];
                    arr[i][0] = arr[i][1];
                    arr[i][1] = temp;
                }

                int s = -1;
                int e = -1;

                if (arr[i][0] % 2 == 1) {
                    s = arr[i][0] / 2 + 1;
                } else {
                    s = arr[i][0] / 2;
                }

                if (arr[i][1] % 2 == 1) {
                    e = arr[i][1] / 2 + 1;
                } else {
                    e = arr[i][1] / 2;
                }

                for (int j = s; j <= e; j++) {
                    path[j]++;
                }
            }

            Arrays.sort(path);


            bw.write("#" + test_case + " " + path[200] + "\n");
        }

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

---

31. 길찾기 (1219) - D4

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

class P1219_길찾기 {
    static ArrayList<Integer>[] al;
    static boolean[] visited;
    static boolean bl;

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int seq = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());

            bl = false;
            visited = new boolean[100];
            al = new ArrayList[100];
            for (int i = 0; i < 100; i++) {
                al[i] = new ArrayList<>();
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                al[a].add(b);
            }

            bfs(0);

            if (bl) {
                bw.write("#" + test_case + " 1\n");
            } else {
                bw.write("#" + test_case + " 0\n");
            }
        }

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

    public static void bfs(int start) {
        visited[start] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int a = queue.poll();
            if (a == 99) {
                bl = true;
                return;
            }

            for (int i : al[a]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

---

32. 장훈이의 높은 선반 (1486) - D4

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

class P1486_장훈이의높은선반 {

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int B = 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());
            }

            HashSet<Integer> set = new HashSet<>();
            set.add(0);

            for (int i = 0; i < N; i++) {
                HashSet<Integer> newSet = new HashSet<>();
                for (int j : set) {
                    newSet.add(j + arr[i]);
                }
                set.addAll(newSet);
            }

            int min = Integer.MAX_VALUE;
            for (int i : set) {
                if (i >= B) {
                    int gap = i - B;
                    min = Math.min(min, gap);
                }
            }

            bw.write("#" + test_case + " " + min + "\n");
        }

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

---

33. 준환이의 양팔저울 (3234) - D4

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

class P3234_준환이의양팔저울 {
    static int[] arr;
    static int answer;
    static int N;
    static boolean[] visited;
    static int index;
    static int[] sorted;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            arr = new int[N];
            visited = new boolean[N];
            index = 0;
            sorted = new int[N];

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

            answer = 0;
            check(0);

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

    public static void check(int depth) {
        if (depth == N) {
            dfs(0, 0, 0);
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                sorted[depth] = arr[i];
                check(depth + 1);
                visited[i] = false;
            }
        }
    }

    public static void dfs(int leftSum, int rightSum, int depth) {
        if (depth == N) {
            if (leftSum >= rightSum) {
                answer++;
                return;
            }
        }

        if (leftSum < rightSum) {
            return;
        }

        dfs(leftSum + sorted[depth], rightSum, depth + 1);
        dfs(leftSum, rightSum + sorted[depth], depth + 1);

    }
}

---

34. 수의 새로운 연산 (1493) - D3

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

class P1493_수의새로운연산 {
    static int x;
    static int y;

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

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

        for (int test_case = 1; test_case <= T; test_case++) {
            st = new StringTokenizer(br.readLine());
            int p = Integer.parseInt(st.nextToken());
            int q = Integer.parseInt(st.nextToken());

            x = 0;
            y = 0;
            search(p, q);

            int now = 1;
            int plus = 1;

            int c = x + y - 1;
            while (c > 0) {
                c--;
                now += plus;
                plus++;
            }


            now += c - y;
            bw.write("#" + test_case + " " + now + "\n");
        }

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

    public static void search(int a, int b) {
        int sum = 0;
        int index = 0;
        for (int i = 1; i < 10000; i++) {
            sum += i;
            if (sum >= a) {
                index = i;
                break;
            }
        }

        int ax = 1;
        int ay = index;
        int gap = sum - a;
        while (gap > 0) {
            gap--;
            ax++;
            ay--;
        }

        sum = 0;
        index = 0;
        for (int i = 1; i < 10000; i++) {
            sum += i;
            if (sum >= b) {
                index = i;
                break;
            }
        }

        int bx = 1;
        int by = index;
        gap = sum - b;
        while (gap > 0) {
            gap--;
            bx++;
            by--;
        }

        y = ax + bx;
        x = ay + by;
    }
}

---

35. String (1213) - D3

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

class P1213_String {

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

        int T = 1;

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            char[] ch = br.readLine().toCharArray();
            char[] arr = br.readLine().toCharArray();
            int answer = 0;

            for (int i = 0; i <= arr.length - ch.length; i++) {
                if (arr[i] == ch[0]) {
                    int index = 0;
                    for (int j = i; j < i + ch.length; j++) {
                        if (arr[j] == ch[index]) {
                            index++;
                            if (index == ch.length) {
                                answer++;
                                break;
                            }
                        } else {
                            break;
                        }
                    }
                }
            }

            bw.write("#" + test_case + " " + answer + "\n");
        }

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

---