<stdio.han>

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

[정답 코드]

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

public class Main {
    static int R, C, answer = 0;
    static char[][] graph;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static HashSet<Character> alphabet;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        graph = new char[R][C];

        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++) {
                graph[i][j] = input.charAt(j);
            }
        }
        alphabet = new HashSet<>(); // HashSet 초기화
        back(0, 0, 1); //
        System.out.println(answer);
    }
    static void back(int x, int y, int count) {
        answer = Math.max(answer, count);
        alphabet.add(graph[x][y]);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                if (!alphabet.contains(graph[nx][ny])) { // 처음 방문한 알파벳일 경우
                    back(nx, ny, count + 1);
                }
            }
        }
        alphabet.remove(graph[x][y]); // 이전 상태로 돌아가기 위해 제거
    }
}

[설명]

백트래킹 문제이다.

일반적인 백트래킹 알고리즘과 다른점은 단순 방문했던 자리를 체크하는게 아니라 똑같은 알파벳이 아닌자리를 체크해줘야한다. 그 부분은 HashSet을 이용해 체크해주었다. 그리고 alphabet.remove()를 활용해 지나온 알파벳을 지우며 이전상태로 돌아간다.

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

[정답 코드]

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

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

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

        int[] arr = new int[N+1];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = 0;

        while (left <= N && right <= N) {
            if (sum >= S) {
                answer = Math.min(answer, right - left);
                sum -= arr[left++];
            } else if (sum < S) {
                sum += arr[right++];
            }
        }
        System.out.println(answer==Integer.MAX_VALUE ? 0 : answer);
    }
}

[설명]

투포인터 알고리즘을 활용한다.

sum 이 S보다 작을 경우 sum += arr[right++]를 하고

sum이 S보다 크거나 같을 경우 sum -= arr[left--]를 해준다. 그리고 동시에 right - left를 해주어 더 작은값을 출력해준다.

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

[정답 코드]

import org.w3c.dom.html.HTMLParagraphElement;

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = 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());
        }
        Arrays.sort(arr);
        int answer = 0;

        for (int i = 0; i < N; i++) {
            int left = 0;
            int right = N - 1;
            int target = arr[i];
            while (left < right) {
                int sum = arr[left] + arr[right];
                if (sum == target) { // sum이 target과 같을 경우
                    if (left != i && right != i) { // left와 right가 같은 수가 아닐경우
                        answer++;
                        break;
                    } else if (left == i) { // 현재 탐색하려는 숫자를 사용하면 안됨
                        left++;
                    } else { // 현재 탐색하려는 숫자를 사용하면 안됨
                        right--;
                    }
                } else if (sum < target) { //sum이 target보다 작을 경우
                    left++;
                } else { // sum이 target보다 클 경우
                    right--;
                }
            }
        }
        System.out.println(answer);
    }
}

[설명]

투 포인터로 풀었다. 배열을 입력받은 후 arr[left] 와 arr[right]를 더한값을 target 과 비교해가며 left를 늘리고 right를 줄이며 탐색한다.

                    if (left != i && right != i) { // left와 right가 같은 수가 아닐경우
                        answer++;
                        break;
                    } else if (left == i) { // 현재 탐색하려는 숫자를 사용하면 안됨
                        left++;
                    } else { // 현재 탐색하려는 숫자를 사용하면 안됨
                        right--;
                    }

 여기서 else if 구문과 else 구문이 이해가 너무안가서 1시간 넘게 이해를 못하고있었다. 

예를 들어 현재 3번 인덱스를 target으로 두고 탐색하고있을 때, 3번인덱스 + X인덱스를 더한값을 찾으려고 했을 경우라는 의미이다. 3번인덱스를 찾으려는데 3번인덱스를 더해서 찾는건 말이 안되기 때문이다.

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

[정답 코드]

import org.w3c.dom.html.HTMLParagraphElement;

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

public class Main {
    static int[][] graph;
    static int[] dx = {-1, 1, 0, 0}; // 상하좌우 탐색
    static int[] dy = {0, 0, -1, 1};
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int count = 0;

        while (true) {
            count++;
            st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken());
            if (N == 0) {
                break;
            }
            graph = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            System.out.println("Problem " + count + ": " + dijkstra());
        }
        br.close();
    }

    static int dijkstra() {
        // 우선 순위 큐에는 int[] = {x좌표, y좌표, 가중치} 가 담긴다
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);


        int[][] distance = new int[N][N]; // 가중치 배열
        for (int i = 0; i < N; i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE); // 모든 가중치 INF로 설정
        }
        queue.offer(new int[]{0, 0, graph[0][0]}); // 좌표 (0, 0) 큐에 추가
        distance[0][0] = graph[0][0];

        while (!queue.isEmpty()) {
            int tmp[] = queue.poll();
            int x = tmp[0];
            int y = tmp[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                    if (distance[nx][ny] > distance[x][y] + graph[nx][ny]) { // 현재 가중치가 새로 찾은 가중치보다 클 경우
                        distance[nx][ny] = distance[x][y] + graph[nx][ny]; // 갱신
                        queue.offer(new int[]{nx, ny, distance[nx][ny]}); // 갱신이 되었다면 큐에 추가
                    }
                }
            }
        }
        return distance[N - 1][N - 1]; // 도착 지점 좌표의 가중치 반환
    }
}

[설명]

가중치가 모두 같을 경우에는 BFS를 사용, 다를 경우에는 다익스트라를 사용한다.

BFS는 일반 큐를 사용, 다익스트라는 우선 순위 큐를 사용.

좌표(0, 0) 부터 시작해 (N-1, N-1) 까지 갔을 경우 도착좌표의 가중치최소값을 출력한다.

가변인수(varargs) : 자바에서 메서드에 임의의 개수의 인수를 전달할 수 있도록 하는 기능. 이를 통해 메서드를 호출할 때 원하는 개수의 인수를 전달할 수 있다. 가변인수는 배열로 처리되며, 메서드 선언 시에 타입 뒤에 세 개의 점(...)을 사용하여 정의한다.

제네릭 : 자바 프로그래밍 언어의 한 기능으로, 타입 매개변수를 사용하여 클래스, 인터페이스, 메서드를 정의하는 방법. 이를 통해 컬렉션 클래스나 제네릭 메서드 등을 작성할 때 특정 타입에 의존하지 않고 일반화된 형태로 구현할 수 있다.

@SafeVarargs : 자바의 애너테이션 중 하나로, 가변인수(varargs) 매개변수를 사용하는 메서드에 붙인다. 이 애너테이션은 컴파일러에게 해당 메서드가 안전하게 사용될 수 있다는 것을 알려준다.

제네릭과 가변인수를 함께 사용할 때 주의점 : 

1. 가변인수의 타입이 제네릭일 경우에는 @SafeVarargs 애너테이션을 사용해야 한다.
2. 제네릭 배열을 생성하는 것은 안전하지 않으므로, 컴파일러 경고가 발생할 수 있다.
3. 가변인수의 타입이 제네릭이거나, 가변인수를 포함하는 제네릭 메서드를 오버로드할 경우 혼동을 줄 수 있다.

import java.util.Arrays;
import java.util.List;

public class GenericVarargsExample {

    // 주의사항 1: 가변인수의 타입이 제네릭일 경우에는 @SafeVarargs 애너테이션을 사용해야 함
    @SafeVarargs
    public static <T> List<T> createList(T... elements) {
        return Arrays.asList(elements);
    }

    // 주의사항 2: 제네릭 배열 생성은 안전하지 않음
    public static <T> T[] createArray(T... elements) {
        // 컴파일러 경고 발생 가능
        return elements;
    }

    // 주의사항 3: 제네릭과 가변인수를 함께 사용한 오버로딩은 혼동을 줄 수 있음
    public static void processElements(String... elements) {
        System.out.println("Processing Strings...");
        for (String element : elements) {
            System.out.println(element);
        }
    }

    public static void processElements(Integer... elements) {
        System.out.println("Processing Integers...");
        for (Integer element : elements) {
            System.out.println(element);
        }
    }

    public static void main(String[] args) {
        // 예시 1: @SafeVarargs 애너테이션 사용한 제네릭 가변인수 메서드 호출
        List<Integer> intList = createList(1, 2, 3, 4, 5);
        System.out.println("Integer List: " + intList);

        // 예시 2: 제네릭 배열 생성
        String[] stringArray = createArray("Hello", "World");
        System.out.println("String Array: " + Arrays.toString(stringArray));

        // 예시 3: 제네릭과 가변인수를 함께 사용한 오버로딩
        processElements("One", "Two", "Three"); // 어떤 메서드가 호출될까?
        processElements(1, 2, 3); // 어떤 메서드가 호출될까?
    }
}

1. createList 메서드에서는 @SafeVarargs 애너테이션을 사용하여 제네릭 가변인수를 안전하게 처리한다.
2. createArray 메서드에서는 제네릭 배열 생성으로 인한 컴파일러 경고를 확인할 수 있다.
3. processElements 메서드에서는 제네릭과 가변인수를 함께 사용한 오버로딩이 혼동을 줄 수 있음을 보여준다. 호출할 때 어떤 메서드가 호출될지 주의해야 한다.

결론 : 가변인수와 제네릭은 궁합이 좋지 않다. 가변인수 기능은 배열을 노출하여 추상화가 완벽하지 못하고, 배열과 제네릭의 타입 규칙이 서로 다르기 때문이다. 제네릭 varargs 매개변수는 타입 안전하지는 않지만, 허용된다. 메서드에 제네릭 (혹은 매개변수화된)varargs 매개변수를 사용하고자 한다면, 먼저 그 메서드가 타입 안전한지 확인한 다음 @SafeVarargs 애너테이션을 달아 사용하는 데 불편함이 없게끔 하자.