[DFS] 백준 - 1595번: 북쪽나라의 도로 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

1595번: 북쪽나라의 도로

 

 

문제는 다음과 같다.

 

 

이미 방문한 도시는 다시 방문할 수 없고, A 도시와 B 도시 간에 가장 먼 거리를 재는 것이다.

그래서 가장 먼 거리를 계산해 보면 5번 노드에서 시작해서 1번, 6번, 3번 순으로 가면 총 거리 22로 제일 길다.

 

근데 입력 조건에 보면 뭔가 언제부터 언제까지 받아야 하는지 표시가 안 되어 있었다.

코드로 확인해 보자

 

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Bridge>[] map;
    static boolean[] visit;
    static int N = 10001;
    static int count;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        map = new ArrayList[N];
        visit = new boolean[N];

        for (int i = 0; i < N; i++) {
            map[i] = new ArrayList<>();
        }

        while (true) {
            int a, b, c;

            try {
                String str = sc.nextLine();
                String[] nums = str.split(" ");
                a = Integer.parseInt(nums[0]) - 1;
                b = Integer.parseInt(nums[1]) - 1;
                c = Integer.parseInt(nums[2]);
            } catch (Exception e) {
                break;
            }

            map[a].add(new Bridge(b, c));
            map[b].add(new Bridge(a, c));
        }

        for (int i = 0; i < N; i++) {
            dfs(i, 0);
        }

        System.out.println(count);
    }

    private static void dfs(int start, int d) {
        visit[start] = true;

        for (int i = 0; i < map[start].size(); i++) {
            if (!visit[map[start].get(i).getCity()]) {
                dfs(map[start].get(i).getCity(), d + map[start].get(i).getDist());
            }
            if (visit[map[start].get(i).getCity()]) {
                count = Math.max(d, count);
            }
        }
        visit[start] = false;
    }
}

class Bridge {
    int city;
    int dist;

    public Bridge(int city, int cost) {
        this.city = city;
        this.dist = cost;
    }

    public int getCity() {
        return city;
    }

    public int getDist() {
        return dist;
    }
}

 

일단 위에부터 차근차근 보면 입력이 최대 10000개의 도시가 있을 수 있기 때문에 N은 10001로 지정해뒀다.

그리고 Bridge 클래스를 만들지 않고 2차원 배열로 [A도시][B도시] = 거리로 하려고 했는데 메모리가 많이 잡아먹을 것 같아 ArrayList[]로 하였다.

 

그 후 while문을 통해 일단 입력을 계속 받는데 만약 null 값이나 이상한 값이 들어오면 종료를 시켜야 하기 때문에 try~catch문으로 잡아줬다.

 

그리고 map에 각각 저장하면 된다.

 

DFS에서는 먼저 들어온 노드를 방문 처리를 해준 후,

 

for문을 돌려주는데 첫 if문은 방문할 도시가 방문하지 않았으면 dfs를 돌려주는데 이때 파라미터 d와 dist를 더해 넣어준다.

다음 if문은 다음에 방문할 도시가 이미 방문되었다면 기존에 카운트된 것과 파라미터로 들어온 계산된 d의 값 중 더 큰 값을 count에 넣는다.

 

for문이 끝나면 현 노드를 미방문 처리로 바꾼다.

그래야지 여러가지의 경우의 수를 계산할 수 있기 때문이다.