다메카솔

🔍문제

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 복습을 해야겠습니다.
  
  

🔍문제

오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.

깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.

🤔발상

간단한 dfs 구현 문제인데, 여러 개념들을 복습할 수 있을 것 같아 연습 겸 풀어보았습니다.
1. 그래프 탐색을 위한 그래프 자료구조 구현
2. bfs, dfs 탐색 구현
1. bfs 탐색에는 queue를 사용
3. 방문 순서는 클래스 레벨에서 전역변수로 관리, 노드번호를 인덱스로 배열에 저장해서 출력

🔦입출력

정점의 최대 수가 100,000입니다. 메모리 제한이 512mb이며 dfs는 재귀호출로 함수 내의 지역변수가 메모리에 저장됩니다. 불필요한 변수선언을 하지 않도록 주의합니다.

📃의사코드

- 데이터 입력
- dfs 탐색
- 연결노드 탐색 시, 정렬순서로 탐색
- 방문 순서를 저장
- 결과 출력

# 👨‍💻코드

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));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken());
            Graph graph = new Graph(n, m, start);
            graph.init(br);
            graph.dfs(start, new boolean[n + 1]);
            bw.write(graph.getResult());
        }
    }
}

class Graph {

    List<List<Integer>> graph;
    int start;
    int nodeCount;
    int edgeCount;
    boolean[] visited[];
    int[] visitOrder;
    int visitIndex;

    Graph(int v, int e, int s) {
        nodeCount = v;
        graph = new ArrayList<>();
        for (int i = 0; i <= v; i++) {
            graph.add(new ArrayList<>());
        }
        visitOrder = new int[v + 1];
        this.edgeCount = e;
        this.start = s;
    }

    public void init(BufferedReader br) throws IOException {
        for (int i = 0; i < edgeCount; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            graph.get(src).add(dest);
            graph.get(dest).add(src);
        }
    }

    public void dfs(int node, boolean[] visited) {
        visited[node] = true;
        visitOrder[node] = ++visitIndex;
        List<Integer> integers = graph.get(node);
        integers.sort(Integer::compareTo);
        for (Integer nextNode : integers) {
            if (visited[nextNode]) {
                continue;
            }
            visited[nextNode] = true;
            dfs(nextNode, visited);
        }
    }

    public void bfs(int node) {
        boolean[] visited = new boolean[nodeCount];
        Queue queue = new LinkedList<Integer>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Integer cur = (Integer) queue.poll();
            visited[cur] = true;
            for (Integer nextNode : graph.get(cur)) {
                if (visited[nextNode]) {
                    continue;
                }
                visited[nextNode] = true;
                queue.offer(nextNode);
            }
        }
    }

    public String getResult() {
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < visitOrder.length; i++) {
            sb.append(visitOrder[i]).append("\n");
        }
        return sb.toString();
    }
}

🚀TIL

• 하나의 자료구조도 문제의 요구사항에 맞춰 적합한 구현형태가 다르다보니 하나의 풀이만 존재하지 않는 것 같습니다.
• 자주 사용하지 않으면 잊어버리므로 자주 복습하도록 노력해야겠습니다.

🔍문제

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 해주고 입력값을 그대로 사용가능