다메카솔

🔍문제

https://www.acmicpc.net/problem/1253
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.

🤔발상

두 수의 합을 구하는 문제는 정렬된 배열일 경우, 양 끝에 포인터 지정하고, 포인터를 움직이면서 원하는 값보다 큰지 작은지를 판단하면서 포인터를 이동하는 투 포인터 알고리즘으로 해결할 수 있습니다.

🔦입출력

N의 수는 2천개이며, N의 값은 10억이므로 두 수의 합은 INT 범위 이내고 투포인터로 탐색할 때 오래걸리지 않는 수입니다. O(N)

📃의사코드

    1. 숫자들을 오름차순으로 정렬한다.
    2. 각 수마다 투포인터로 해당 수를 만들 수 있는지 확인
    3. 만들 수 있다면 카운트를 증가시킨다.

👨‍💻코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n];
            Arrays.sort(arr);

            String[] sarr = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(sarr[i]);
            }


            int count = 0;
            for (int i = 0; i < n; i++) {
                int start = 0;
                int end = n - 1;
                while (start < end) {
                    if (start == i) {
                        start++;
                        continue;
                    }
                    if (end == i) {
                        end--;
                        continue;
                    }
                    int sum = arr[start] + arr[end];
                    if (sum == arr[i]) {
                        count++;
                        break;
                    } else if (sum < arr[i]) {
                        start++;
                    } else {
                        end--;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

🚀TIL

• - 투포인터 알고리즘을 알고있다면 쉽게 해결할 수 있는 문제입니다.
• 삼중 포인터 문제도 예전에 리트코드에서 풀어본 기억이 있는데, 재귀형식으로 포인터 하나를 고정한 뒤에, 다시 자신을 호출하여 2가지 변수를 선택하는 알고리즘이었습니다. 복습을 해두면 좋을 것 같습니다.

🔍문제

https://www.acmicpc.net/problem/4485
젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. \[0]\[0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 \[N-1]\[N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

🤔발상

0,0에서 n-1,n-1까지  최단거리를 탐색하는 문제입니다.
한 지점에서 다른 지점까지의 최단거리에서 다익스트라 알고리즘을 사용할 수 있을 것 같습니다.
또한 좌표 이동 시 1칸씩 이동 가능하다는 점에서 bfs탐색에 적합할 것으로 보입니다.

🔦입출력

동굴의 크기는 2~125이며 루피는 0~9 범위입니다.

📃의사코드

- 데이터 입력받기
- bfs탐색
- 결과 출력

👨‍💻코드

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

/*
입력
동굴의 크기 정수 Number(2~125)
N줄 - 도둑 루피의 크기(0~9)
출력
가장 작은 최소 금액(최단 거리)
설계
2차원 배열을 0,0에서 n-1,n-1까지 최단 거리로 갈 때의 비용을 측정
상하좌우 1칸 이동 가능
dfs 탐색으로 누적 거리를 파라미터로 넘기며, 종료 지점의 값을 반환해서 최소값 찾기
*/

// The main method must be in a class named "Main".
public class Main {
    public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            StringBuilder sb = new StringBuilder();
            String problem = "Problem";

            int n = Integer.parseInt(br.readLine());
            int tc = 0;
            while (n != 0) {
                tc++;
                Map map = new Map(n);
                map.init(br);
                sb.append(problem).append(" ").append(tc).append(": ").append(map.getResult()).append("\n");
                n = Integer.parseInt(br.readLine());
            }
            bw.write(sb.toString());
        }
    }
}

class Map {

    private int[][] map;
    private int minResult;
    private int[][] dirs = {{0, 1}, {1, 0},{0, -1}, {-1, 0}};

    Map(int n) {
        map = new int[n][n];
    }

    public void init(BufferedReader br) throws IOException {
        int n = map.length;
        minResult = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
    }

    public int getStart(){
        return map[0][0];
    }

    public void dfs(int x, int y, int sum, boolean[][] visited) {
        visited[y][x] = true;
        int n = map.length;
        if (x == n - 1 && y == n - 1) {
            minResult = Math.min(minResult, sum);
            visited[y][x] = false;
            return;
        }
        for (int[] dir : dirs) {
            int nx = x + dir[0];
            int ny = y + dir[1];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) {
                continue;
            }
            if (!visited[ny][nx]) {
                dfs(nx, ny, sum + map[ny][nx], visited);
            }
        }
        visited[y][x] = false;
    }

    public int getResult() {
        return bfs();
    }
    private int bfs() {
        int n = map.length;
        int[][] minCost = new int[n][n];
        for (int[] row : minCost) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        minCost[0][0] = map[0][0];
        Queue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(0, 0, map[0][0]));

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            int x = current.x;
            int y = current.y;
            int cost = current.cost;

            if (x == n - 1 && y == n - 1) {
                return cost;
            }

            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                    int newCost = cost + map[ny][nx];
                    if (newCost < minCost[ny][nx]) {
                        minCost[ny][nx] = newCost;
                        queue.offer(new Node(nx, ny, newCost));
                    }
                }
            }
        }
        return -1;
    }
}

class Node implements Comparable<Node> {
    int x, y, cost;

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

    @Override
    public int compareTo(Node other) {
        return this.cost - other.cost;
    }
}

🔍문제

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

1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.

1번 학생의 키 < 5번 학생의 키
3번 학생의 키 < 4번 학생의 키
5번 학생의 키 < 4번 학생의 키
4번 학생의 키 < 2번 학생의 키
4번 학생의 키 < 6번 학생의 키
5번 학생의 키 < 2번 학생의 키
이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에서 b로 화살표를 그려서 표현하였다.



1번은 5번보다 키가 작고, 5번은 4번보다 작기 때문에, 1번은 4번보다 작게 된다. 그러면 1번, 3번, 5번은 모두 4번보다 작게 된다. 또한 4번은 2번과 6번보다 작기 때문에, 4번 학생은 자기보다 작은 학생이 3명이 있고, 자기보다 큰 학생이 2명이 있게 되어 자신의 키가 몇 번째인지 정확히 알 수 있다. 그러나 4번을 제외한 학생들은 자신의 키가 몇 번째인지 알 수 없다.

학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.

🤔발상

자신의 키가 몇 번째인지 알 수 있는 학생이 누군지 고민을 했습니다.
문제에서 이미지로 주어진 그래프를 관찰하다보니, 한 학생이 다른 학생과 모든 학생과 직,간접적으로 연결 관계가 존재하면 자신의 키가 몇 번째 인지 알 수 있다고 보았고, 플로이드 워셜 알고리즘을 이용하여 연결 관계를 파악하고, 이 숫자를 세어 전체 인원수와 비교하면 될 것으로 보았습니다.

🔦입출력

다행이 학생 수가 500 이하로, 만약 10,000등 수가 많았으면 다른 그래프 탐색방법을 고민해보았어야 할 것 같은데 플로이드 워셜을 사용할 수 있을 것 같습니다.

📃의사코드

- 데이터 입력받기
- 플로이드 워셜 이용하여 연결관계 업데이트
- 각 학생의 연결된 인원 수 세기
- 모든 학생과 연결된 학생의 수 세기

👨‍💻코드

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

public class Main {
public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            String[] nm = br.readLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            HeightUtil heightUtil = new HeightUtil(n, m);
            heightUtil.init(br);
            bw.write(String.valueOf(heightUtil.getResult()));
        }
    }
}

class HeightUtil {

    boolean[][] graph;
    int[] dist;
    int n;
    int m;

    public HeightUtil(int n, int m) {
        this.n = n;
        this.m = m;
        graph = new boolean[n + 1][n + 1];
        dist = new int[n + 1];
    }

    public void setGraph(int a, int b) {
        graph[a][b] = true;
    }

    public void floydWarshall() {
        for (int k = 1; k <= n; ++k) {
            for (int j = 1; j <= n; ++j) {
                for (int i = 1; i <= n; ++i) {
                    if (graph[i][k] && graph[k][j]) {
                        graph[i][j] = true;
                    }
                }
            }
        }
    }

    public void setDist() {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] || graph[j][i]) {
                    dist[i]++;
                }
            }
        }
    }

    public int getResult() {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == n - 1) {
                result++;
            }
        }
        return result;
    }

    public void init(BufferedReader br) throws IOException {
        for (int i = 0; i < m; i++) {
            String[] ab = br.readLine().split(" ");
            int a = Integer.parseInt(ab[0]);
            int b = Integer.parseInt(ab[1]);
            setGraph(a, b);
        }
        floydWarshall();
        setDist();
    }
}

🚀TIL

• 다른 탐색 방법도 한번 고민해보고 구현해보면 좋을 것 같습니다.

🔍문제

https://www.acmicpc.net/problem/2457
오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 
N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

🤔발상

꽃들을 시작 날짜와 종료 날짜로 정렬한 뒤에, 앞에서부터 조건에 맞는지 검사하면서 가장 종료 날짜가 긴 꽃을 선택하면 될 것 같았습니다.
주 키워드는 정렬과 그리디 알고리즘으로 보입니다.

🔦입출력

입력
꽃들의 총 개수 N(1~100,000)
꽃이 피는 날짜와 지는 날짜 x N
출력:  
선택한 꽃들의 최소 개수

📃의사코드

- 입력받은 꽃들을 정렬 가능한 클래스로 생성하여 배열에 담기
- 배열 정렬
- 시작날짜, 종료날짜 기준점 생성
- 시작날짜가 종료날짜 이전 동안 반복
	- 꽃들 배열 탐색
		- 탐색 대상의 시작날짜가 현재 시작날짜보다 늦으면 안됨
		- 탐색 대상의 종료날짜가 현재까지 찾은 마지막 날짜보다 뒤라면
			- 마지막날짜 업데이트
			- 인덱스 업데이트
			- 찾음 플래그 on

👨‍💻코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.time.LocalDate;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

public static void main(String args[]) throws NumberFormatException, IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int n = Integer.parseInt(br.readLine());
            Flower[] flowers = new Flower[n];
            for (int i = 0; i < n; i++) {
                flowers[i] = new Flower(br.readLine());
            }
            Arrays.sort(flowers);
            final int BASE_YEAR = 2023;
            LocalDate start = LocalDate.of(BASE_YEAR, 3, 1);
            LocalDate end = LocalDate.of(BASE_YEAR, 12, 1);

            int count = 0;
            int idx = 0;
            LocalDate maxEnd = start;

            //1. [x]시작날짜, 종료날짜 비교
            //2. [x]선택한 값이 종료날짜 이전인 동안 반복
            //3. [x]탐색 대상의 시작일이 이전 꽃의 이전 꽃의 종료일보다 이후이면 선택 안함
            //4. [x]탐색 대상의 기간이 이전 최대값보다 크면 선택
            while (start.isBefore(end)) {
                boolean find = false;
                for (int i = idx; i < n; i++) {
                    if (flowers[i].getStart().isAfter(start)) {
                        break;
                    }
                    if (flowers[i].getEnd().isAfter(maxEnd)) {
                        maxEnd = flowers[i].getEnd();
                        idx = i;
                        find = true;
                    }
                }
                if (!find) {
                    count = 0;
                    break;
                }
                start = flowers[idx].getEnd();
                count++;
                idx++;
            }

            bw.write(String.valueOf(count));
        }
    }

}

class Flower implements Comparable<Flower> {

    private final LocalDate start;
    private final LocalDate end;

    Flower(String str) {
        StringTokenizer st = new StringTokenizer(str);
        start = LocalDate.of(2023, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        end = LocalDate.of(2023, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
    }

    public LocalDate getStart() {
        return start;
    }

    public LocalDate getEnd() {
        return end;
    }


    //equals, hashCode, toString 생략
    @Override
    public int compareTo(Flower o) {
        if (this.start.equals(o.start)) {
            return o.end.compareTo(this.end);
        }
        return this.start.compareTo(o.start);
    }
}

🚀TIL

• 처음엔 LocalDate를 좀 더 활용하고 싶어 CronoUtil.DAYS.between(start,end)로 period를 구해서 최적해를 찾아보려 했는데, 시작 날짜에 따라 문제의 최적해가 꽃의 period만으로 판단할 수 없어서 수정하였습니다.
• 날짜를 다루는 알고리즘 문제가 꽤 자주 나오는데, 시간내서 java.time 복습을 해야겠습니다.
  
  

🔍문제

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

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

🤔발상

주어진 데이터는 노드와 간선이 주어지는 그래프 형태의 데이터이며 음의 가중치가 존재합니다.
그 중에 사이클이 존재하는지 검사하는 알고리즘으로 벨만포드 알고리즘으로 풀기에 적합한 문제라 판단하였습니다.
최단거리를 찾는 방법 중 자주 쓰이는 알고리즘 3개 중 하나이며 각각의 특징은 다음과 같습니다.

• 다익스트라
  • 한 노드 사이의 최단거리를 계산
  • DP를 이용하여 빠름
  • 음의 가중치가 존재하면 사용 불가능
• 플로이드 워셜
  • 모든 노드 사이의 최단거리를 계산
  • O(N ^ 3) 시간복잡도로 느림
  • 음의 가중치가 존재해도 사용 가능
• 벨만포드
  • 모든 노드 사이의 최단거리를 계산
  • 음의 가중치가 존재해도 사용 가능
  • 음수 사이클을 감지 가능함

🔦입출력

음의 가중치가 주어진 간선은 입력 순서로 구분되며, 입력값을 전처리해주어야 합니다.

📃의사코드

- 데이터 입력
- 입력시 음의 가중치 별도 처리
- 벨만포드 알고리즘 이용, 거리 업데이트
- 사이클 검사 결과 출력

👨‍💻코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int tc = Integer.parseInt(br.readLine());
            for (int i = 0; i < tc; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int v = Integer.parseInt(st.nextToken());
                int undirected = Integer.parseInt(st.nextToken());
                int directed = Integer.parseInt(st.nextToken());
                Graph graph = new Graph(v, undirected * 2 + directed);
                graph.init(br, undirected, directed);
                graph.bellmanFord(1);
                bw.write(!graph.isCycle ? "NO" : "YES");
                bw.newLine();
            }
        }
    }
}

class Graph {

    boolean isCycle;

    class Edge {

        /**
         * source
         */
        int s;
        int dest;
        int weight;

        Edge() {
            s = dest = weight = 0;
        }

        Edge(int s, int dest, int weight) {
            this.s = s;
            this.dest = dest;
            this.weight = weight;
        }
    }

    int V, E;
    /**
     * edge
     */
    ArrayList<Edge> e;

    Graph(int v, int en) {
        V = v;
        E = en;
        e = new ArrayList<>();
        isCycle = false;
    }

    public void init(BufferedReader br, int undirected, int directed) throws IOException {
        StringTokenizer st;
        for (int i = 0; i < undirected; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            e.add(new Edge(src, dest, weight));
            e.add(new Edge(dest, src, weight));
        }
        for (int i = 0; i < directed; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            e.add(new Edge(src, dest, -weight));
        }
    }

    public void bellmanFord(int src) {
        Graph graph = this;
        int V = graph.V, E = graph.E;

        int[] dist = new int[V + 1];
        Arrays.fill(dist, 1000000000);
        dist[src] = 0;

        for (int i = 1; i <= V; i++) {
            for (int j = 0; j < E; j++) {
                Edge edge = graph.e.get(j);
                if (dist[edge.dest] > dist[edge.s] + edge.weight) {
                    dist[edge.dest] = dist[edge.s] + edge.weight;
                }
            }
        }

        for (int i = 0; i < E; i++) {
            Edge edge = graph.e.get(i);
            if (dist[edge.dest] > dist[edge.s] + edge.weight) {
                isCycle = true;
            }
        }
    }
}

🚀TIL

• 문제를 푸는 것보다 개선에서 굉장히 고생을 많이 하였습니다.
• 최초 풀이는 평소 익숙한 방식인 2중연결리스트로 그래프 자료구조를 구현하여 일반적인 그래프 순환탐색을 이용하여 구현하였습니다.(노드마다 모든 간선을 탐색하는게 아닌, 연결 간선만 탐색)
• 그 후 최적화 시도를 위해 연결관계를 표현하지 않고 간선만 입력받아 리스트로 저장한 뒤, 간선을 순회하는 벨만포드 알고리즘 의사코드를 작성하였는데 몇가지 오류가 발생하였습니다
  • 이전엔 발생하지 않던 오버플로 발생(Integer.MAX_VALUE로 초기화 하면 오류 발생)
  • 간선을 입력받으면서 생기는 사소한 반복문 인덱스 이슈
  • 시간제한 이슈(이는 오버플로 이슈를 우회하다 생긴 이슈)
    • 한번만 수행하면 되는 벨만포드지만 오버플로로 오답이 발생, 그런데 시작지점을 변경하여 여러번 반복수행하면 오버플로 오답이 놀랍게도 해결됨(??)
• 몇일전부터 고민하던 1시작 반복문을 for(i=0; i<n; ++i)로 개선
  • 이를 통해 배열일 경우 선언문에서만 +1 해주고 입력값을 그대로 사용가능

🔍문제

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

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

🤔발상

친구의 친구, 친구의 친구의 친구는 주어진 연결관계 내에서 경유를 통해 연결될 수 있는가를 물어보는 문제로 파악했습니다.
플로이드 워셜로 최단경로를 업데이트 하면 연결관계를 알 수 있고, 이를 이용해 가장 작은 점수, 그리고 그 점수에 해당하는 사람들을 찾으면 되며, 이를 위해 자료구조와 정렬이 필요합니다.

정렬 문제는 정렬이 문제의 핵심키워드일 경우엔 추가적인 시간복잡도, 공간복잡도 고려가 필요하지만 입력수가 50처럼 작은 경우에는 자바에서 기본적으로 제공하는 라이브러리나 스트림 등을 사용해도 큰 이슈 없이 해결되는 경우가 많습니다.

최적화를 위해선 다소 코드가 복잡해도 for문이나 배열을 이용해 직접 조작하는게 좋지만, 간단하게 해결할 수 있는 경우엔 쉬운 방법을 택하는 것도 괜찮은 전략입니다.

🔦입출력

최대 회원의 입력 수는 50이며 종료 입력을 받아 입력을 종료해야 합니다.
100 미만이므로 O(N ^ 3)에 적합합니다.

📃의사코드

- 데이터 입력받기
- 연결관계 업데이트(플로이드 워셜)
- 점수 계산
- 결과 출력(정렬된 결과)

👨‍💻코드

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

public class Main {
  public static void main(String args[]) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int n = Integer.parseInt(br.readLine());
            Election election = new Election(n);

            while (true) {
                String[] input = br.readLine().split(" ");
                int a = Integer.parseInt(input[0]);
                int b = Integer.parseInt(input[1]);
                if (a == -1 && b == -1) {
                    break;
                }
                election.addConnection(a, b);
            }

            election.floydWarshall();
            election.calculateScore();
            bw.write(election.getResult() + "\n");      
        }
  }
}

class Election {

    static final int INF = 10000000;

    int[][] graph;
    Candidate[] candidates;
    int minScore;
    int n;

    public Election(int n) {
        this.n = n;
        this.graph = new int[n + 1][n + 1];
        this.candidates = new Candidate[n + 1];
        this.minScore = INF;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    graph[i][j] = INF;
                }
            }
        }
    }


    public void addConnection(int a, int b) {
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    public void floydWarshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }

    public void calculateScore() {
        for (int i = 1; i <= n; i++) {
            int max = 0;
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] < INF) {
                    max = Math.max(max, graph[i][j]);
                }
            }
            candidates[i] = new Candidate(max, i);
            minScore = Math.min(minScore, max);
        }
    }

    public String getResult() {
        StringBuilder sb = new StringBuilder();
        List<Candidate> list = Arrays.stream(candidates).filter(candidate -> {
            if (candidate == null) {
                return false;
            }
            return candidate.score == minScore;
        }).sorted().collect(Collectors.toList());

        sb.append(minScore).append(" ").append(list.size()).append("\n");
        for (Candidate candidate : list) {
            sb.append(candidate.number).append(" ");
        }
        return sb.toString().trim();
    }
}

class Candidate implements Comparable<Candidate> {

    int score;
    int number;

    public Candidate(int score, int number) {
        this.score = score;
        this.number = number;
    }

    @Override
    public int compareTo(Candidate o) {
        return this.number - o.number;
    }
}

🚀TIL

• 최저 점수인 사람들을 찾고 정렬하는게 번거로워 보여 별도 클래스를 만들고 Comparable을 구현하여 필터링, 정렬을 동시에 해결을 시도했습니다.
• 개인 IDE에선 java 17 을 사용하고 있는데, 문제 사이트는 java 11이다보니, 스트림 api의 toList() 메서드를 지원하지 않아(자바 16부터 지원) 컴파일 에러가 발생하는 이슈가 있었습니다.
• Try-with-resource 문법은 꽤 괜찮았으며, 반복문의 변수를 의미변수로 명명하는 것은 IDE를 사용할 땐 편리하지만 IDE 도움 없이 라이브코딩하는 경우 코드작성이 번거롭고 오타의 위험이 있어 안쓰는게 더 좋을 것 같습니다.

🔍문제

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

케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.

예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?

천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.

케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.

오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.

예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.

1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.

2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.

3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.

4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.

마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.

5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

🤔발상

문제의 핵심 아이디어는 모든 사람들의 연결 단계 수를 계산하고 그 합인 케빈 베이컨 수 중 최소 값을 출력하는 것입니다.
어제 풀었던 알고리즘인 플로이드 와셜 알고리즘을 활용하기 적절한 문제이며 약간의 후처리 과정으로 답을 얻을 수 있습니다.

🔦입출력

유저의 수가 100 이하이므로 플로이드 와셜 알고리즘의 제한사항 중 하나인 O(N ^ 3)으로 시간 내에 수행 가능할 것으로 생각됩니다.

📃의사코드

- 연결 관계 입력받기
- 플로이드 와셜 -> 연결 관계 업데이트
- 케빈 베이컨 수 계산
- 결과 출력

👨‍💻코드

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

public class Main {
    
    /*
    - 모든 사람의 최단경로 계산
    - 한 사람의 최단경로 합 계산
    - 가장 작은 최단경로(케빈 베이컨의 수) 출력
    
    - 입력제한 N (2 <= N <= 100)
    */
    
  public static void main(String args[]) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      KevinBacon kv = new KevinBacon();
      kv.init(br);
      bw.write(String.valueOf(kv.getResult()));
      bw.close();
  }
}

class KevinBacon {
    private int n;
    private int[][] graph;
    private final int INF = 1000000;

    public void init(BufferedReader br) throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        graph = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j){
                    graph[i][j] = INF;
                }
            }
        }

        for(int i=0;i<m;i++){
            updateGraph(br.readLine());
        }
    }

    private void updateGraph(String input) throws IOException{
        String[] inputs = input.split(" ");
        int a = Integer.parseInt(inputs[0]);
        int b = Integer.parseInt(inputs[1]);

        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    private void floydWarshall(){
        for(int k=1;k<= n;k++){
            for(int i=1;i<= n;i++){
                for(int j=1;j<= n;j++){
                    int newDistance = graph[i][k] + graph[k][j];
                    if(newDistance < graph[i][j]){
                        graph[i][j] = newDistance;
                    }
                }
            }
        }
    }

    public int getResult(){
        floydWarshall();
        int minSum = Integer.MAX_VALUE;
        int result = 0;
        for(int i=1;i<=n;i++){
            int sum = 0;
            for(int j=1;j<=n;j++){
                if (graph[i][j] < INF) {
                    sum += graph[i][j];
                }
            }
            if(sum < minSum){
                minSum = sum;
                result = i;
            }
        }
        return result;
    }

}

🚀TIL

• 이전에 풀었던 문제로 개인적인 학습을 위해 클래스로 만들어 기능을 메서드 별로 분리하였습니다.(TDD 개발방법론 적용)
• 리팩토링 후 결과 제출에 이슈가 있었는데, BufferdWriter의 write 메서드를 사용할 때, int  결과값을 그대로 반환하여 String을 인자로 받는 write 메서드와 파라미터 불일치로 이상값이 출력되어 수정하였습니다.
• 코드 가독성 관련하여 몇가지 개선사항을 확인하여 다음부터 적용할 예정입니다.
  • 매직넘버 로직(graph\[i]\[j] < 10000000) -> INF 상수화 + boolean isConnect() 메서드 추출
  • 문제별로 다른 입출력 시작순서(0 시작 or 1 시작)을 구별하기 위한 1 시작일 경우 i j 관습변수가 아닌 personNumber 등의 의미변수 사용
• BufferedReader와 BufferedWriter가 가독성 측면에서 분리하는게 좋을 것 같아 try-with-resources 문법으로 감싸주면 좋을 것 같습니다.