<stdio.han>

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

[정답 코드]

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

public class Main {
    static int R, C, answer = Integer.MAX_VALUE;
    static char[][] graph;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static Queue<int[]> jihoon = new LinkedList<>(); // 지훈이의 좌표가 담긴 큐
    static Queue<int[]> fire = new LinkedList<>(); // 불의 좌표가 담긴 큐
    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);
                if (graph[i][j] == 'J') {
                    jihoon.offer(new int[]{i, j});
                }
                if (graph[i][j] == 'F') {
                    fire.offer(new int[]{i, j});
                }
            }
        }
        br.close();

        int answer = 0;
        while (true) {
            answer++; // while 반복문을 1회 시행할 때 마다 1분이 지난것이므로 1씩 증가
            int fireSize = fire.size(); // 불의 좌표가 담긴 큐의 크기 == 불의 갯수
            while (fireSize > 0) { // 번져야 할 불의 개수만큼만 반복, 이미 번진 불은 번지는것을 반복하지 않음
                fireSize--;
                int[] tmp = fire.poll();
                int x = tmp[0];
                int y = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                        if (graph[nx][ny] == '.' || graph[nx][ny] == 'J') { // 불이 번진 위치가 벽이 아니라면
                            fire.offer(new int[]{nx, ny}); // 새로운 불의 좌표를 큐에 담는다
                            graph[nx][ny] = 'F'; // 번진만큼 지도를 갱신
                        }
                    }
                }
            }

            int jihoonSize = jihoon.size();
            while (jihoonSize > 0) { // 지훈이의 좌표가 담긴 큐가 비어있지 않을 경우
                jihoonSize--; // 새로운 지훈이의 좌표갯수만큼만 반복, 이미 이동한 지훈이는 이동하는것을 또 반복하지 않음
                int[] tmp = jihoon.poll();
                int x = tmp[0];
                int y = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int nx = x + dx[i];
                    int ny = y + dy[i];
                    if (nx < 0 || nx >= R || ny < 0 || ny >= C) { // 탈출을 했을 경우
                        System.out.println(answer);
                        return;
                    }
                    if (graph[nx][ny] == '.') { // 이동가능한 자리일 경우
                        jihoon.offer(new int[]{nx, ny}); // 이동한 위치의 좌표를 큐에 담는다
                        graph[nx][ny] = 'J'; // 이동한 위치를 J로 갱신 (사실 이 코드는 필요하지는 않음)
                    }
                }
            }
            if (jihoon.isEmpty()) { // 새로이동할 때마다 지훈이의 좌표가 담긴 큐 jihoon 이 늘어나는데, 이동이 불가능하면 큐가 비게 됨
                System.out.println("IMPOSSIBLE");
                return;
            }
        }
    }
}

[설명]

bfs심화문제이다. 지훈이가 4방탐색을 하며 지도밖을 나갈 경우 반복문이 종료되는 것까지를 구현하는것은 약간만 생각하면 할 수 있다. 하지만 다른문제와 다른것은 지훈이가 4방탐색을함과 동시에 불도 4방으로 퍼져나간다는것을 생각해야 한다. 나는 이부분에서 막혀서 다른글을 참고했다. 

대략적인 풀이방식은 이렇다 : 

1. 불과 지훈이의 좌표를 각 큐에 담는다.

2. 불이 먼저 퍼져나가며 퍼져나간 불의 위치를 큐에 담는다.

3. 지훈이가 4방탐색을 하며 지훈이가 갈 수 있는 모든위치의 좌표를 큐에 담는다.

4. 이미 퍼져나간 불은 한 번더 퍼져나갈필요가없다. 새롭게 퍼져나간 불만 다시 퍼져나간다. (애초에 이미 퍼져나간불은 큐에 좌표가 없다.)

5. 3에서 4방탐색을 하며 지훈이가 갈 수 있는 모든 위치에서 다시 4방탐색을 하며 탈출구를 찾는다.

6. 4, 5를 반복한다.

7 - 1. 지훈이의 좌표가 지도 밖을 나갈경우 정답을 출력해준다.

7 - 2. 지훈이가 더이상 새롭게 이동할수 있는 위치가 없을 경우 jihoon 큐에는 더이상 값이 안담겨있기 때문에 IMPOSSIBLE을 출력해준다.

디버깅모드를 하고 지도의 모습을 시뮬레이션한것을 보면 약간은 신기하다. 여기서 중요한점은 불이 지훈이의 위치가 담긴 자리까지 불이 번져나가며 덮어버리는 경우가 있는데. 단순히 지도에서만 그렇고 지훈이의 좌표는 jihoon 큐 안에 담겨있기 때문에 문제없다.

열거 타입(Enumeration Type) : 서로 관련된 상수들의 집합을 정의할 때 사용되는 특별한 종류의 클래스. 일정 개수의 상수 값을 정의한 다음, 그 외의 값은 허용하지 않는 타입.

정수 열거 패턴의 예시 코드 - 취약하다!!

// 정수 열거 패턴 - 안티 패턴
public class Weekdays {
    public static final int MONDAY = 1;
    public static final int TUESDAY = 2;
    public static final int WEDNESDAY = 3;
    // 나머지 요일들도 동일하게 정의

    // 주어진 요일을 출력하는 메서드
    public static String getDay(int day) {
        switch (day) {
            case MONDAY: return "Monday";
            case TUESDAY: return "Tuesday";
            case WEDNESDAY: return "Wednesday";
            // 나머지 요일들에 대한 처리
            default: return "Invalid day";
        }
    }
}

열거 타입의 예시 : 

// 열거 타입
public enum Day {
    MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY;

    // 주어진 요일을 출력하는 메서드
    public static String getDay(Day day) {
        switch (day) {
            case MONDAY: return "Monday";
            case TUESDAY: return "Tuesday";
            case WEDNESDAY: return "Wednesday";
            // 나머지 요일들에 대한 처리
            default: return "Invalid day";
        }
    }
}

Day day = Day.MONDAY;
System.out.println(Day.getDay(day)); // 출력: Monday

전략 열거 타입 패턴 : 각 열거 상수가 서로 다른 동작을 나타내는 열거 타입. 이러한 방식으로 각 상수가 자신만의 동작을 가지며, 열거 타입을 통해 각 동작을 선택할 수 있다.

전략 열거 타입 패턴의 예시 코드 : 

// 열거 타입
enum PayrollDay {

	// 주중은 WEEKDAY로 표시되며, 주말은 WEEKEND로 표시된다.
    MONDAY(PayType.WEEKDAY), TUESDAY(PayType.WEEKDAY), WEDNESDAY(PayType.WEEKDAY),
    THURSDAY(PayType.WEEKDAY), FRIDAY(PayType.WEEKDAY), SATURDAY(PayType.WEEKEND),
    SUNDAY(PayType.WEEKEND);
	
    // PayType 열거 상수를 저장하는 private final 필드
    private final PayType payType;

	// PayrollDay의 생성자는 PayType을 받아들여 해당 요일의 지불 방식을 설정한다.
    PayrollDay(PayType payType) {
        this.payType = payType;
    }

    double pay(double hoursWorked, double payRate) {
        return payType.pay(hoursWorked, payRate);
    }

    // 전략 열거 타입 패턴
    enum PayType {
        WEEKDAY {
          double overtimePay(double hours, double payRate) {
              return hours <= HOURS_PER_SHIFT ? 0 : (hours - HOURS_PER_SHIFT) * payRate / 2;
          }
        },
        WEEKEND {
            double overtimePay(double hours, double payRate) {
                return hours * payRate / 2;
            }
        };

        private static final int HOURS_PER_SHIFT = 8;

        abstract double overtimePay(double hrs, double payRate);

        double pay(double hoursWorked, double payRate) {
            double basePay = hoursWorked * payRate;
            return basePay + overtimePay(hoursWorked, payRate);
        }
    }
}

핵심 정리 : 열거 타입은 확실히 정수 상수보다 뛰어나다. 더 읽기 쉽고 안전하고 강력하다. 대다수 열거 타입이 명시적 생성자나 메서드 없이 쓰이지만, 각 상수를 특정 데이터와 연결짓거나 상수마다 다르게 동작하게 할 때는 필요하다. 드물게는 하나의 메서드가 상수별로 다르게 동작해야 할 때도 있다. 이런 열거 타입에서는 switch 문 대신 상수별 메서드 구현을 사용하자. 열거 타입 상수 일부가 같은 동작을 공유한다면 전략 열거 타입 패턴을 사용하자.

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

[정답 코드]

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 C = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int result = 0;
        int left = 0;
        int right = arr[N - 1] - arr[0]; // 최대 간격

        while (left <= right) {
            int cnt = 1;
            int cur = arr[0]; // 첫 번째 집부터 시작

            int mid = (right + left) / 2; //공유기 설치의 최소 간격

            for (int i = 1; i < N; i++) { // 첫 번째집은설치했으니 두번째집부터 시작
                if (arr[i] - cur >= mid) {
                    cnt++;
                    cur = arr[i]; // 현재 바라보는 인덱스(커서)를 설치한 집으로 이동
                }
            }

            if (cnt >= C) { // 공유기간의 거리를 적당히 설정해서 최소 C개만큼 설치했을 경우
                result = mid;

                // 좀더 좋은 결과값을 찾기위해 간격을 넓혀본다
                left = mid + 1;
            } else {
                // 결과값을 찾기위해 간격을 좁힌다
                right = mid - 1;
            }
        }
        System.out.println(result);
    }
}

[설명]

공유기를 설치한 집과 다음 설치할 집과의 간격이 mid 이상일 경우에만 cnt를 1씩 증가시킨다. for문이 끝난 후 cnt 의 값이 C이상일 경우 좀더 최적의 해를 찾기위해 간격을 넓혀서 재탐색해본다. 우리는 최댓값을 찾는것이기 때문이다. cnt의 값이 C보다 적을 경우 간격을 좁혀 해를 재탐색한다.

타입 안전 이종 컨테이너(Type-safe heterogeneous container) : 다양한 타입의 요소를 안전하게 저장하고 검색할 수 있는 컨테이너. 이를 통해 다양한 타입의 데이터를 일관된 방식으로 처리할 수 있다. 이러한 컨테이너를 고려함으로써 프로그램의 유연성과 안정성을 향상시킬 수 있다.

import java.util.HashMap;
import java.util.Map;

// 데이터베이스의 행을 표현하는 클래스
public class DatabaseRow {
    // 열(Column)과 해당 열의 값을 저장하는 맵
    // 타입 안전 이종컨테이너
    private final Map<Column<?>, Object> columns = new HashMap<>();

    // 열과 해당하는 값을 추가하는 메서드
    public <T> void addColumn(Column<T> column, T value) {
        columns.put(column, value);
    }

    // 열에 해당하는 값을 반환하는 메서드
    public <T> T getValue(Column<T> column) {
        // 맵에서 열에 해당하는 값을 가져와 형변환하여 반환
        return column.getType().cast(columns.get(column));
    }
}

// 열(Column)을 나타내는 클래스
class Column<T> {
    // 열의 값의 타입을 나타내는 클래스
    private final Class<T> type;

    // 열의 값의 타입을 받아 초기화하는 생성자
    public Column(Class<T> type) {
        this.type = type;
    }

    // 열의 값의 타입을 반환하는 메서드
    public Class<T> getType() {
        return type;
    }
}

결론 : 컬렉션 API로 대표되는 일반적인 제네릭 형태에서는 한 컨테이너가 다룰 수 있는 타입 매개변수의 수가 고정되어 있다. 하지만 컨테이너 자체가 아닌 키를 타입 매개변수로 바꾸면 이런 제약이 없는 타입 안전 이종 컨테이너를 만들 수 있다. 타입 안전 이종 컨테이너는 Class를 키로 쓰며, 이런 식으로 쓰인 Class 객체를 타입 토큰이라 한다. 또한, 직접 구현한 키 타입도 쓸 수 있다. 예컨대 데이터베이스의 행(컨테이너)을 표현한 DateabaseRow 타입에는 제네릭 타입인 Column<T>를 키로 사용할 수 있다.

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) 까지 갔을 경우 도착좌표의 가중치최소값을 출력한다.