SWEA_3124_최소 스패닝 트리

요약

MST 구현 문제 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리만들기!

접근

이 문제는 문제 설명에서도 알 수 있듯 MST를 활용해 답을 찾는 문제다. MST를 구할 땐, Kruskal과 Prim 총 2가지 방식이 있다. Kruskal이 좀 더 직관적으로 이해하기 쉬워서 이 풀이는 Kruskal을 이용해 풀었다.

알고리즘 - Kruskal

1. make-set : 집합의 초기화
2. union : 집합끼리 합치기
3. find : 집합의 root 찾기

위의 내용이 기본적인 Union-Find 알고리즘이다. Kruskal은 이를 활용해서 구한다.

• Kruskal의 핵심은 가중치가 낮은 간선부터 처리하는 것이다!
• 또한, 사이클이 존재하는지 체크하며 넘어가야한다.

이를 위해서 헷갈리지 않기 위해 make-set 전에 오름차순 정렬을 하고, 사이클 존재여부는 union을 하기 전에 find로 각각의 집합 root를 찾아서 비교를 통해 다를 경우에만 union을 하도록 처리하면 된다!

제출 코드

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

public class Main
{
    static int[] parent;
    static int cnt, V, E;
    static long res; // 스패닝 트리의 최댓값이 199_999 * 1_000_000이라 20억을 넘는다!
    static int[] groupSize;

    static class Edge implements Comparable<Edge> {
        int start;
        int end;
        int weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override // 정렬 기준
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        // T 개수 받음
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            V = Integer.parseInt(st.nextToken());
            E = Integer.parseInt(st.nextToken());

            Edge[] edges = new Edge[E]; // 간선 입력 저장할 배열

            for (int i = 0; i < E; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int start = Integer.parseInt(st.nextToken());
                int end = Integer.parseInt(st.nextToken());
                int weight = Integer.parseInt(st.nextToken());

                edges[i] = new Edge(start, end, weight);
            }

            Arrays.sort(edges); // 가중치가 가장 낮은 간선들을 순서로

            parent = new int[V+1]; // 그룹 번호 저장
            groupSize = new int[V+1]; // 그룹 사이즈 저장
            res = 0;
            cnt = 0;

            makeSet();

            for (Edge edge : edges) {

                boolean isUnion = union(edge.start, edge.end);

                if (isUnion) {
                    cnt++; // 모든 정점을 연결했는지 확인하기 위해
                    res += edge.weight;
                }
                if (cnt == V-1) break; // 모든 정점을 연결했다면, 연결된 간선의 수는 정점의 수-1 이기 때문!
            }

            sb.append("#").append(tc).append(" ").append(res).append("\n");

        }// end of tc
        System.out.print(sb.toString());
    }// end of main

    static void makeSet() { // 자기 자신으로 초기화
        for (int i = 1; i < V+1; i++) {
            parent[i] = i;
            groupSize[i] = 1;
        }
    }

    static boolean union(int start, int end) { // 합치기
        int pStart = find(start);
        int pEnd = find(end);

        if (pStart == pEnd) return false;

        // 그룹 크기 비교 (그룹 합치기) - Union by Size (최적화)
        if (groupSize[pStart] > groupSize[pEnd]) {
            // 큰 그룹 아래에 작은 그룹 넣기
            parent[pEnd] = parent[pStart];
             // 큰 그룹 사이즈 갱신
            groupSize[pStart] += groupSize[pEnd];
        }
        else {
            parent[pStart] = parent[pEnd];
            groupSize[pEnd] += groupSize[pStart];
        }

        return true;
    }

    static int find(int v) { // 부모 찾기
        if (parent[v] == v) return v;

        return parent[v] = find(parent[v]); // 경로 압축이 같이 되어야 한다!
    }
}// end of class

풀이

Edge 클래스

각 간선들의 정보를 저장하기 위해 Edge 클래스를 선언했다. 클래스를 선언하지 않고, 2차원 배열로 만들 수 있지만, 클래스로 따로 관리하는게 더 직관적으로 이해하기 쉬워서 클래스 생성 방식을 선택했다!

    static class Edge implements Comparable<Edge> {
        int start;
        int end;
        int weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override // 정렬 기준
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

• 여기서 핵심은 compareTo로 오름차순 정렬할 기준을 선언해주는 것이다!

  오름차순 정렬

• Kruskal의 핵심!!

  Arrays.sort(edges); // 가중치가 가장 낮은 간선들을 순서로

  make-set

  처음에 각 노드들이 자기 자신을 그룹의 root로 갖도록 초기화

    static void makeSet() { // 자기 자신으로 초기화
        for (int i = 1; i < V+1; i++) {
            parent[i] = i;
            groupSize[i] = 1;
        }
    }

  union

  두 노드들을 연결하면서, 그룹의 root를 하나로 합치는 과정

    static boolean union(int start, int end) { // 합치기
        int pStart = find(start);
        int pEnd = find(end);
  
        if (pStart == pEnd) return false;
  
        // 그룹 크기 비교 (그룹 합치기) - Union by Size (최적화)
        if (groupSize[pStart] > groupSize[pEnd]) {
            // 큰 그룹 아래에 작은 그룹 넣기
            parent[pEnd] = parent[pStart];
             // 큰 그룹 사이즈 갱신
            groupSize[pStart] += groupSize[pEnd];
        }
        else {
            parent[pStart] = parent[pEnd];
            groupSize[pEnd] += groupSize[pStart];
        }
  
        return true;
    }

  find

  그룹의 root를 찾아가는 과정

    static int find(int v) { // 부모 찾기
        if (parent[v] == v) return v;
  
        return parent[v] = find(parent[v]); // 경로 압축이 같이 되어야 한다!
    }

  최적화

  1. 경로 압축

    static int find(int v) { // 부모 찾기
        ...
  
        return parent[v] = find(parent[v]); // 경로 압축이 같이 되어야 한다!
    }

  이렇게 경로 압축을 해줘야하는 이유는 어떤 정점이 다른 정점들 3개 정도와 연결되어서 그룹의 root를 찾을 수 있다면, 그 정점의 root는 이미 이전에 찾았는데 매번 같은 행위를 반복해서 해야하기에 이를 한번만 하도록 해 시간을 줄일 수 있기 때문!

(참고) return parent[v] = find(parent[v]); 이 코드는 아래의 코드와 완전히 같은 동작을 한다

int root = find(parent[v]);
parent[v] = root;
return parent[v];

2. Union by Size

이 과정은 트리의 높이가 과도하게 커지는 것을 막기 위해 사용하는 최적화 방법이다! 그룹의 root마다 그룹의 크기를 저장해서 크기가 큰 그룹에 크기가 작은 그룹을 합치는 방식으로 union에 규칙을 더한다!

static int[] groupSize = new int[V+1]; // 각 그룹의 size를 저장할 배열 생성
...

static void makeSet() { // 자기 자신으로 초기화
    for (int i = 1; i < V+1; i++) {
        ...
        groupSize[i] = 1; // 그룹 크기를 1로 초기화
    }
}

// 그룹 크기 비교 (그룹 합치기) - Union by Size (최적화)
static boolean union(int start, int end) {
    ...
    if (groupSize[pStart] > groupSize[pEnd]) {
        // 큰 그룹 아래에 작은 그룹 넣기
        parent[pEnd] = parent[pStart];
        // 큰 그룹 사이즈 갱신
        groupSize[pStart] += groupSize[pEnd];
    }
    else {
        parent[pStart] = parent[pEnd];
        groupSize[pEnd] += groupSize[pStart];
    }
}

배운 점

Union-Find 최적화

1. 경로 압축
2. Union by Size

깨달은 점

• 항상 변수 사이즈를 고려하자... 여기서도 res 크기를 생각 못해서 계속 테케 통과를 못했다... res는 최대 199_000 * 1_000_000 이라서 20억이 넘으니까 long으로 값을 저장해야한다...

• static 변수 초기화를 까먹지 말자!

SWEA_1249_보급로

요약

출발지에서 목적지까지 도착가능한 가장 최소의 시간을 구해라. 위치마다 지나가는데 기다려야하는 시간이 있다. (단, 0 ~ 9 사이의 값) 전체 맵의 크기는 N x N으로 0~100 사이의 값

접근

이 문제는 가중치가 음수가 아닌 양수인 그래프의 최소 비용 경로를 찾는 문제이다. 따라서, Djikstra를 사용해서 풀 수 있다. (벨만포드도 가능은 함)

• 다익스트라는 그리디한 BFS (출발지에서 최소 거리인 정점들을 선택해나가면서 최단 거리를 구하는 방식)

알고리즘

Djikstra

map[][] 초기환경 세팅
dist[][] 생성
dist[][]를 INF(Infinity) 값으로 채움
dist[0][0] = 0;

PriorityQueue 생성 (가중치를 오름차순 정렬) // PQ가 관리하는 값: 정점 위치 & 해당 위치까지의 최소거리
PQ에 첫번째 vertex 삽입

while(PQ is not empty)

    vertex : pq에서 꺼낸 정점
    if vertex.cost is not Minimum : vertex의 cost가 최소 비용 거리인지 확인
        continue;

    for i 0 to 4 // 4방 돌리기
        nr, nc
        not isinRange(nr, nc) continue // 범위 벗어나는지 확인

        cost = dist[vertex.x][vertex.y] + map[nr][nc]
        if (cost < dist[nr][nc]) // 기존의 다음 정점의 도착 최소 비용보다 적은지 체크
            dist[nr][nc] = cost
            pq.offer(new int[]{nr, nc, map[nr][nc]})

1. dist[][] 2차원 배열에 각 정점별 도착 가능한 최소 비용을 저장
2. 이때 dist는 모두 INF(무한대)값으로 초기화!
3. PriorityQueue를 사용해 최소거리가 되는 정점들로 이동

제출코드

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

public class Solution {
    static int[][] map;
    static int N;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int[][] dist;
    static final int INF = Integer.MAX_VALUE;

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

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

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

            for (int i = 0; i < N; i++) {
                char[] list = br.readLine().toCharArray();
                for (int j = 0; j < N; j++) {
                    map[i][j] = list[j] - '0';
                }
            }// end of map 초기화

            // 가중치를 계산해서 가장 적은 것들만 선택해서 최종적으로 도달하기 위해 메모하는 큐
            PriorityQueue<int[]> pq = new PriorityQueue<>(
                (a, b) -> Integer.compare(a[2], b[2])
            );

            // 위치별 최소 누적 비용 저장
            dist = new int[N][N];
            for (int r = 0; r < N; r++) {
                Arrays.fill(dist[r], INF);
            }

            dist[0][0] = 0; // 시작위치 초기화

            // 시작 값 집어넣음
            pq.offer(new int[]{0, 0, 0});

            while(!pq.isEmpty()) {
                int[] vertex = pq.poll();
                int x = vertex[0];
                int y = vertex[1];
                int weight = vertex[2];
                if (weight > dist[x][y]) continue; // 해당 위치의 값이 최소인지 먼저 확인

                for (int d = 0; d < 4; d++) {
                    int nr = x + dr[d];
                    int nc = y + dc[d];

                    if (!isinRange(nr, nc)) continue; // 범위 내인지 확인

                    // 누적 값 업데이트
                    if (dist[nr][nc] > dist[x][y] + map[nr][nc]) {
                        dist[nr][nc] = dist[x][y] + map[nr][nc];
                        pq.offer(new int[]{nr, nc, dist[nr][nc]});
                    }
                }
            }
            sb.append("#").append(tc).append(" ").append(dist[N-1][N-1]).append("\n");
        } // end of tc
        System.out.print(sb.toString());
    }// end of main

    static boolean isinRange(int r, int c) {
        return (r >= 0 && r < N && c >= 0 && c < N);
    }
}

느낀 점

다익스트라... 뭔가 이해한 것 같으면서도 이해하지 못한 이 느낌... 계속 문제를 접하면서 풀어봐야 알 것 같다... 확실한건, 최소 비용을 체크하는게 핵심이다!

배운 점

처음에 이걸 그냥 DFS 백트래킹으로 돌리면 안될까? 라는 생각을 해서 코드를 짰다. N이 6일때까지는 잘 돌아갔지만, 그 이상은 timeout 걸려서 안돌아갔다.. 백트래킹으로 돌리면 시간복잡도는 O($3^{N^2}$)가 된다.

4방을 돌리는데, 이전에 왔던 곳은 visited 처리가 되어있기 때문에, 3방면을 돌리고, 그 반복을 전체 정점 개수만큼 돌리기 때문에 O($3^{N^2}$)

SWEA_16546_Baby-gin

요약

0~9 사이의 숫자 6개가 주어질 때, 이 숫자들을 어떤 순서로 재배열하든 3장씩 묶었을 때 모두 같은 세 숫자(Triplet)이거나 연속된 세 숫자(Run)인 묶음 2개로 완전히 분할될 수 있는지 판별하는 문제

접근

이 문제는 주어진 6가지의 숫자로 만들 수 있는 모든 순열을 보고, Baby-gin이 되는지 파악하면 되는 문제다.

따라서 핵심은 순열을 구현하는 것!

알고리즘

• 순열 알고리즘

  static isSelected[] : 해당 위치의 숫자의 선택 여부 저장
  static numbers[] : 순열을 저장할 배열
  

void permutation(int cnt) { // cnt : 만들어진 순열의 길이 if (cnt == N) { 순열이 됐을 때 사용될 로직 return }

for (int i = 0; i < N; i++) { if (isSelected[i]) continue; // 이미 사용된 수 제외

  isSelected[i] = true;
  numbers[cnt] = i
  permutation(cnt + 1) // 다음 자리 채우기
  isSelected[i] = false; // 원상 복구 (백트래킹)

} }

# 제출코드
```java
import java.io.*;

public class Solution {
    static int[] cards;
    static boolean res;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int tc = 1; tc <= T; tc++) {
            cards = new int[6];
            res = false;

            String str = br.readLine();

            for (int i = 0; i < 6; i++) {
                cards[i] = str.charAt(i) - '0';
            }

            permutation(0, new boolean[6], new int[6]);
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        }
        System.out.print(sb.toString());
    }

    static void permutation(int cnt, boolean[] isSelected, int[] numbers) {
        if (cnt == 6) {
            // 0~2가 run? triple?
            boolean n1 = run(numbers[0], numbers[1], numbers[2]) || triple(numbers[0], numbers[1], numbers[2]);
            // 3~5가 run? triple?
            boolean n2 = run(numbers[3], numbers[4], numbers[5]) || triple(numbers[3], numbers[4], numbers[5]);

            if (n1 && n2) {
                res = true;
            }
            return;
        }

        for (int i = 0; i < 6; i++) {
            if (isSelected[i]) continue;
            isSelected[i] = true;
            numbers[cnt] = cards[i];
            permutation(cnt+1, isSelected, numbers);
            isSelected[i] = false;
            // permutation(cnt, isSelected, numbers); // 이건 굳이 다시 안해줘도 된다!
        }
    }

    static boolean run(int a, int b, int c) {
        return (b - a == 1) && (c - b == 1);
    }

    static boolean triple(int a, int b, int c) {
        return (a == b) && (b == c);
    }
}

/*

0~9까지 카드 중 임의 6장
3개가 연속 -> run
3개가 같은 번호 -> triple

6개가 run이랑 triple로 구성 -> baby gin

순열을 만들어서 확인해야한다!

// static
int[] cards = new int[6]
boolean res;

for(i = 0 ~ 6) {
    cards[i] = String.charAt(i)-'0'
}
res = false;
순열 코드

int cnt = 0;
isSelected[] = new boolean[6];
while(true) {
    if (cnt == 6);
    for (int i = 0; i < 6; i++) {
        isSelected[i] = true;

    }
}

void permutation(int cnt, boolean[] isSelected, int[] numbers) {
    if (cnt == 6) {
        // 0~2가 run? triple?
        boolean n1 = run(numbers[0], numbers[1], numbers[2]) || triple(numbers[0], numbers[1], numbers[2]);
        // 3~5가 run? triple?
        boolean n2 = run(numbers[3], numbers[4], numbers[5]) || triple(numbers[3], numbers[4], numbers[5]);

        if (n1 && n2) {
            res = true;
            return;
        }
    }

    for (int i = 0; i < 6; i++) {
        if (isSelected[i]) continue;
        isSelected[i] = true;
        numbers[cnt] = cards[i];
        permutation(cnt+1, isSelected, numbers);
        isSelected[i] = false;
        permutation(cnt, isSelected, numbers);
    }
}

boolean run(int a, int b, int c) {
    return (b - a == 1) && (c - b == 1);
}

boolean triple(int a, int b, int c) {
    return (a == b) && (b == c);
}

*/

// 여기까지 설계하는데 30분 사용! (16:29 ~ 17:02)
// 구현하는데 10분 사용! (17:08~17:19)

어려웠던 점

원상복구 한 다음에 다시 permutation을 호출했는데, 이건 하면 안된다! 다시 재귀를 부르게 되면 cnt는 계속 0이고 visited[0]은 false 상태여서 무한루프에 빠지게 된다! 부분집합을 만드는 코드와 헷갈렸다... 부분집합을 만들 때는 for 문을 사용하지 않는다!

• 재귀를 다시 한번 부르는 경우는 부분집합! why? 해당 수를 포함한다, 포함하지 않는다로 가지치기 때문!

순열에서 for문을 사용하는 이유는 순서가 중요하기 때문이다! 앞과 뒤의 순서가 중요하기 때문에 for를 0부터 계속 돌린다.

• 그렇다면 조합은? 조합은 i를 start부터 돌린다. 왜? 앞쪽부터 만들 수 있는 조합을 다 만들어서 옮기니까, start값을 증가시키면서 모든 조합을 다 만들어버린다.

아직 순열을 완벽하게 다루는데엔 부족함이 있다. 관련 문제를 찾아서 푼다면 익숙해질 것 같다!

배운 점

numbers[] 배열과 isSelected[] 배열을 static으로 선언해도 된다!

• numbers[] : 순열의 값들이 바뀌면서 자연스레 값을 덮어쓰기 때문!
• isSelected[] : 재귀를 돈 후에 false로 상태 변환을 해주기 때문!

그래서 위의 permutation 함수를 아래와 같이 만들어도 된다.

static boolean[] isSelected
static int[] numbers
static void permutation(int cnt) {

    if (res) return; // 이미 베이비진이라면 즉시 종료

    if (cnt == 6) {
        // 0~2가 run? triple?
        boolean n1 = run(numbers[0], numbers[1], numbers[2]) || triple(numbers[0], numbers[1], numbers[2]);
        // 3~5가 run? triple?
        boolean n2 = run(numbers[3], numbers[4], numbers[5]) || triple(numbers[3], numbers[4], numbers[5]);

        if (n1 && n2) {
            res = true;
        }
        return;
    }

    for (int i = 0; i < 6; i++) {
        if (isSelected[i]) continue;
        isSelected[i] = true;
        numbers[cnt] = cards[i];
        permutation(cnt+1);
        isSelected[i] = false;
    }
}

문제를 풀 때, 설계에 사용된 시간, 직접 코드로 옮기는데 걸리는 시간을 측정하면서 진행하는건 좋은 습관인 것 같다! 앞으로도 이 방식으로 코딩테스트 연습을 해나가자!

SWEA_7465_창용 마을 무리의 개수

요약

1~N 번의 번호를 가진 사람이 있을 때, 각 사람들의 인간관계를 연결해서 무리를 만들어야한다. 최종적으로, 받은 입력으로 만들어지는 전체 무리 개수를 출력해야한다.

접근

무리를 만들어서 총 몇개의 무리로 구성되어있는지를 구하는 문제이니 Union-Find를 사용했다.

Union-Find란?

서로소 집합 알고리즘으로, 교집합이 없는 집합의 개수를 구할 수 있는 알고리즘이다. 이를 위해선 총 3단계로 연산된다.

1. Make-Set(x) : 원소가 본인을 부모로 갖는 서로소 집합으로 초기화
2. Find-Set(x) : 집합 찾기 (대표자를 리턴)
3. Union(x, y) : 두 집합 합치기 (집합과 집합을 합친다)

알고리즘

1. Parent 배열을 각 원소 번호로 초기화 (Make-Set)
2. 2개의 원소들을 입력 받으며 두 원소들의 대표자를 각각 찾는다. (Find-Set)
3. 각 대표자들이 다르다면 하나의 대표자를 다른 대표자로 바꾼다. (Union)

직접 작성한 수도코드

1. makeset
각 정점을 자신을 부모로 갖도록 부모배열 상태를 초기화한다.

2. findset
선택된 정점의 부모를 찾아간다.

int findSet(int v) {
    if (v == parent[v]) return v;
    return findSet(parent[v])

3. union
두 정점의 크기 비교를 통해 큰놈 밑에 작은 놈을 붙인다.
void union(int x, int y) {
    int parentX = findSet(x);
    int parentY = findSet(y);
    if (parentX == parentY) return;
    if (parentX < parentY) {
        parent[parentY] = parentX;
    }
    else {
        parent[parentX] = parentY;
    }
}

제출코드

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

public class Solution {
    static int[] parent;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken()); // 노드 수
            int M = Integer.parseInt(st.nextToken()); // 간선의 수

            parent = new int[N+1];

            // make-set
            for (int i = 1; i <= N; i++) {
                parent[i] = i;
            }

            for (int m = 0; m < M; m++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                // union
                union(x, y);
            }

            // 무리 개수 출력
            // 무리 개수는 본인이 대표자인 애들만 세면 된다! (중요!)
            int groupCnt = 0;
            for (int i = 1; i <= N; i++) {
                if (parent[i] == i) groupCnt++;
            }

            sb.append("#").append(tc).append(" ").append(groupCnt).append("\n");
        }
        System.out.print(sb.toString());
    }

    // // find-set (경로 압축 x)
    // static int findSet(int v) { // int를 리턴!
    //     if (v == parent[v]) return v;
    //     return findSet(parent[v]);
    // }

    // find-set (경로 압축 o)
    static int findSet(int v) {
        if (parent[v] == v) return v;
        return parent[v] = findSet(parent[v]); // 경로 압축!
    }

    // union
    static void union(int x, int y) {
        int parentX = findSet(x);
        int parentY = findSet(y);
        // if (parentX == parentY) return;
        // (중요) 작은 부모의 값을 큰 부모의 값으로 옮긴다! (x와 y를 옮기는게 아니라!)
        if (parentX != parentY) { // 굳이 parentX와 parentY의 대소비교를 하지 않아도 된다! (문제에서 다른 조건이 주어진다면 여기서 집합의 부모를 대소비교 로직 추가하면 된다!)
            parent[parentY] = parentX;
        }
    }       
}

어려웠던 점

1. 마지막에 서로소 집합의 개수를 구할 때, boolean 배열에 parent[v] == v로 T/F로 구분한 뒤, boolean 배열을 순회하면서 true인 애들만 카운트 하는걸로 처음에 개수를 구했는데, 이는 비효율적인 것!

   그냥, parent[i] == i인 애들만 카운트하면 된다...

2. 대표자를 바꿨어야하는데, 그냥 입력으로 받은 x를 y로 치환해서 테케 4개를 틀렸다. (절대 까먹지 말 것!) parent[x] = y 가 아니라! parent[parentX] = parentY!!

3. 경로 압축!! find-set 코드의 리턴에 parent[x] = findSet(parent[x])로 업데이트 치는 코드로 바꿔주면 된다!

경로 압축하지 않은 최종 그래프	경로 압축한 최종 그래프
- input
```
1
10 9
1 2
3 4
5 6
7 8
9 10
2 4
6 8
4 6
8 10
```

배운 점

• 서로소 집합을 구해야할 땐, Union-Find!

• 이는 추후 크루스칼 알고리즘을 구현할 때, 활용된다!

• return parent[v] = findSet(parent[v]); 는 int를 반환한다! (아래의 식으로 컴파일러가 연산하기 때문)

  ➡️ int root = findSet(parent[v]);

    parent[v] = root;
            return root;

SWEA_7465_창용 마을 무리의 개수

요약

1~N 번의 번호를 가진 사람이 있을 때, 각 사람들의 인간관계를 연결해서 무리를 만들어야한다. 최종적으로, 받은 입력으로 만들어지는 전체 무리 개수를 출력해야한다.

접근

이 문제를 보고 사람과 사람 사이의 관계를 그래프로 표현할 수 있다고 생각했다. 각 사람을 정점으로 두고, 서로 알고 있는 두 사람 사이에 간선을 연결하면 된다.

그래프는 인접 행렬과 인접 리스트 모두 사용할 수 있다. 인접 행렬은 두 사람이 연결되어 있는지 O(1)에 확인할 수 있지만, 특정 사람과 연결된 모든 사람을 찾으려면 1번부터 N번까지 확인해야 한다. 또한 사람 수가 많고 실제 관계의 수가 적다면 사용하지 않는 공간이 많아질 수 있다.

이 문제에서는 한 사람과 연결된 사람들을 탐색하고, 다시 그 사람들과 연결된 사람들을 연속해서 탐색해야 한다. 따라서 실제로 연결된 사람들만 저장하고 탐색할 수 있는 인접 리스트가 더 자연스럽다고 판단했다.

각 사람마다 연결된 사람들을 리스트에 저장한 뒤, 1번부터 N번까지 순차적으로 확인한다. 아직 방문하지 않은 사람을 발견하면 새로운 무리라고 판단해 무리의 개수를 1 증가시키고, DFS나 BFS를 통해 해당 사람과 연결된 모든 사람을 방문 처리한다. 이후 이미 방문한 사람은 같은 무리에 속한 사람이므로 다시 탐색하지 않는다. 나는 BFS를 활용해서 문제를 풀었다.

이 과정을 N번 사람까지 반복하면 서로 연결된 사람들의 집합, 즉 연결 요소의 개수를 구할 수 있고 이것이 마을의 무리 개수가 된다.

알고리즘

1. 인접 리스트로 사람 사이의 관계를 표현한다.
2. visited 배열을 만들어 각 사람의 방문 여부를 관리한다.
3. 1번부터 N번까지 순차적으로 확인한다.
4. 현재 사람이 이미 방문했다면 같은 무리에서 처리된 사람이므로 넘어간다.
5. 아직 방문하지 않은 사람이라면 새로운 무리의 시작이므로 무리 수를 1 증가시키고, 해당 사람을 Queue에 넣어 BFS~
6. Queue에서 사람을 하나씩 꺼내 해당 사람과 연결된 사람들을 확인한다. 아직 방문하지 않은 사람이 있다면 방문 처리한 뒤 Queue에 넣는다.
7. Queue가 빌 때까지 반복하면 현재 사람과 연결된 하나의 무리가 모두 처리된다.
8. N번 사람까지 반복한 뒤 무리 수를 출력한다.

제출 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class swea_7465_창용마을무리의개수 {
    static boolean[] visited;
    static List<List<Integer>> peoples;
    static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            N = Integer.parseInt(st.nextToken()); // 정점 개수
            int M = Integer.parseInt(st.nextToken()); // 엣지 개수
            int group = 0; // 그룹 수 카운트
            peoples = new ArrayList<>(); // 사람들 연결된 그래프

            for (int i = 0; i <= N; i++) {
                peoples.add(new ArrayList<>()); // 0~N번까지 노드까지 초기화
            }
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());

                // 양방향 처리
                peoples.get(s).add(e);
                peoples.get(e).add(s);
            }

            // 인접리스트 확인
            // printAdjList();

            visited = new boolean[N+1]; // 인맥 방문 처리

            for (int i = 1; i <= N; i++) {
                if (!visited[i]) {
                    bfs(i);
                    group++;
                }
            }

            sb.append("#").append(tc).append(" ").append(group).append("\n");
        }
        System.out.println(sb.toString());
    }

    static void bfs(int people) {
        visited[people] = true;
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(people);

        while(!q.isEmpty()) {
            int me = q.poll();
            for (int i = 0; i < peoples.get(me).size(); i++) {
                // 나와 연결되어있는 친구를 큐에 넣는다.
                int friend = peoples.get(me).get(i);
                if (!visited[friend]) {
                    q.offer(friend);
                    visited[friend]= true;
                }
            }
        }
    }

    // static void printAdjList() {
    //     System.out.println();
    //     for (int i = 0; i <= N; i++) {
    //         System.out.print(i + " : ");
    //         if (peoples.get(i).isEmpty()) {System.out.println(); continue;}
    //         for (int j = 0; j < peoples.get(i).size(); j++) {
    //             System.out.print(peoples.get(i).get(j) + ", ");
    //         }
    //         System.out.println();
    //     }
    // }
}

어려웠던 점

• 인접 리스트 개념은 알고 있는데 직접 구현하려니 어렵다..
  • ArrayList로 구현을 했는데, 처음이라 어색한 듯하다... 이걸 LinkedList로 직접 구현해서 푸는 방법으로도 해봐야한다.
• 또 다른 핵심은 무방향 그래프이기에 양방향 그래프로 처리를 해야한다! 단방향으로 처리하게 되면, 모든 관계를 표현하지 못한다.

깨달은 점

List<List> 이렇게 구현할수도 있고, List[] 이렇게 구현하면, 배열 안에 List를 집어넣을 수 있다!

SWEA_2105_디저트_카페

요약

N개의 2차원 배열 안에 1~100까지의 숫자들이 주어질 때, 대각선 방향으로 움직이면서 만들 수 있는 모든 사각형 중 사각형의 구성 숫자들이 곂치지 않는 사각형을 구성하는 칸의 최대 개수!

접근

이걸 사각형 모양을 만들어야하니까 N-Queen처럼 하나씩 놔보면서 사각형이 만들어지는지를 확인해간다 생각하면 백트래킹이 떠오른다!

알고리즘

격자 그래프로 생각하고, dfs를 활용한 백트래킹!

최종 코드

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

public class Solution {
    static int N, res; // N: 배열 크기, res : 사각형의 최대크기기
    static int[][] desert;
    // {r+1, c+1 / r+1, c-1 / r-1, c-1 / r-1, c+1}
    static int[] dr = {1, 1, -1, -1};
    static int[] dc = {1, -1, -1, 1};
    static int startR, startC; // 사각형의 첫 시작점
    static boolean[] visited;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
            desert = new int[N][N];
            res = -1;

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

            for (int r = 0; r < N; r++) {
                for (int c = 0; c < N; c++) {
                    // 4 꼭짓점들은 못돌게 막는다.
                    if ((r == 0 && c == 0) || (r == 0 && c == N-1) || (r == N-1 && c == N-1) || (r == N-1 && c == 0)) continue;
                    startR = r;
                    startC = c;
                    visited = new boolean[101];
                    visited[desert[r][c]] = true;
                    dfs(r, c, 0, 1);
                }
            }

            sb.append("#").append(tc).append(" ").append(res).append("\n");
        }
        System.out.println(sb.toString());
    }

    static void dfs(int r, int c, int dir, int count) {
        int nr = r + dr[dir];
        int nc = c + dc[dir];

        // 기저 조건
        // 시작 row보다 높이 못간다.
        if (nr < startR) {
            return;
        }
        // 방향을 3번 바꿈 + 시작 위치로 돌아왔는가.
        if (dir == 3 && nr == startR && nc == startC) {
            // System.out.println("dir == 3 && nr == startR && nc == startC");
            //최댓값 (res와 count 비교해서 큰걸 res)
            if (res < count) {
                res = count;
            }
            return;
        }
        // 다음 이동 위치가 범위 벗어나면 종료
        if (nc >= N || nr >= N || nc < 0 || nr < 0) {
            return;
        }

        // 이미 먹은 디저트라면 패스
        if (visited[desert[nr][nc]]) {
            return;
        }
        // 순환 파트 -----------
        // visited[desert[nr][nc]] = true;

        // 꺾기 // dir이 3이 아닐때만 (3은 오직 직진)
        if (dir != 3) {
            visited[desert[nr][nc]] = true;
            dfs(nr, nc, dir+1, count+1); // 백트래킹
            visited[desert[nr][nc]] = false;
        }
        // 직진 시키기
        visited[desert[nr][nc]] = true;
        dfs(nr, nc, dir, count+1); // 백트래킹
        visited[desert[nr][nc]] = false;
    }
}

어려웠던 점

백트래킹이 아직 익숙하지 않아서 visited 관리를 못해서 못풀었다. 문제를 푸는데 총 3시간이 걸렸다. 대각선으로 사각형 조합을 만드는건 알겠는데, 이를 어떻게 구현해야하는지 도저히 감이 안와서 이것부터 AI에게 구현 방식에 대해 아이디어를 도움을 받았다. ➡️ dr, dc를 대각으로 돌리는건 맞는데, 백트래킹으로 꺾었을 때, 꺾지 않았을 때로 사각형 조합이 만들어지는지를 확인하면서 나아가야한다!

깨달은 점

• 디버거를 쓰는게 정말 중요하다! (이걸로 static 초기화 안한거 찾았다...)

SWEA_7733_치즈도둑

요약

정사각형의 치즈가 인풋으로 주어지고, 각 칸마다 숫자가 있다. 각 시간마다 시간과 일치하는 숫자의 칸을 먹는다. 그 과정에서 남은 치즈들의 덩어리가 생기는데, 전체 치즈를 다 먹는 과정에서 생기는 치즈 덩어리의 최댓값을 구해라!

접근

이 문제를 보자마자 '격자 그래프'가 떠올랐다. 그리고, 덩어리들을 묶어야하니까 BFS로 찾는 방식을 택했다. BFS로 아직 남아있는 덩어리들을 방문처리를 하고, 다 방문했으면 덩어리 개수를 1 올리는 방식!

알고리즘

1. 맛있는 정도의 최댓값을 인풋을 받을 때, 저장한다
2. 맛있는 정도가 최댓값이 될 때까지 아래의 과정을 반복한다.
3. 격자 그래프를 순회하면서 지금의 맛있는 정도보다 높은 칸이면서 아직 방문하지 않은 칸을 찾는다. 3-1. BFS 탐색

     3-1-1. 처음 들어온 칸을 Queue에 넣는다.
     3-1-2. 해당 칸을 방문처리한다.
     3-1-3. Queue가 비어있지 않을때까지 반복한다.
     3-1-4. Queue의 요소를 뺀다.
     3-1-5. 해당 요소의 위치를 방문처리한다.
     3-1-6. 4방처리하면서 아직 방문하지 않았으면서, 지금의 맛있는 정도보다 높은 칸이면 해당 칸을 Queue에 넣는다.

   3-2. 덩어리의 개수를 1 증가시킨다.
4. 지금까지의 덩어리 수와 지금 맛있는 정도의 덩어리 수의 최댓값을 비교 후 최댓값 업데이트

제출 코드

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

public class swea_7733_치즈도둑 {
    static int[][] cheese;
    static boolean[][] visited;
    static int res;
    static int N;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 치즈 배열 크기

        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
            cheese = new int[N][N]; // 치즈 원본 생성
            int X = 0;
            res = 1;
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    cheese[i][j] = Integer.parseInt(st.nextToken());
                    if (cheese[i][j] > X) X = cheese[i][j];
                }
            }

            int cnt = 1;

            while (cnt <= X) {
                visited = new boolean[N][N];
                int combine = 0;
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        if (cheese[r][c] > cnt && !visited[r][c]) {
                            // System.out.println("cheese[r][c] <= cnt && !visited[r][c]");
                            Node n = new Node(r, c);
                            bfs(n, cnt); // bfs돌리면서 visited 처리하고 다 돌면 카운트처리
                            combine++;
                        }
                    }
                }
                // 치즈덩어리 개수 비교
                if (res < combine) {
                    res = combine;
                    // System.out.println("res < combine");
                }
                cnt++;
            }
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        } // end of tc
        System.out.println(sb.toString());
    } // end of main

    public static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void bfs(Node n, int cnt) {
        // 방문을 기록할 노트
        Queue<Node> q = new ArrayDeque<>();
        // 시작 노드 집어 넣는다.
        q.offer(n);
        int r = n.x;
        int c = n.y;
        // 시작노드 방문처리
        visited[r][c] = true;

        while(!q.isEmpty()) {
            Node next = q.poll();
            for (int i = 0; i < 4; i++) {
                int nr = next.x+dr[i];
                int nc = next.y+dc[i];
                // 범위 가두기
                if (nr >= 0 && nr < N && nc >= 0 && nc < N && cheese[nr][nc] > cnt && !visited[nr][nc]) {
                    q.offer(new Node(nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }
    }
} // end of class

어려웠던 점

• 어렵다기보단 내가 아직 BFS에 익숙하지 않다는 것을 느꼈다.
• BFS가 손에 익었다면 20분? 30분?이면 풀었을 문제를 1시간이 걸렸다...
• 다시보니 정말 기본적인 그래프 BFS 문제였는데 아직 구현이 약하다는게 스스로 느껴진다...

다시는 까먹으면 안되는 것!

🌟 전부다 1일때를 놓쳤다. -> 모든 덩어리는 최소 1개이므로 덩어리의 초기값은 1로 초기화했어야 한다..

🌟 res를 초기화 하는걸 놓쳤다. -> static 변수들은 항상 테케안에서 초기화하는걸 명심할 것!

🌟 제미나이의 테케를 믿지말것. 제미나이한테 테케 생성해달라했다가 제미나이가 숫자 잘못센거때문에 20분 넘게 코드를 계속 고민했다...

🌟 문제를 처음 봤을 때, 시간복잡도부터 계산했다.

  N은 최대 100, X값도 최대 100이니까 이 문제는 O(N^2 * X) 안에 다 돌려야한다고 판단해서 코드를 짤때도 이를 생각하면서 짜서 시간초과가 안났다!! (이건 잘한듯 ㅎㅎ) 다음에도 이래야한다!

SWEA_1953_탈주범검거

요약

지하 터널의 맨홀 뚜껑 위치에서 시작해, 서로 연결 가능한 7종류의 파이프를 타고 이동할 때 경과 시간 $L$ 이하로 탈주범이 도달할 수 있는 모든 터널 위치(격자 칸)의 개수를 구하는 문제

접근

문제를 처음 보자마자 느낀건 각 파이프마다 상하좌우별 연결될 수 있는 파이프가 다 달라서 이 조합을 먼저 선언해둬야겠다 생각했다. 그리고 시작 위치부터 bfs로 돌리면서 $L$까지 돌리고, 그때 앞서 선언한 상하좌우별 연결되는 파이프가 있다면 answer값을 1씩 올리면서 최종적으로 answer값을 반환하면 될 것이라 생각하고 접근했다.

알고리즘

1. 전체 2차원 배열을 하나 만든다.
2. 값들을 기본 값(파이프 위치)에 맞게 초기화한다.
3. dr, dc를 만들어 상하좌우 탐색을 하게 만든다.
4. 기본 위치를 시작으로 visited 배열로 방문 여부를 체크하면서, $L$ 너비까지 상하좌우 bfs 탐색을 돌린다.
5. 현재 내 위치의 파이프와 상하좌우 파이프의 조합을 확인하며 연결된다면 answer값을 증가시키고 visited 위치를 true로 변경한다.
6. 최종적으로 answer값을 출력한다.

제출 코드

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

public class Solution {
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static int[][] land;
    static boolean[][] visited;
    // 파이프의 각 방향이 뚫려있을 때, 연결할 수 있는 파이프들
    static int[] up = {1,2,5,6};
    static int[] down = {1,2,4,7};
    static int[] left = {1,3,4,5};
    static int[] right = {1,3,6,7};
    static int N;
    static int M;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken())+1;
            M = Integer.parseInt(st.nextToken())+1;
            int R = Integer.parseInt(st.nextToken())+1; // 시작 위치 x
            int C = Integer.parseInt(st.nextToken())+1; // 시작 위치 y
            int L = Integer.parseInt(st.nextToken()); // 소요 시간

            land = new int[N][M]; // 테두리를 한바퀴 두름
            visited = new boolean[N][M]; // 해당 파이프 방문 여부 체크
            // 땅 생성
            for (int i = 1; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 1; j < M; j++) {
                    land[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            int res = bfs(L, R, C);
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        }
        System.out.print(sb.toString());
    }

    public static int bfs(int breadth, int x, int y) {
        int res = 0;
        Queue<Node> q = new ArrayDeque<>();
        // 시작 파이프 집어 넣음
        q.offer(new Node(x, y, land[x][y]));
        visited[x][y] = true;
        res += 1;
        int time = 1;

        while(!q.isEmpty()) {
            // 목표만큼 너비 탐색 했으면 종료
            if (time >= breadth) break;

            int size = q.size();
            for (int s = 0; s < size; s++) {
                Node n = q.poll();
                // 현재 노드의 사방면을 조사
                for (int i = 0; i < 4; i++) {
                    // 지금 노드의 파이프와 사방면 각각의 파이프가 매칭이 가능한지
                    int nr = n.x+dr[i];
                    int nc = n.y+dc[i];
                    if (nr < 0 || nr >= N || nc < 0 || nc >= M) {
                        continue;
                    }
                    // 연결된 위치의 파이프
                    int nextPipe = land[nr][nc];
                    if (isConnected(n.pipe, nextPipe, i) && !visited[nr][nc]) {
                        q.offer(new Node(nr, nc, land[nr][nc]));
                        visited[nr][nc] = true;
                        res+=1;
                    }
                }   
            }
            time++;
        }

        return res;
    }

    public static boolean isConnected(int pipeA, int pipeB, int direct) {
        if (pipeB == 0) return false;

        if (pipeA == 1) {
            // 상
            if (direct == 0) {
                for (int i : up) {
                    if (i == pipeB) return true;
                }
            }
            // 하
            else if (direct == 1) {
                for (int i : down) {
                    if (i == pipeB) return true;
                }
            }
            // 좌
            else if (direct == 2) {
                for (int i : left) {
                    if (i == pipeB) return true;
                }
            }
            // 우
            else {
                for (int i : right) {
                    if (i == pipeB) return true;
                }
            }
        }
        else if (pipeA == 2) {
            // 상
            if (direct == 0) {
                for (int i : up) {
                    if (i == pipeB) return true;
                }
            }
            // 하
            if (direct == 1) {
                for (int i : down) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 3) {
            // 좌
            if (direct == 2) {
                for (int i : left) {
                    if (i == pipeB) return true;
                }
            }
            // 우
            if (direct == 3) {
                for (int i : right) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 4) {
            // 상
            if (direct == 0) {
                for (int i : up) {
                    if (i == pipeB) return true;
                }
            }
            // 우
            if (direct == 3) {
                for (int i : right) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 5) {
            // 하
            if (direct == 1) {
                for (int i : down) {
                    if (i == pipeB) return true;
                }
            }
            // 우
            if (direct == 3) {
                for (int i : right) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 6) {
            // 하
            if (direct == 1) {
                for (int i : down) {
                    if (i == pipeB) return true;
                }
            }
            // 좌
            if (direct == 2) {
                for (int i : left) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        else if (pipeA == 7) {
            // 상
            if (direct == 0) {
                for (int i : up) {
                    if (i == pipeB) return true;
                }
            }
            // 좌
            if (direct == 2) {
                for (int i : left) {
                    if (i == pipeB) return true;
                }
            }
            return false;
        }
        return false;
    }

    public static class Node {
        int x;
        int y;
        int pipe;

        public Node(int x, int y, int pipe) {
            this.x = x;
            this.y = y;
            this.pipe = pipe;
        }
    }
}

어려웠던 점

bfs를 짜면서, 특정 시간($L$)이 되었을 때, 종료시키는 걸 구현하는게 bfs 알고리즘 구현하는게 익숙하지 않아서 어려웠다.

• 시간 제한이나 거리 제한이 있는 bfs의 경우 q.size()로 레벨 순회를 사용하거나 bfs로 넘기는 값에 time이나 length와 같이 변수를 만들어 관리해야한다!

또한 처음에 방문 여부를 체크하지 않고 그냥 돌려서 무한루프에 빠지기도 했다. 이미 연결되었던 부분에 대해선 visited 체크를 통해 다시 방문하지 않도록 처리하는게 중요하다!

또 내 위치의 파이프가 1번 파이프인 경우, 어차피 연결된다 생각하고, true를 반환했는데, 1번 파이프와 연결되지 않는 파이프들도 있다는걸 뒤늦게 파악했다. 이를 파악하는데 시간을 소모했다..

추가로...) pipe끼리 연결되는지에 대한 여부를 모두 하드코딩으로 박았는데, 이게 맞는지 잘 모르겠다... ➡️비트 마스킹을 사용하거나, 2차원 배열로 파이프별 가능한 여부를 저장해두는 방식으로 구현하면 가능하다고 한다... 비트마스킹을 잘 모르니까, 이와 관련한 문제를 여러 문제 풀면서 익혀야한다는걸 느낀다... (세상엔 참 배워야할게 많다...)

새롭게 알게된 점

코드를 작성할 때, step by step으로 잘 구현되고 있는지 확인하는 것이 중요한 것임을 또 깨달았다... 다 만들고 돌리니 어디서부터 잘못된건지 찾기가 너무 어렵다!!

Programmers_베스트앨범

요약

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 해야한다.

정렬 우선순위 1 : 가장 많이 재생된 장르순 정렬 우선순위 2 : 장르 내에서 가장 많이 재생된 노래순 정렬 우선순위 3 : 고유 번호가 낮은 노래순

접근

문제를 처음 보자마자 노래를 지칭하는 객체를 하나 만들고, 그 객체에 대해서 언급된 우선순위에 맞게 정렬하면 해결될 것이라는 생각을 했다. 여기서 가장 중요하게 느껴졌던 점은 노래 객체를 저장할 자료구조를 선정하는 것이었다. 그리고, 우선순위 정렬을 하는 방법을 알고 있느냐, 익숙하게 다룰 수 있느냐 또한 중요한 것으로 보였다.

장르별 노래 플레이 횟수가 저장되도록하기 위해 key를 genre, value를 play로 하는 Map을 사용했고, 이를 활용해 먼저 정렬되어야 하는 기준을 잡았다. 그리고 Music 배열을 map.size()만큼 만들어서 그 배열을 Comparator의 compare 함수를 오버라이드해서 쓰면 해결될 것이라 생각하고 접근했다.

알고리즘

1. genre, play, 고유 번호를 저장하는 Music 클래스를 만든다.
2. for문으로 돌면서 Music 객체를 만들고, 이 객체의 genre와 play 값을 활용해 Map에 값을 누적시킴과 동시에 Music 배열에 그 객체를 집어 넣는다.
3. Array.sort()를 하면서, Comparator 인터페이스를 활용해 문제의 기준에 맞게 정렬되도록 만든다. (이때, map을 함께 활용해 우선순위를 정렬하는 것이 핵심!)
4. 정렬된 Music 배열을 순회하면서 장르별 정렬 기준에 맞게 상위 2개 이하씩 뽑히도록 돈다.
5. 최종적으로 result 배열을 출력한다.

제출 코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        // 총 음악 개수
        int len = genres.length;
        Music[] musics = new Music[len];
        // 장르별 노래 개수 저장
        Set<String> set = new HashSet<>();
        Map<String, Integer> map = new HashMap<>();

        // 장르 종류 저장
        for (int i = 0; i < len; i++) {
            set.add(genres[i]);
        }
        // 장르 개수 저장
        for (String genre : set) {
            map.put(genre, 0);
        }

        for (int i = 0; i < len; i++) {
            String genre = genres[i]; // 현재 인덱스의 장르
            musics[i] = new Music(genre, plays[i], i);
            map.put(genre, map.get(genre)+plays[i]);
            // map.put(genre, map.getOrDefault(genre, 0)+plays[i]); // Set을 쓰지 않고 해결 가능
        }

        // 3가지 정렬 기준에 맞춰서 정렬 (Comparable)
        Arrays.sort(musics, new Comparator<Music>() {
            @Override
            public int compare(Music a, Music b) {
                if (a.genre.equals(b.genre)) {
                    if (a.play == b.play) {
                        return a.idx - b.idx;
                    }
                    return b.play - a.play;
                }
                return map.get(b.genre).compareTo(map.get(a.genre));
            }
        });

        List<Integer> answer = new ArrayList<>();

        String genre = "";
        // 정렬된 배열을 끝까지 돔
        for (int i = 0, cnt = 0; i < musics.length; i++) {
            // 이전 곡과 같은 장르인 경우
            if (genre.equals(musics[i].genre)) {
                // 이미 2곡을 선택했다면 다음으로 이동
                if (cnt == 2) {
                    continue;
                }
                // 2곡 선택되지 않았다면 해당 앨범의 인덱스 추가
                else {
                    cnt++;
                    answer.add(musics[i].idx);
                }
            }
            // 새로운 장르인 경우
            else {
                cnt = 1;
                genre = musics[i].genre;
                answer.add(musics[i].idx);
            }
        }

        int[] arr = new int[answer.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = answer.get(i);
        }
        return arr;
    }
    public static class Music {
        String genre;
        int play;
        int idx;

        public Music(String genre, int play, int idx) {
            this.genre = genre;
            this.play = play;
            this.idx = idx;
        }
    }
}

// 알고리즘 
// 자료구조 : Class와 Array 사용하면 풀릴 것 같다.
// 조건 
// Class를 먼저 정렬한다. 그 후 노래별 재생횟수로 정렬한다.

어려웠던 점

Comparator 인터페이스를 활용해 다중 정렬을 사용하는게 처음이라 문법이 조금 어색하고 어려웠다. 특히 map을 활용해 정렬을 한다는 걸 스스로 알아내기까지 시행착오가 많았다.

상위 2개를 뽑고 나머지는 뽑지 않아야하는 걸 구현하는데 생각보다 애를 먹었다. cnt를 올리다가 2가 되고, 장르가 같다면 continue 치면 되는건데, 어렵게 index 를 점프 시키려고 하다가 코드가 좀 꼬인 부분이 있었다. 시간을 줄이려고 한거지만, 실제 시험에서는 이 생각보단 가장 컴팩트하게 해결할 수 있는 방법으로 접근한 뒤 시간 초과가 발생하면 이 방식으로 접근해보자!

새롭게 깨달은 점

Map에 값을 넣을 때, set을 써서 map에 key 만들고, 초기화하고 하는건 절대하지말 것! Map의 getOrDefault() 메서드를 활용하자!!!

map.put(genre, map.getOrDefault(genre, 0)+plays[i]); // Set을 쓰지 않고 해결 가능

SWEA_5658_보물상자 비밀번호

요약

정사각형 형태의 보물상자 뚜껑 네 변에 총 $N$개의 16진수 숫자(0~F)가 적혀 있다. 상자를 시계 방향으로 한 칸씩 회전시킬 수 있으며, 회전할 때마다 네 변에 위치한 숫자들(각 변마다 $N/4$자리 수)을 읽어 16진수 숫자를 만든다. 생성 가능한 모든 16진수 중 중복을 제거하고 내림차순으로 정렬했을 때, $K$번째로 큰 수를 10진수로 변환하여 출력한다.

접근

문제를 봤을 때, 별다른 알고리즘이 떠오르기보단 자료구조를 무엇을 선택할까가 가장 중요하고 고민되었던 지점이다. 번호 중복이 되면 안되니 이를 Set으로 관리하고, 이 Set에 저장된 것들을 배열로 바꿔서 정렬하면 되겠다는 생각이 들었다.

회전시켜야하니까, 이를 Queue를 활용해서 앞에걸 빼서 뒤에 집어넣으면 되겠다 생각했다. 근데 이는 알고보니 '반시계' 방향이었다. 시계 방향으로 회전시키기 위해선 뒤에서 빼서 앞으로 집어넣어야한다. 그래서 Deque을 써야한다!

그리고 16진수를 10진수로 바꾸는 함수를 만들고, N/4의 개수가 되면 이를 변환할 수 있는 함수 총 2개를 만들어야겠다 생각했다.

알고리즘

1. 시계 방향 회전을 위한 Deque 활용

• 상자가 시계 방향으로 회전하는 형태이므로, 맨 뒤의 원소를 꺼내 맨 앞에 삽입하는 연산이 필요해 양방향 입출력이 가능한 Deque 자료구조로 회전을 구현한다.

2. $N/4$ 단위 분할 및 진법 변환

• 상자가 1칸 회전할 때마다 네 변의 숫자들을 $N/4$개씩 잘라 16진수 문자열을 만들고, 이를 10진수 정수로 변환한다.

3. Set을 통한 중복 제거

• 동일한 숫자가 여러 번 생성될 수 있으므로, 변환된 10진수 값들을 Set 자료구조에 추가하여 중복을 자동으로 걸러낸다. 한 변의 길이가 $N/4$이므로 총 $N/4$번만 회전시키면 모든 가능한 조합을 수집할 수 있다.

4. 배열(List) 변환 후 정렬 및 $K$번째 값 추출

• Set에 모인 고유한 숫자들을 배열(List)로 변환한 뒤 내림차순으로 정렬하고, $K$번째($K-1$ 인덱스) 원소를 정답으로 도출한다.

제출 코드

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

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

        int T = Integer.parseInt(br.readLine());
        for (int tc=1; tc<=T; tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            // 비밀번호 숫자들 받음
            String passwords = br.readLine();
            // 각 번호들 저장
            ArrayDeque<String> numbers = new ArrayDeque<>();

            for (int i = 0; i < N; i++) {
                numbers.offer(passwords.charAt(i)+"");
            }

            Set<Integer> set = new HashSet<>();

            // N/3번 돌린다 (다시 원래 위치로 번호들이 오게되는 총 회전 수)
            for (int i=0; i<N/4; i++) {
                // N번 돌리면서 q에서 빼고 집어넣으며 숫자조합 만듦
                String num = "";
                for (int j=0; j<N; j++) {
                    // 앞의 숫자를 빼고 뒤에 넣는다. 그러면서 모든 3자리 숫자 체크
                    String temp = numbers.pollFirst();
                    num += temp;
                    numbers.offerLast(temp);
                    // 3번 돌렸으면 이를 10진수로 바꿔서 Set에 박음
                    if (num.length() == N/4) {
                        // 숫자로 변경
                        int pwd = strToInt(num);
                        set.add(pwd);
                        num = "";
                    }
                }
                // 앞을 빼서 뒤로 넣는다.
                String front = numbers.pollLast();
                numbers.offerFirst(front);
            }

            // Set의 값들을 배열로 변경
            int[] pwdList = new int[set.size()];
            int idx = 0;
            for (int pwd : set) {
                pwdList[idx++] = pwd;
            }

            Arrays.sort(pwdList);
            int kPwd = pwdList[set.size()-K];
            sb.append("#").append(tc).append(" ").append(kPwd).append("\n");
        }
        System.out.print(sb.toString());
    }

    // 16진수 -> 10진수
    public static int c16to10(String num16) {
        char c = num16.charAt(0);
        int num10 = 0;
        if (c > '9') {
            num10 = c-'A'+10;
        }
        else {
            num10 = c-'0';
        }
        return num10;
    }

    // 숫자로 변환!
    public static int strToInt(String num) {
        int res = 0;
        String[] nums = num.split("");
        for (int i=0; i<nums.length; i++) {
            // 각 자리 숫자
            int n = c16to10(nums[i]);
            res += Math.pow(16, nums.length-1-i)*n;
        }
        return res;
    }
}

어려웠던 점

1. StringTokenizer!! 이거는 한글자한글자 못 뜯어낸다! 띄어쓰기가 있을 때만 쓰고, 구분자가 없는 경우엔 charAt()이나 split()으로 뜯어내야한다!
2. 시계 방향, 반시계 방향이 너무 헷갈렸다.. 처음엔 그냥 Queue를 썼는데, 왜 안되지 하고 계속 코드 고치다가 도저히 안풀려서 Gemini에게 힌트를 달라고하니, Deque로 해야 시계방향으로 회전된다는걸 알았다... Deque의 메서드도 좀 잘 알아야겠다!
3. 그리고 내림차순을 해야했는데, 이를 고려못하고 그냥 오름차순에서 K값을 찾으려했다... Collections.reverse()에 익숙해지자!

새로 알게 된 점

1. 완벽히 회전시켜야한다면 똑같은걸 뒤에 한번 더 붙이면 된다!

• 알고있었는데, 이 문제를 봤을 때, 생각이 안났다... 익숙해지도록 연습하자!

2. String의 16진수를 바로 10진수로 바꿀 수 있다니! Integer.parseInt("1F4", 16); 이거면 바꿀 수 있다는걸 처음 알았다... 직접 16진수 변환하는 코드 짰는데...

최적화한 코드

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

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

        int T = Integer.parseInt(br.readLine());
        for (int tc=1; tc<=T; tc++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            // 비밀번호 숫자들 받음
            String passwords = br.readLine();
            // 비밀번호 rotate하는 대신 2번 반복시켜서 rotate하는 효과 만듦
            String rotatedPwd = passwords+passwords;
            // 중복 비밀번호 처리를 위한 Set
            Set<Integer> set = new HashSet<>();

            // 한 변에 N/4만큼 숫자들이 있을 수 있으니 N/4번 반복
            for (int i=0; i<N/4; i++) {
                // N/4의 길이만큼 띄어서 비밀번호로 자르도록 함
                for (int j=i; j<N; j+=N/4) {
                    // N/4의 길이만큼 자름
                    String pwd = rotatedPwd.substring(j, j+N/4);
                    // String의 16진수를 10진수로 변환
                    int intPwd = Integer.parseInt(pwd, 16);
                    // Set에 집어넣어서 중복제거 처리
                    set.add(intPwd);
                }
            }

            // Set의 값들을 배열로 변경
            int[] pwdList = new int[set.size()];
            int idx = 0;
            for (int pwd : set) {
                pwdList[idx++] = pwd;
            }

            Arrays.sort(pwdList); // 오름차순 정렬
            // N번째로 큰걸 알기 위해 역순으로 접근 (내림차순)
            int kPwd = pwdList[set.size()-K];
            // Arrays.sort(pwdList, Collections.reverseOrder()); (내림차순)
            // int kPwd = pwdList[K];
            sb.append("#").append(tc).append(" ").append(kPwd).append("\n");
        }
        System.out.print(sb.toString());
    }
}

Programmers - 주차 요금 계산

요약

차량의 입·출차 기록이 주어질 때, 주차장의 정해진 기본요금, 추가요금에 맞게 각 차량별 주차요금을 계산해야한다.

단, 입차 후 출차 기록이 없는 차량은 23:59에 나간 것으로 간주. 추가 요금 발생 시간이 나누어 떨어지지 않는 경우, 올림으로 시간을 반영해 추가요금 청구. 최종 결과는 차량 번호의 오름차순대로 누적 요금을 출력할 것.

접근

이 문제를 처음 봤을 때, 문제의 길이가 길어서 이해할게 많고, 알고리즘까지 생각하기 어려울 것이라 생각했다. 근데, 긴 문제의 특징은 요구하는 사항에 맞게 구현만 올바르게 하면 되는 것이었다. 문제의 요구사항을 파악하고 이를 코드로 적절히 옮기기만한다면 문제가 해결될 것이라 생각했다. 여기서 핵심은 차량을 관리하는 자료구조를 어떤 것을 쓸 것이냐였다.

알고리즘

이번 문제는 알고리즘이라기보단, 자료구조를 선택하는게 키포인트였다.

먼저 차량의 입출차 정보를 기록하기 위해선 Map 자료구조로 key, value로 차량의 입차정보를 관리했다. 차량이 출차되는 순간 해당 차량의 정보를 key로 조회해서 출차시간과 입차시간을 계산한다. 그 값을 차량의 누적 주차시간을 저장할 또다른 Map에 저장한다. 이때, 해당 Map은 TreeMap을 사용한다.

• TreeMap은 key 값을 자동으로 오름차순 정렬하는 특징이 있다. 이를 활용해 문제의 조건인 오름차순 정렬을 해결한다. 최종적으로 TreeMap에 저장된 차량 번호 순서대로 누적 시간을 가져와서 이를 요금 기준에 맞게 계산하면 해결된다.

제출 코드

import java.util.HashMap;
import java.util.TreeMap;
import java.util.Set;

class Solution {
    static int giTime;
    static int giFee;
    static int danTime;
    static int danFee;

    public int[] solution(int[] fees, String[] records) {

        giTime = fees[0];
        giFee = fees[1];
        danTime = fees[2];
        danFee = fees[3];
        // 입출차 관리 맵
        HashMap<Integer, String> map = new HashMap<>();
        // 차량별 누적 요금 관리
        TreeMap<Integer, Integer> carTime = new TreeMap<>();

        for (String r : records) {
            String[] record = r.split(" ");
            String time = record[0]; // 시각
            int car = Integer.parseInt(record[1]); // 차량 번호
            String ny = record[2]; // 내역
            // 입차
            if (ny.equals("IN")) {
                map.put(car, time);
            }
            // 출차
            else {
                int totalTime = 0;
                // 입차했던 시간 가져옴. 동시에 해당 차량 삭제
                String icTime = map.remove(car);
                String[] ic = icTime.split(":"); // 입차시간
                String[] cc = record[0].split(":"); // 출차시간
                int min = Integer.parseInt(cc[1]) - Integer.parseInt(ic[1]);
                int hour = Integer.parseInt(cc[0]) - Integer.parseInt(ic[0]);
                if (min < 0) {
                    min = 60 + min;
                    hour -= 1;
                }
                // 누적 주차 시간
                totalTime = hour * 60 + min;
                // 차에 시간을 누적함 (차량이 처음 누적될 때 "getOrDefault"로 에러 방지)
                carTime.put(car, carTime.getOrDefault(car, 0) + totalTime);
            }
        }

        // 입차 후 출차하지 않은 차량 관리
        for (int carNum : map.keySet()) {
            int totalTime = 0;
            String icTime = map.get(carNum);
            String[] ic = icTime.split(":"); // 입차시간
            int min = 59 - Integer.parseInt(ic[1]);
            int hour = 23 - Integer.parseInt(ic[0]);
            // 누적 주차 시간
            totalTime = hour * 60 + min;
            // 차량별 누적 요금 관리
            carTime.put(carNum, carTime.getOrDefault(carNum, 0) + totalTime);
        }

        int[] answer = new int[carTime.size()];
        int idx = 0;
        for (int time : carTime.values()) {
            answer[idx] = payFee(time);
            idx++;
        }

        return answer;
    }

    // 요금 계산
    public static int payFee (int time) {
        int totalFee = giFee;
        time -= giTime;
        if (time <= 0) return totalFee;

        if (time % danTime == 0) {
            totalFee += time/danTime*danFee;
        }
        else {
            totalFee += (time/danTime+1)*danFee;
        }
        return totalFee;
    }
}

어려웠던 점

TreeMap이라는걸 이 문제를 풀면서 처음 알았다. 오름차순으로 차량 정보를 조회해오는 방법을 생각해봤을 때, 처음에 1차원 배열을 9999까지 만들고 할까 생각했는데, 이는 메모리 낭비라는 생각이 들어 List로 관리할까하다가 이는 코드의 복잡성이 올라가 어떻게 해결하지 아이디어가 떠오르지 않았다.

이를 Gemini에게 물어보니 TreeMap이라는 자료구조를 알려줘서 이를 활용했다. 활용할 때, 핵심은 Map에 값을 집어넣을 때, 키 값이 없다면, getOrDefault로 누적 시간의 값을 0으로 지정해서 누적 시간 값을 value에 집어 넣는 것이었다.

그리고 시간을 올림해서 처리하는 것도 처음엔 if else문으로 처리했는데, 이를 더 간단히 해결하려고 Math.ceil을 사용했다.

근데, 그냥 ceil을 사용하니 올림이 적용이 안됐다. 이는 Java의 '/'연산은 몫만 남기므로 ceil을 한다고 한들 그냥 내림 계산이 되어버린다.

이를 해결하려면, 연산되는 값을 double로 지정해서 소숫점 값이 나오도록 해야했다. 이 부분을 놓쳐서 디버깅하는데 시간을 오래 썼다. 어찌보면 당연한건데, 아직 많이 공부해야하나보다.. 아래는 최종 제출한 코드를 조금 더 개선시킨 코드이다.

• Map의 자료형 변경 및 일부 계산식 단순화 (시간 계산, 요금 계산)

  ...
  class Solution {
    ...
    public int[] solution(int[] fees, String[] records) {
        ...
        // 입출차 관리 맵 (차 번호, 입차 시간)
        HashMap<String, Integer> map = new HashMap<>();
        // 차량별 누적 시간 관리 (차 번호, 누적 주차 시간)
        TreeMap<String, Integer> carTime = new TreeMap<>();
  
        for (String r : records) {
            ...
            // 절대 분 단위 환산
            String[] hhmm = time.split(":");
            int currentMin = Integer.parseInt(hhmm[0]) * 60 + Integer.parseInt(hhmm[1]); 
            // 입차
            if (ny.equals("IN")) {
                map.put(car, currentMin);
            }
            // 출차
            else {
                // 입차했던 시간 가져옴. 동시에 해당 차량 삭제
                int icTime = map.remove(car);
  
                // 누적 주차 시간
                int totalTime = currentMin - icTime;
                // 차에 시간을 누적함 (차량이 처음 누적될 때 "getOrDefault"로 에러 방지)
                carTime.put(car, carTime.getOrDefault(car, 0) + totalTime);
            }
        }
  
        // 입차 후 출차하지 않은 차량 관리
        for (String carNum : map.keySet()) {
            int icTime = map.get(carNum);
            // 누적 주차 시간
            int totalTime = 23*60+59 - icTime;
            // 차량별 누적 요금 관리
            carTime.put(carNum, carTime.getOrDefault(carNum, 0) + totalTime);
        } 
        ...
        return answer;
    }
  
    // 요금 계산
    public static int payFee (int time) {
        int totalFee = giFee;
        time -= giTime;
        if (time <= 0) return totalFee;
  
        // double로 해야 소수점이 생겨서 올림이 가능
        totalFee += Math.ceil((double)time/danTime)*danFee;
  
        return totalFee;
    }
  }

Programmers - 단속카메라

요약

모든 차를 단속할 수 있도록 설치하는 카메라의 최소 개수를 구하라

접근

처음에 문제를 봤을 때, 차량마다 출발 지점을 기준으로 정렬을 하고 각 차량마다 겹치는 구간에 카메라를 두면 되겠다고 생각했다.

그러고 문제의 TC를 이 논리로 푸니까 개수가 안맞았다.

20분 동안 어떻게 풀지 고민했는데 답이 안나와서 스터디를 같이 하는 친구가 푼 코드에 주석을 읽고 어느정도 접근 방식을 알고 접근했다.

그 접근 방식은 아래와 같다.

1. 정렬을 한다.
2. 자동차의 고속도로 나간 지점에 카메라를 세운다.
3. 새로 세운 카메라를 다음 차량이 잡을 수 있는지를 검사하며 새로운 카메라를 설치할지말지 결정한다.

알고리즘

1. 차량별 고속도로를 나간 시점을 기준으로 정렬한다.
2. 최초 카메라 설치를 첫번째 차량이 나간 시점으로 초기화한다.
3. 차량 전체를 순회하며 최근 설치된 카메라로 해당 차량을 탐지할 수 있는지 판단 3-1. 탐지할 수 없다면, 해당 차량의 탈출이 나가는 시점으로 최근 카메라 설치 위치를 이동 3-2. 카메라 개수 증가

제출 코드

import java.util.Arrays;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        int[] cameras = new int[routes.length];

        // 고속도로 탈출한 시점으로 정렬
        Arrays.sort(routes, (a, b) -> a[1] - b[1]);

        // 최근에 설치한 카메라 위치
        int newCam = routes[0][1]; // 기본 값으로 첫번째 차량의 고속도로 나간 지점을 잡음
        answer++; // 카메라 개수 1 증가

        for (int i = 1; i < routes.length; i++) {
            // 설치한 카메라가 다음 자동차의 출발지를 못잡는다면, 새로운 카메라 설치
            if (routes[i][0] > newCam) {
                newCam = routes[i][1];
                answer++;
            }
        }

        return answer;
    }
}

깨달은 점

Greedy라는걸 파악하기도 어렵고, 문제를 접근하는 아이디어조차 떠올리기 힘들었다. Greedy는 미래를 생각안하고, 그 순간순간 가장 좋아보이는 최적의 선택을 하는 알고리즘 설계 기법... 이걸 어떻게 아냐... 많이 접해봐야 이게 그리디 문제인지 알 것 같다.

Programmers - 섬 연결하기

요약

모든 섬을 연결할 수 있는 전체 간선의 최소 비용

접근

일단 섬들을 연결하는걸 보고 그래프 관련 문제라는 생각이 들었다.

• 처음에 접근한 방식

1. costs를 [0]과 [1]을 기준으로 정렬되도록 만듦
2. costs를 순회하며, 각 노드가 포함된 최소 비용이 드는 경로를 answer에 누적.
3. 방문한 섬들을 visited 처리

이 방식대로 문제를 푸니 전체 섬의 수를 n개라 했을 때, n-1을 순회해야하는데, n을 순회하는 문제가 있었다.

이때 문제 푸는 시간을 1시간 넘게 써서 AI의 도움을 받아 올바르게 접근하고 있는지 물어보니, 이 문제는 MST(최소 신장 트리)를 구현하는 문제였다.

• MST란? 가중치가 있는 그래프에서 모든 정점을 가장 작은 비용으로 연결하는 트리

알고리즘

MST를 구현하는 알고리즘은 총 2가지 방법이 있다.

1. 크루스칼 알고리즘 (Kruskal)

   : 가중치가 가장 작은 간선부터 순차적으로 탐색하며 하나의 그래프를 완성

2. 프림 알고리즘 (Prim)

   : 임의의 노드를 먼저 방문처리한 후 인접한 노드 중 비용이 낮은 간선을 찾아가며 하나의 그래프를 완성

나는 좀 더 직관적인 크루스칼 알고리즘을 선택해 풀었다.

크루스칼 알고리즘의 핵심 아이디어는 각 노드마다 최상단 조상 노드의 정보를 저장하고, 모든 노드의 최상단 조상 노드를 동일하게 만드는 것이다.

이를 위해서 가장 중요한 것은 Find와 Union이다. find : 현재 노드의 최상단 조상 노드를 찾는 것 union : 두 노드 그룹을 하나의 노드 그룹으로 합치는 것

find는 재귀로 구현하고, union은 노드 연결 정보를 순회하며 하나의 간선에 연결된 두 노드의 부모 노드가 다르다면 하나로 합치는게 핵심!

최종 코드

import java.util.Arrays;

class Solution {
    int[] lands;

    public int solution(int n, int[][] costs) {
        int answer = 0;

        // 각 노드의 부모 노드 저장
        lands = new int[n+1];
        for (int i = 0; i < lands.length; i++) {
            // 본인이 부모 노드가 되도록 초기화
            lands[i] = i;
        }

        // costs를 cost 기준으로 정렬
        Arrays.sort(costs, (a1, b1) -> a1[2] - b1[2]);

        // 2. 메인 로직에서의 Union-Find 적용
        for (int i = 0; i < costs.length; i++) {
            // 1. 각 시작노드와 끝 노드를 뽑는다.
            int start = costs[i][0];
            int end = costs[i][1];

            // 각 노드의 부모 노드가 동일한지 확인
            // 2-1. 부모 노드가 동일하다면 skip
            int rootStart = find(start);
            int rootEnd = find(end);
            if (rootStart == rootEnd) continue;
            // 2-2. 부모 노드가 다르다면 두 그룹을 하나로 묶는다.
            else {
                lands[rootEnd] = rootStart;

                answer += costs[i][2];
            }
        }

        return answer;
    }

    // 별도의 find 메서드를 만들어 '최종 대표'를 찾는 로직을 구현
    public int find(int land) {
        // 지금 섬이 최종 끝인지 확인
        if (lands[land] == land) {
            return land;
        }

        // 내가 최종 노드가 아니라면, 내 부모의 부모를 찾음
        return find(lands[land]);
    }
}

새로 배운 점

MST라는 걸 개념만 알고 있었는데, 실제로 구현하려니 너무 어려웠다. 크루스칼 알고리즘은 처음 듣고, 프림 알고리즘은 들어만 봤는데, 실제로 마주하니 어렵다.. 그래도 이렇게 기록해나가며 문제를 풀다보면 나중엔 쉽게 잘 풀지 않을까라는 생각 중이다.

• 처음에 접근한 방식으로 푼 코드

  import java.util.*;
  

class Solution { public int solution(int n, int[][] costs) { int answer = 0;

    // 이어진 섬들 저장
    boolean[] visited = new boolean[n];

    // costs를 cost 기준으로 정렬
    Arrays.sort(costs);

    for (int i = 0; i < n; i++) {
        int min = Integer.MAX_VALUE;
        for (int j = 0; j < costs.length; j++) {
            int start = costs[j][0];
            int end = costs[j][1];
            if (start == i || end == i) {
                // 같은 경우를 처리하는게 관건
                if (!(visited[start] && visited[end])) {
                    visited[start] = true;
                    visited[end] = true;
                    min = Math.min(min, costs[j][2]);
                    System.out.println(i + " = " +costs[j][0] + " | " +  costs[j][1] + " : " + min);   
                }
                // System.out.println(i + " = " +costs[j][0] + " | " +  costs[j][1] + " : " + min);
            }
        }
        answer += min;
    }

    return answer;
}

} ```

Programmers - 정수 삼각형

요약

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능할 때 거쳐간 숫자의 최댓값

접근

문제만 봤을 땐, DFS로 전부 다 탐색할 수 있겠다라는 생각을 했다. 제약 조건을 보니 N이 1~500까지였다. 이를 최악의 경우를 계산해보니 총 노드이 개수는 약 125,000개가 된다. 이를 DFS로 돌리기란 시간복잡도에서 무조건 문제가 생긴다.

문제를 다시 보니 DP 중 메모이제이션을 활용해 풀면 해결될 것 같다는 생각을 했고, 내가 생각한 알고리즘대로 풀어보니 답이 나왔다.

알고리즘

알고리즘 : DP (메모이제이션)

1. 위에서 아래로 내려간다 1번 인덱스부터 n번 인덱스까지
2. 0번 인덱스부터 i 인덱스까지 돌면서 값 업데이트
3. 가장 좌측이랑 우측이라면 각각 한번의 연산만 함
4. 모든 값을 업데이트한 뒤, 제일 바닥에서 값이 제일 큰걸 answer에 둔다

최종 코드

class Solution {
    int[][] triangle;

    public int solution(int[][] triangle) {
        int answer = 0;
        this.triangle = triangle;
        // 1. 위에서 아래로 내려간다 1번 인덱스부터 n번 인덱스까지
        int start = triangle[0][0];
        int len = triangle.length;

        for (int i = 1; i < len; i++) {
            // 2. 0번 인덱스부터 i 인덱스까지 돌면서 값 업데이트
            for (int j = 0; j <= i; j++) {
                // 3. 누적합 계산
                triangle[i][j] = memoization(i, j);
            }
        }

        // 4. 모든 값을 업데이트한 뒤, 제일 바닥에서 값이 제일 큰걸 answer에 둔다
        for (int i = 0; i < len; i++) {
            answer = Math.max(answer, triangle[len-1][i]);
        }

        return answer;
    }

    // h : 높이, w : 너비
    public int memoization(int h, int w) {
        int res = triangle[h][w];
        // 3-1. 가장 좌측 한번의 연산만 함
        if (w == 0) {
            res += triangle[h-1][0];
        }
        // 3-2. 우측이라면 한번의 연산만 함
        else if (h == w) {
            res += triangle[h-1][w-1];
        }
        // 3-3. 위의 두 경우가 아니라면 두 부모의 값 중 큰 것과 합한다.
        else {
            int num = Math.max(triangle[h-1][w-1], triangle[h-1][w]);
            res += num;
        }
        return res;
    }
}

깨달은 점

• DP(메모이제이션)을 개념으로만 알고 있었는데, 실제 문제를 만나고, 손으로 풀어보니 감을 잡았다.
• 이번 문제는 손으로 푼 풀이를 그대로 코드로 옮기는데 큰 어려움 없이 풀렸다. (나... 재능있나...?)
• 처음 문제를 볼 때, 알고리즘이 떠오르지 않으면 제약조건을 먼저 보자!!

프로그래머스 - 여행경로

요약

ICN부터 시작되는 전체 여행경로를 출력하라. 단, 2개 이상의 경로가 나오는 경우 알파벳 순서가 빠른 경로를 출력할 것

접근

무조건 "ICN"부터 시작하니까 ICN이 루트 노드가 되는 트리를 탐색하는 것으로 접근을 시작했다. 테스트 코드를 손으로 풀어봤을 때, 이미지와 같은 경로가 나올 수 있도록 구현한다고 생각을 하고, 이를 직접 알고리즘으로 구현했다.

알고리즘

1. 시작: "ICN" 출발 항공권을 찾아 방문 처리 후 DFS 탐색 시작

2. 조건 확인: DFS 내에서 현재 도시(nextCity)와 티켓의 출발지가 같은 미방문 티켓 탐색

3. DFS 진행: 일치하는 티켓을 방문 처리하고 경로(path)에 추가한 뒤, depth를 1 늘려 재귀 호출

4. 백트래킹: 끝까지 가지 못하고 막혔다면, 다른 길을 찾기 위해 방문 해제(visited=false) 및 현재 경로에서 제거

5. 종료 및 갱신: depth가 전체 티켓 수와 같아지면 완성된 경로 반환. 기존 정답이 존재한다면 알파벳 사전순 비교를 통해 조건에 맞는 답으로 갱신

최종 코드

import java.util.*;

class Solution {
    String[][] tickets;
    // 정답 배열
    String[] answer;
    // 총 티켓 개수
    int len;
    // 방문 여부 확인
    boolean[] visited;
    // 누적 경로 저장
    List<String> path;

    public String[] solution(String[][] tickets) {
        this.tickets = tickets;
        this.len = tickets.length;
        answer = new String[len+1];

        for (int i = 0; i < len; i++) {
            // 방문 배열 초기화
            this.visited = new boolean[len];
            // 누적 경로 초기화
            this.path = new ArrayList<>();
            if (tickets[i][0].equals("ICN")) {
                visited[i] = true;
                path.add(tickets[i][0]);
                path.add(tickets[i][1]);
                findPath(1, tickets[i][1]);
            }
        }

        return answer;
    }

    // 방문한 나라 수(depth)와 다음 도시를 매개변수(nextCity)로 받음
    public void findPath(int depth, String nextCity) {
        // 모든 배열 방문 시 종료
        if (depth >= len) {
            if (answer[0] == null) {
                answer = path.toArray(new String[0]);
            }
            // 알파벳 순서로 비교
            for (int i = 0; i < depth; i++) {
                // answer가 사전순으로 더 빠르다 (음수)
                if (answer[i].compareTo(path.get(i)) < 0) {
                    break;
                }
                // answer가 사전순으로 더 느리다 (양수)
                else if (answer[i].compareTo(path.get(i)) > 0) {
                    answer = path.toArray(new String[0]);
                    break;
                }
            }
            return;
        }

        for (int i = 0; i < len; i++) {
            if (!visited[i] && tickets[i][0].equals(nextCity)) {
                visited[i] = true;
                path.add(tickets[i][1]);
                findPath(depth+1, tickets[i][1]);
                // 가지치기로 다른 경우를 찾기 위해 방문 배열을 false로 처리
                visited[i] = false;
                // 추가한 경로 제거
                path.remove(path.size()-1);
            }
        }
        // 방문 가능한 배열 없을 시 종료
        return;
    }
}

어려웠던 점

• List 자료형을 배열로 바꾸는 코드가 자꾸 생각이 안난다... 직접 생각하는데 5분씩은 걸린다. 이를 외울 것! ➡️ list.toArray(new String[0])
• String[]을 new로 생성하면 null이 저장된다는걸 이제 처음 피부로 깨달음... 어쩐지 .eqauls("")로 하니까 자꾸 널포인터익셉션 터지더니... ➡️ String은 String Pool에서 관리하는게 아니면 객체로 생성되기 때문에 null로 초기화가 된다!
• dfs에서 visited를 false로 바꿨을 때, 지금 추가했던 path 경로도 제거해줘야한다! (백트래킹해야하니까 이전 상태로 돌려야 한다!)

프로그래머스 - 네트워크

요약

총 노드 개수가 n으로 주어지고, 노드들의 연결된 정보가 2차원 배열로 주어질 때, 연결될 수 있는 네트워크 집합들의 총 개수를 구해야한다!

접근

0번 노드부터 접근하면서 깊이 우선 탐색(DFS)를 돌리면서 방문한 노드들을 visited로 처리하면서 연결하면 되겠다!라는 생각을 가지고 접근

알고리즘

1. 주어지는 n과 computers 배열을 클래스변수로 빼고, 네트워크 개수를 저장할 변수도 클래스 변수로 지정한다.
2. visited 배열을 생성해 노드 방문 여부를 저장한다.
3. 0번 노드부터 차례로 방문하면서 방문한 node들을 visited = true로 저장한다.
4. 각 노드와 연결된 노드들을 다 방문할때까지 visited 여부를 확인하고 업데이트하는 것을 반복한다.

최종 코드

class Solution {
    int n;
    int[][] computers;
    int answer;
    boolean[] visited;

    public int solution(int n, int[][] computers) {
        this.n = n;
        this.computers = computers;

        visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            findNetwork(i, i);   
        }

        return answer;
    }

    public void findNetwork(int startNode, int node) {
        if (visited[node]) return;

        visited[node] = true;

        for (int i = 0; i < n; i++) {
            // 아직 방문하지 않았으면서 연결된 노드가 있는지 확인
            if (!visited[i] && computers[node][i] == 1) findNetwork(startNode, i);
        }

        if (startNode == node) {
            answer++;
        }
    }
}

어려웠던 점

visited 처리는 알겠는데, 언제 네트워크 개수를 증가시켜야할지 판단하는게 어려웠다. DFS 내부에서 answer 카운트를 올리면 재귀를 돌때마다 카운트가 될 것이기에 어떻게 해야할지 고민하다, 처음 시작 노드 정보를 재귀 함수의 input으로 넣고, 연결된 노드 탐색을 모두 끝낸 후 answer를 증가시키는 방식을 택했다. 그런데, 이 코드는 짠 내가 나중에 다시봐도 이해하기 어려운데, 다른 사람이 보면 더 이해하기 어려울 것 같고, for문이 2중으로 들어간다는 측면에서 다시 최적화된 코드를 짜야겠다는 생각이 들었다. 코드가 복잡해 보이는 이유는 answer가 증가되는 방식 때문이라는 생각이 든다. 그래서 아래와 같이 코드를 재구성했다.

최적화 코드

class Solution {
    ...

    public int solution(int n, int[][] computers) {
        ...

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // 최초로 노드를 탐색하기 시작할 때, 부모 노드로 삼고 네트워크 개수를 1 증가시킨다.
                answer++;
                findNetwork(i);   
            }
        }

        return answer;
    }

    // 재귀 함수 인자를 node만 받도록 수정
    public void findNetwork(int node) {
        ...
    }
}

Programmers - 타겟 넘버

숫자들이 담긴 배열이 주어지고, 숫자끼리 + 혹은 - 연산을 했을 때, 타겟 넘버가 나오는 경우의 총 횟수를 찾아야 한다!

접근

처음엔 문제를 봤을 때, 머릿속으로 모든 연산자 조합을 다 구해서 연산하면 되겠다라는 생각을 했는데, 코드를 짜려고 키보드에 손을 올린 순간 뭐부터 해야할지 생각이 안떠올랐다. 일단 DFS로 찾아야하는건 알았는데, 어떻게 코드를 짜야할지 감이 안와서 손으로 그림을 그려보니 구현 방향이 보였다. 이렇게 포화 이진트리라는게 눈에 보였고, 그러면 DFS를 +연산하는것과 -연산하는걸 분리해서 계산하면 되겠다라는 결론에 도달했다.

알고리즘

1. 숫자들이 담긴 배열과 타겟 넘버를 클래스 멤버로 선언
2. 루트 node를 기준으로 +연산을 하는 경우와 -연산을 하는 경우로 나눔
3. leaf node에 도달했다면 최종 합산 값을 타겟 넘버와 비교해 총 횟수를 1 증가시킴

최종 코드

class Solution {
    int[] numbers;
    int target;
    int answer;
    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;

        findTargetNumber(0, 0);

        return answer;
    }

    // DFS
    public void findTargetNumber(int depth, int sum) {
        if (depth == numbers.length) {
            if (sum == target) answer++;
            return;
        }

        // 해당 depth에서 값을 더하는 경우
        findTargetNumber(depth+1, sum+numbers[depth]);
        // 해당 depth에서 값을 빼는 경우
        findTargetNumber(depth+1, sum-numbers[depth]);
    }
}

깨달았던 점

처음으로 손으로 그림을 그려서 문제를 접근하고 생각한 접근법대로 코드를 짰을 때, 한번에 돌아가니까 신기했다. 문제를 보고 바로 키보드에 손이 올라가는게 아니라, 정답을 찾기 위한 알고리즘을 손으로 그려보고 전체 윤곽이 그려진 상태에서 코드를 쳐야한다는 것을 처음 깨달은 순간이었다. 쉬운 문제라 이렇게 손으로 그려서 풀었을지 모르지만, 앞으로 다른 문제들을 만났을 때도 그림으로 먼저 문제를 이해하고 풀어가는 방식으로 풀어봐야겠다. 추가로, 값이 변하지 않는 numbers와 target과 같은 변수는 클래스 변수로 빼서 재귀 함수의 인자를 줄이는 방식으로 코테 풀이 스타일을 일관화 해야겠다.

Programmers - 피로도

요약

초기 피로도가 있고, 각 던전마다 입장 가능한 최소 피로도와 던전 탐험 시 소모되는 피로도가 저장된 던전의 리스트가 입력으로 주어진다. 지금 가진 피로도로 갈 수 있는 총 던전의 개수를 구해야한다!

접근

던전을 방문하는 모든 경우의 수를 고려해서 들어갈 수 있는 던전의 개수를 세아려 그 중 최댓값을 뽑아야 한다. 따라서 완전탐색 알고리즘으로 구현해야했다. 완전탐색은 보통 BFS나 DFS로 구현하는데, 이 문제는 모든 경우의 수를 다 탐색해서 조합해 값을 비교할 수 있는 DFS 알고리즘 (재귀)을 선택했다.

알고리즘

1. 현재 피로도와 총 던전 정보를 입력으로 받는다
2. 방문 여부를 체크할 visited 배열을 만든다.
3. 첫번째 던전부터 마지막 던전까지 순차적으로 제일 처음으로 들어가고, 재귀를 통해 모든 조합을 탐색하도록 만든다. 3-1. 현재 조합의 총 던전 방문 횟수와 지금까지 방문한 최대 방문 던전 횟수의 대소비교 3-2. 해당 던전을 방문했는지 먼저 체크한다. 3-3. 현재 피로도가 가려는 던전의 최소 피로도와의 대소비교 3-4. 들어갈 수 있다면 방문 횟수를 증가시킴

최종 코드

import java.util.*;

class Solution {
    int answer = -1;
    public int solution(int k, int[][] dungeons) {

        // 현재 체력
        int hp = k;
        // 방문여부 체크
        boolean[] visited = new boolean[dungeons.length];

        // 모든 경우의 수 조회
        dfs(dungeons, visited, hp, 0);

        return answer;
    }

    // 완전탐색 (DFS)
    public void dfs(int[][] dungeons, boolean[] visited, int hp, int cnt) {
        answer = Math.max(answer, cnt);

        for (int i = 0; i < dungeons.length; i++) {
            if (!visited[i] && dungeons[i][0] <= hp) {
                visited[i] = true;
                dfs(dungeons, visited, hp - dungeons[i][1], cnt+1);
                visited[i] = false;
            }
        }
    }
}

// 알고리즘 : DFS
// 자료구조 : 배열
// 조건 : 지금의 체력이 던전 입장 가능한지

어려웠던 것

일단 먼저 재귀에 대한 개념이 내 머리에 명확히 남아있지 않다... hp를 다음 스탭 가기 전에 줄이고, cnt(던전 방문 횟수)를 증가시키고 재귀를 돌렸는데, 완탐이 안돼서 뭐지? 했는데 재귀를 돌리는 함수 호출 내부에서 값 증감을 시켜야 완탐이 가능하다는걸 Gemini의 도움을 통해 알게되었다... 근데 지금해보니, 상관없이 되는데, 이전에 내가 코드를 잘못 짰나보다...

지금의 코드 최적화

1. 재귀로 총 4개의 인자를 받는데, 고정된 값인 던전과 방문 배열을 클래스변수로 빼서 처리하면 코드가 깔끔할 것 (단, 실무에선 x)
2. 재귀를 도는데 이미 던전을 다 돌 수 있는 경우를 찾았다면 그 즉시 재귀 종료.

• 최적화한 코드

  import java.util.*;
  

class Solution { int answer = -1; int hp; // 현재 체력 boolean[] visited; // 방문 배열 int[][] dungeons; // 던전 배열 public int solution(int k, int[][] dungeons) {

    this.hp = k;
    visited = new boolean[dungeons.length];
    this.dungeons = dungeons; // 동일한 변수명이기에 this로 지정
    // 모든 경우의 수 조회
    dfs(hp, 0);

    return answer;
}

// 완전탐색 (DFS)
public void dfs(int hp, int cnt) {
    // 모든 던전을 다 도는 경우를 찾았다면 그 즉시 종료
    if (dungeons.length == answer) return;

    if (answer < cnt) {
        answer = cnt;
    }

    for (int i = 0; i < dungeons.length; i++) {
        if (!visited[i] && dungeons[i][0] <= hp) {
            visited[i] = true;
            // int currentHp = hp - dungeons[i][1];
            // int currentCnt = cnt+1;
            // dfs(currentHp, currentCnt);
            dfs(hp-dungeons[i][1], cnt+1);

            visited[i] = false;
        }
    }
}

} ```

SWEA-정사각형 방

요약

NxN의 배열이 있고 그 안엔 모두 다른 값의 숫자들이 배치되어있다. A요소가 상하좌우의 다른 요소와 비교했을 때, 주변에 1 큰 수가 있다면 그 요소와 길을 이을 수 있다. 배열에서 이을 수 있는 길의 최대 길이와 그때의 시작 요소의 값을 출력 (최대 길이의 길이 여러개인 경우 시작 요소의 값이 작은 것을 출력)

접근

이 문제를 처음 봤을 때, 전체 모든 요소를 탐색해야하고, 시작 요소와 그 길의 최종 길이를 저장해서 값들을 비교해나가면 되겠다!는 생각으로 접근했다.

내가 다시 푼 풀이의 알고리즘은 아래와 같다.

알고리즘

완전 탐색 (시뮬레이션)

1. 먼저 NxN의 배열 값들에 대한 iuput을 int형 2차원 배열에 저장
2. 상하좌우를 탐색할 수 있게 dr, dc 배열 생성
3. 배열의 요소들을 하나씩 선택해나가며 그 요소를 기준으로 주변 값들이 이어지는지 while 문으로 끝까지 탐색
4. 탐색이 끝나면 지금까지의 최대 길의 길이와 현재 요소에서 이을 수 있는 길의 길이의 값 비교해 최댓값 갱신
5. 모든 요소를 다 볼 때까지 반복

최종 코드

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

// 외길이니 BFS, DFS 쓰지 않는다. visited도 쓰지 않는다.
// 메모이제이션으로 이미 방문한 곳이라면 그 위치에서 갈 수 있는 거리만큼 cnt올린다.

class Solution {
    private static int[][] A;
    private static int N;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        for (int testCase = 1; testCase <= T; testCase++) {
            N = Integer.parseInt(br.readLine()); // 1 ~ 1000
            A = new int[N][N];

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

            // 최대 이동할 수 있는 방의 개수
            int maxCnt = 0;
            // 최대 이동 가능 칸의 시작값
            int idx = Integer.MAX_VALUE; // 최대 이동을 위해 출발할 방 위치 (숫자) (작은 수를 찾아야 한다)

            // 모든 정점에서 출발해 갈 수 있는 칸으로 탐색
            for (int r = 0; r < A.length; r++) {
                for (int c = 0; c < A.length; c++) {
                    int cnt = go(r, c); // (r,c)에서 출발해 이동 가능한 칸 수
                    if (maxCnt < cnt || (maxCnt == cnt && idx > A[r][c])) {
                        maxCnt = cnt;
                        idx = A[r][c];
                    }
                }
            }
            sb.append("#").append(testCase).append(" ").append(idx).append(" ").append(maxCnt).append("\n");
        } // end of tc
        System.out.print(sb.toString());
    } // end of main

    private static int[] dr = {-1, 1, 0, 0}; // 상하좌우
    private static int[] dc = {0, 0, -1, 1};

    /**
     * A[r][c]에서 출발해 최대 이동할 수 있는 방의 개수를 리턴
     * @param r
     * @param c
     * @return
     */
    private static int go(int r, int c) {
        int cnt = 1; // r, c에서 이동할 수 있는 방의 개수

        while(true) {
            int nextNum = A[r][c] + 1;
            boolean flag = false; // 다른 칸으로 이동했는지 확인하는 플래그

            // 현재칸(r,c)에서 인접 칸을 탐색하는데 그 칸에 갈 수 있는가(나보다 1큰가?) - 자주 나오니 코드블럭으로 외울 것
            for (int i = 0; i < dr.length; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];
                // 배열범위 내인지는 항상 체크!
                if (nr >= 0 && nc >= 0 && nr < N && nc < N && nextNum == A[nr][nc]) {
                    r = nr;
                    c = nc;
                    cnt++;
                    flag = true;
                    break; // 상하좌우에서 1큰 값이 있다면 다른 곳엔 같은 값이 없기에 멈춘다! (안해도 풀리긴 하지만, 시간 절약을 위해 붙이는게 필요)
                }
            }
            if (!flag) break;
        }

        return cnt;
    }
} // end of class

어려웠던 것

이 문제는 BFS, DFS 문제가 굳이 아니다! why? 외길이니까. 외길이 무엇이냐? 갈 수 있는 곳은 4방향 중 한 곳으로밖에 못간다. 배열 내에 중복되는 값이 없기 때문! 따라서 방문 여부(visited)도 탐색할 필요가 없고, 남은 가지를 탐색할 필요가 없다

BFS, DFS : 그래프에서 사용!

다른 접근법

수학적으로 접근할수도 있다. 배열의 모든 요소들은 모두 다 다른 값들을 가지고 있고, 1씩 차이가 나기 때문에 아래의 그림과 같이 접근이 가능하다.

[배열]

이때 요소의 길이는 다음 요소의 행과 열을 각각 비교해서 둘의 차의 합이 1이라면 연속된 것으로 볼 수 있음!!

백엔드 개발의 핵심은 데이터를 어떻게 안전하게 저장하고, 효율적으로 처리하여, 사용자에게 전달할 것인가 에 있습니다. 다른 백엔드 개발 프레임워크들(Django, Node.js)등도 있지만, Spring Boot가 채택이 되는 이유는 대규모 엔터프라이즈 환경에서의 확실한 안정성과 정형화된 규칙, 예외처리, 인증 및 인가에서 강력한 기능을 제공하기 때문입니다. 따라서 여러 사람이 동일한 프로젝트를 개발하여도 일률적인 규칙에 의해 개발이 가능하고 안정적인 서비스 제공이 가능합니다.

1️⃣ 견고한 기초: 객체지향과 설계 원칙 (Java OOP & SOLID)

Spring Boot에 대해 알아보기 전, Spring Boot의 근간이 되는 언어인 Java의 중요 개념에 대해 알아보고자 합니다. Java는 객체지향 언어로 그 특징으로 캡슐화, 추상화, 다형성, 상속을 가집니다.

• 캡슐화 : 객체 외부에서 내부에 어떤 필드를 가지고 있는지 알지 못하게 하는 것입니다.
• 추상화: 메서드의 동작을 선언하지 않고 메서드명만 선언할 수 있는 것입니다.
• 다형성: 같은 메서드명을 가졌지만, 다양한 동작을 하는 메서드를 가질 수 있는 것입니다.
• 상속: 자식 객체는 부모 객체의 필드 및 메서드를 가질 수 있는 것입니다.

캡슐화는 접근 제어자, 추상화는 abstract class, interface, 다형성은 method overriding, method overloading, 상속은 extends를 이용해 구현합니다.

다음으로 객체지향의 5대 원칙인 SOLID 원칙입니다.

• SRP (단일 책임 원칙) : 하나의 클래스는 하나의 책임만을 가져야 한다.
• OCP (개방 폐쇄 원칙) : 클래스는 확장에는 열려 있고, 수정에는 닫혀 있어야 한다.
• LSP (리스코프 치환 원칙) : 부모 클래스를 자식 클래스가 대체할 수 있어야 한다.
• ISP (인터페이스 치환 원칙) : 하나의 범용적 인터페이스가 아닌 여러 개의 인터페이스로 구현해야 한다.
• DIP (의존 역전 원칙) : 고수준 모듈은 저수준 모듈에 의존하면 안된다. (상위 모듈은 하위 모듈이 아닌 인터페이스에 의존해야 한다.)

결국 Spring Boot는 위와 같은 Java의 객체 지향 특징과 원칙에 따라 구현되어야 합니다.

2️⃣ 생산성의 혁신: Spring Boot 아키텍처 (Core & Container)

Spring Boot를 공부하기 전 Spring Boot의 전신인 Spring과 어떤 차이점이 있는지 알아보고자 합니다. Spring은 동일하게 백엔드 개발에 사용되던 Java 기반 프레임워크입니다. 하지만, 이를 사용하기 위해선 개발에 사용되던 시간보다 설정(환경, 의존성, 서버 실행 등)에 사용되는 시간이 많았습니다.. 이 점 때문에 백엔드 개발의 강력한 프레임워크이지만 사용에 어려움이 있었고, 이를 해결하기 위해 탄생한 것이 Spring Boot입니다.

• “설정하는 시간을 줄이고, 개발에 할애하는 시간을 늘이자!”

Spring Framework의 복잡한 설정을 Spring Boot는 IoC와 DI, Bean을 통해 자동화합니다.

IoC는 제어의 역전으로 객체의 생성, 생명 주기 관리, 의존성 주입 등을 개발자가 아닌 Spring 컨테이너가 관리하도록 위임하는 것을 의미합니다. 따라서 코드의 결합도를 낮추고, 유연한 아키텍처와 테스트 가능한 구조로 만들 수 있습니다.

이처럼 컨테이너가 외부에서 객체를 관리해주기 때문에 개발자는 특정 기술이나 프레임워크에 종속되지 않은 순수한 자바 객체(POJO (Plain Old Java Object))만으로 비즈니스 로직을 구현할 수 있습니다. 이를 통해 객체지향 원리에 충실한 설계를 가능하게 하며, 단위 테스트를 더욱 용이하게 만듭니다.

의존성 주입(DI)은 이렇게 관리되는 POJO 객체들이 의존하는 다른 객체를 직접 생성하는 것이 아닌 Spring 컨테이너에서 주입받는 방식을 말합니다. Spring에서는 생성자 주입을 사용해 불변성을 보장하고 순환 참조를 방지하는 것이 권장됩니다.

생성자 주입 방식이 권장되는 이유는 주입 받을 객체를 final로 선언해 불변성을 보장하고, 의존성 주입을 하지 않거나 순환 참조가 발생했을 시, 컴파일 타임에 이를 확인하고 수정이 가능합니다. 또한, 한눈에 파악하기 용이합니다.

DI가 적용되는 흐름은 다음 사진과 같습니다. Spring Boot는 객체를 Bean으로 등록하여 객체를 생성하고 삭제합니다. 객체 생성 후 @PostConstruct로 초기화하고, 소멸 전 @PreDestroy로 리소스를 정리합니다. 이렇게 Bean으로 등록해 객체의 생성과 삭제를 맡기는 이유는 개발자가 객체를 생성한 후 삭제하는 로직을 작성하지 않았을 시, 메모리 누수가 발생하여 서비스 중단되는 일이 발생할 수 있는데 이를 미연에 방지하기 위해 Spring Boot는 IoC를 통해 개발자가 아닌 프레임워크에 이 일을 위임합니다.

Bean 생명 주기 흐름은 아래와 같습니다.

Spring Boot에선 서비스의 환경(Configuration)을 application.yml 파일을 이용해 설정하는데 동일한 서비스를 여러 환경에서 구동할 수 있도록 Spring Boot는 Profile 기능을 제공합니다. 이를 통해 개발 환경, 테스트 환경, 운영 환경을 코드 변경없이 전환할 수 있습니다.

이는 application-dev.yml, application-test.yml, application-prod.yml 과 같이 환경 설정 파일을 생성하고 각각의 운영환경을 활용해 구동할 수 있는 쉘 스크립트를 짠다면, Profile 기능을 활용해 환경 전환이 가능합니다.

3️⃣ 웹 서비스의 표준: REST API와 MVC (Web Layer)

Spring Boot는 요청을 중앙에서 처리하는 Dispatcher Servlet을 중심으로 Controller(요청 처리), Service(비즈니스 로직), Repository(DB 접근)로 역할을 분리해 유지보수성을 높입니다. 이러한 MVC 패턴은 데이터 처리, 화면 처리, 제어 로직을 분리하는 것이 목적입니다.

Controller는 사용자 요청의 입구로 파라미터를 받고 비즈니스 로직을 호출한 뒤 결과를 반환합니다.

Model은 Controller가 로직 수행 결과를 View에 전달할 때 사용하는 데이터 저장소입니다.

View는 사용자에게 보여줄 최종 화면(HTML, JSON 등)을 처리합니다.

계층 간의 분리를 통해 각 컴포넌트는 맡은 역할에 집중하는데 Service는 실질적 비즈니스 로직을 수행하고 Repository는 DB(데이터 저장소)에 접근하는 통로, 이후 설명할 Mapper는 자바 객체와 SQL 쿼리를 연결하는 역할을 수행합니다.

이렇게 분리된 구조를 기반으로 웹 요청을 처리하고, 데이터를 전달하며 화면을 렌더링합니다.

Spring MVC 요청 흐름은 아래와 같습니다.

웹 어플리케이션 개발을 위해선 먼저 Spring Boot의 의존성에 spring-boot-starter-web을 추가해야합니다. spring-boot-starter-web은 웹 어플리케이션에 필요한 모든 라이브러리를 한 번에 포함하는 starter로 내장 서버인 Tomcat을 포함해 프론트엔드와의 소통을 위한 RESTful API, 웹 MVC, JSON, 예외 처리, 로깅 등을 지원합니다.

Spring Boot에서 처리된 자원들을 프론트엔드에 서빙하기 위해서 일종의 규약이 필요한데 그것이 RESTful API 입니다. RESTful API는 자원을 명사(URI)로 행위를 HTTP 메서드(GET, POST 등)로 표현하는 아키텍처 스타일입니다.

GET은 조회, POST는 생성, PUT은 전체 수정, PATCH는 부분 수정, DELECT는 삭제를 의미합니다. 이렇게 표현된 규약에 따라 API를 사용하여 프론트엔드와의 통신을 하고 의미를 명확하게 전달합니다.

프론트엔드와의 원활한 통신을 위해 주로 JSON 포맷을 사용합니다. Spring Boot에서 처리한 자원을 Controller에서 @RestController 어노테이션을 이용하면 자원을 XML또는 JSON 형식으로 전달합니다.

이렇게 서빙된 API를 프론트엔드 측에서 쉽게 확인하고 테스트할 수 있도록 돕는 도구를 OAS(OpenAPI Specification)이라고 합니다. 현업에서 많이 사용되는 것은 Swagger로 Spring Boot의 springdoc-openapi 의존성을 활용해 코드로부터 API 명세서(Swagger UI)를 자동 생성해 프론트엔드와 효율적으로 협업합니다.

4️⃣ 데이터 중심 개발: JPA와 트랜잭션 (Persistence Layer)

기존의 Java를 이용한 개발에서는 Java에서 SQL을 직접 실행하여 DB와 연동하는 방식인 JDBC를 이용해 개발했습니다. JdbcTemplate 또는 MyBatis를 이용해 SQL을 직접 작성하고 모든 쿼리를 직접 작성해야했으나 이 어려움을 JPA (Java Persistence API)라는 새로운 기술을 통해 단순화하였습니다. JPA는 SQL을 직접 작성하는 JDBC 방식에서 벗어나, 객체 중심으로 데이터를 다룹니다.

JPA (ORM, Object-Relational Mapping)를 이용해 Java 객체와 DB 테이블을 매핑합니다. @Entity, @Id, @Column 등의 어노테이션으로 스키마를 정의하고, JpaRepository 인터페이스를 통해 기본적으로 CRUD를 자동합니다.

spring-boot-starter-data-jpa 의존성을 gradle 파일에 추가하고 JPA 및 DB 연결 정보를 application.yml 파일에 작성해 사용합니다.

JPA는 Spring Data JPA가 제공하는 인터페이스인 JPA Repository를 이용해 id를 이용한 데이터 추출(findById), 모든 데이터 조회(findAll) 등의 데이터베이스 조작이 가능합니다. 기본 제공되는 메서드 이외의 개발자가 메서드 키워드를 이용해 원하는 데이터를 가지고오는 메서드를 생성할 수 있습니다.

By(뒤에 오는 조건 필드 지정), And/Or(조건 연결), Like(SQL의 like와 동일한 기능)등의 메서드 키워드를 메서드에 작성하면 해당 동작을 하는 쿼리문이 자동 적용됩니다. 복잡한 조건 또는 특정 데이터 형태의 조회가 필요하다면 @Query 어노테이션을 통해 JPQL 또는 Native SQL을 이용한 쿼리문 작성도 가능합니다. 하지만 더 나아가 복잡한 동적 쿼리나 타입 안정성이 필요할 때는 자바 코드로 쿼리를 짜는 QueryDSL을 도입하는 것이 일반적입니다.

@Query 어노테이션을 사용하면 직접 쿼리문을 작성할 수 있어 편리하지만, 쿼리가 문자열 형태이기 떄문에 오타가 발생해도 컴파일 시점에 잡아내기 어렵다는 단점이 있습니다. 이를 해결하기 위해 QueryDSL을 함께 사용합니다.

즉, 간단한 조회는 메서드 이름 규칙으로 해결하고, 복잡한 동적 쿼리는 QueryDSL을 사용해 타입 안정성을 확보합니다.

JPA는 자동으로 트랜잭션을 관리해줍니다. 서비스 계층에서 @Transactional 어노테이션을 통해 데이터 정합성을 보장합니다. 예외 발생 시 자동으로 롤백(Rollback)되며, 서비스 계층에서 트랜잭션의 범위를 설정하는 것이 중요합니다. JPA에서 트랜잭션이 커밋되는 시점은 기본적으로 트랜잭션을 시작한 메서드가 성공적으로 종료될 때입니다.

트랜잭션이 시작되면 JPA는 영속성 컨텍스트라는 논리적 영역을 생성하고 엔티티는 해당 영역에, SQL은 쓰기 지연 SQL 저장소에 저장됩니다. 트랜잭션이 종료될 때, 영속성 컨텍스트의 변경 내용을 데이터베이스에 동기화(Flush)하고 쓰기 지연 저장소의 내용을 불러와 SQL을 실행합니다.

5️⃣ REST API 보안과 인증: JWT (JSON Web Token)

기존의 세션 기반 인증 방식은 서버 메모리에 사용자 상태를 저장해야 하므로 사용자가 늘어날수록 서버에 부담이 가고, 여러 대의 서버를 운영할 때 세션을 공유하기 까다롭다는 단점이 있습니다. 이를 해결하기 위해 토큰 기반 인증 방식인 JWT를 도입해 확장성을 확보합니다.

JWT는 인증에 필요한 정보들을 JSON 객체에 담아 암호화한 후, 이를 클라이언트에게 전달하는 토큰입니다. 서버는 사용자의 인증 상태를 저장하지 않고(Stateless) 클라이언트가 요청을 보낼 때마다 토큰을 함께 전달하면 서버는 토큰의 유효성만 검증하기에 서버 확장 시, 매우 유리합니다. 또한 토큰 자체에 사용자 식별 정보나 권한 등 필요한 데이터가 포함되어 있어 별도의 데이터 조회가 줄어듭니다.

JWT는 .을 구분자로 사용해 세 부분으로 구성됩니다.

Header에는 토큰의 타입(JWT)과 사용된 암호화 알고리즘 정보(HS256, RS256 등)가 담깁니다.

Payload에는 실제 전달할 사용자 정보인 Claims가 담겨있고 이 안에는 사용자 ID, 토큰 만료 시간 등을 포함합니다. Payload를 수정하더라도 서버의 Secret Key가 없으면 올바른 서명을 생성할 수 없기에 보안은 유지되지만, Payload는 암호화가 아닌 인코딩된 정보이기에 누구나 정보를 볼 수 있습니다. 따라서 비밀번호와 같은 민감 정보는 절대 담지 않도록 주의가 필요합니다.

마지막으로 Signature엔 헤더와 페이로드를 합친 후 서버만이 가진 Secret Key로 암호화한 값입니다. 이를 통해 토큰이 중간에 변조되지 않았음을 증명합니다.

동작 방식은 클라이언트가 로그인을 성공하면 서버는 JWT를 생성해 응답합니다. 이후 클라이언트는 HTTP 요청 헤더에 해당 토큰을 실어 보내고, 서버는 Secret Key를 이용해 서명을 검증하는 과정을 통해 사용자를 인증합니다.

참고) CORS(Cross-Origin Resource Sharing) 웹 브라우저는 보안 상의 이유로 다른 Origin의 리소스 요청을 기본적으로 차단하는데 프론트엔드와의 연결을 위해 서버 측에서 이를 풀어줘야합니다. 이때 사용하는 것이 CORS로 서버가 ‘내 자원을 특정 외부 도메인에서 접근해도 된다’고 허용해주는 것입니다.

6️⃣ 안정성과 운영: 횡단 관심사와 모니터링 (Aspects & Ops)

Spring boot에선 비즈니스 로직 외의 공통 관심사를 분리하고 시스템 상태를 진단합니다.

AOP (관점 지향 프로그래밍)를 이용해 로깅, 보안, 트랜잭션 등 반복되는 코드 즉, 공통 관심사를 Aspect로 모듈화하여 핵심 로직과 분리합니다. 이는 핵심 비즈니스 로직을 오염시키지 않으면서도 시스템 전반에 일관된 운영 정책을 적용할 수 있게 합니다.

OOP는 ‘기능’ 단위로 클래스를 구현한다면, AOP는 ‘공통 관심사(Aspect)’를 모듈화해 코드 중복을 줄이고 유지보수가 쉽도록 구현합니다.

이는 별도의 설정 없이 spring-boot-starter-aop 의존성만 추가한다면 바로 사용 가능합니다. 이때 제공되는 어노테이션은 @Aspect, @Advice, @JoinPoint, @Pointcut 등이 있습니다.

서버 운영 측면에서 사용자가 잘못된 값을 입력하지 않도록 사용자의 입력값 검증 또한 중요합니다. 검증 과정 없이 잘못된 데이터가 시스템으로 들어오면, 예기치 못한 오류나 데이터베이스에 원치 않는 값이 저장될 수 있기 때문입니다. 이를 위해 자바 표준 어노테이션인 @Valid 또는 Spring이 제공하는 @Validation 어노테이션을 사용합니다.

참고) @Valid는 일반적인 간단한 객체 검증에 사용되고, @Validation은 그룹을 지정해 상황별로 다르게 검증할 때 사용합니다.

@NotNull, @NotBlank, @Max, @Email 등을 사용하여 입력값 검증 로직을 DTO에 선언적으로 적용하고, 잘못된 데이터 유입을 @Valid를 이용해 컨트롤러단에서 즉시 차단합니다. 검증에 실패하면 서버는 400 Bad Request를 클라이언트에게 반환합니다.

Service 계층이 아닌 Controller에서 검증하는 이유는 Service에서 데이터를 처리하기 전 잘못된 데이터를 가능한 한 시스템의 가장 바깥쪽에서 처리하기 위해 Controller에서 받자마자 검증을 거칩니다. 또한 전역적 예외 처리를 통해 일관된 형식의 응답을 클라이언트에게 보내주기 용이하기 때문입니다.

Spring Boot는 예외 처리 설정을 하지 않았을 때 자동으로 BasicErrorController를 사용해 예외를 자동으로 처리합니다. 이때의 예외 처리를 사용자가 보기 편하도록 개발자가 커스텀할 수 있습니다.

@ControllerAdvice를 사용하여 예외 처리를 전역적으로 중앙화하고, @ExceptionHandler를 이용해 클라이언트에게 일관된 에러 응답을 제공합니다.

예외 처리의 우선순위는 컨트롤러 내의 @ExceptionHandler, @ControllerAdvice 내의 @ExceptionHandler, ResponseStatusException, 스프링 부트의 기본 예외 처리 순으로 처리됩니다.

Spring Boot는 애플리케이션의 상태 확인, 시스템 모니터링, 관리, 운영 자동화 등(서비스가 잘 돌아가고 있는가를 확인)을 위한 운영용 엔드 포인트를 Actuator라는 모듈로 제공합니다.

application.yml 파일에서 설정을 통해 /actuator/health, /actuator/metrics 등의 엔드포인트를 통해 애플리케이션의 운영 상태를 실시간으로 모니터링합니다.

뿐만 아니라, Spring Boot에서는 강력한 로깅 기능도 제공합니다. 애플리케이션 로그 관리가 중요한 이유는 문제 진단 및 원인 분석에 용이하고, 시스템 모니터링 및 운영 효율화 측면에서 반드시 필요합니다. Spring Boot는 로그 시스템을 자동으로 구성해줘 초기 설정만 한다면 바로 로그 관리가 가능합니다.

SLF4J는 자바 생태계에서 가장 널리 사용되는 로그 파사드(Facade) 라이브러리입니다. 직접 로그를 기록하지 않고 내부적으로 실제 로깅 구현체에 위임하는 방식을 취하고 있습니다.

여기서 로그 파사드란 여러 로깅 프레임워크를 일관된 API로 감싸서 사용할 수 있게 해주는 중간 계층을 의미합니다. 만약 Logback이라는 로그 파사드를 사용하다가 Log4j로 변경하고자 할 때, 코드 변경 없이 build.gradle 또는 pom.xml에서 의존성만 교체한다면 변경 가능합니다.

결론

지금까지 살펴본 백엔드 개발의 흐름은 단순한 코드 작성을 넘어, 객체지향 원칙이라는 단단한 기초 위에 Spring Boot라는 효율적인 도구를 얹고, JPA와 JWT, AOP와 같은 현대적인 기술 스택을 조화롭게 결합하는 과정입니다.

결국 백엔드 개발자에게 요구되는 역량은 특정 기술의 단순한 사용법 숙지가 아니라, "왜 이 기술이 도입되었는가?" 에 대한 본질적인 이해를 바탕으로 최적의 아키텍처를 설계하는 능력입니다. 이 글에서 다룬 핵심 개념들은 견고하고 확장 가능한 서비스를 구축하기 위한 든든한 이정표가 되어줄 것입니다.