[자바] 백준 14588 - Line Friends (Small) (java)

 문제 : boj14588

---

 

필요 알고리즘 개념

• Floyd-warshall 또는 BFS, 그래프 이론
  
  • 플로이드 와샬 혹은 BFS로 풀 수 있는 그래프 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

 

1. 결국 서로간의 최단거리를 구해야 함. 그럼 bfs, 플로이드 와샬, 다익스트라 정도가 생각남.
2. O(N^3) 해도 N이 300이라 매우 충분하므로 대충 구현 쉬운 플로이드 와샬로 진행함.
3. 중요한건 일단 위치정보를 가지고, 그래프를 만드는 것임. (18~30line)
  -> 처음엔 200001개짜리 배열에 범위별로 전부 기입해서 순회하면서 찾을 생각이었는데, TC중에 -1000000, 1000000 인게 300개라면 시간초과 나게됨.
  -> 그래서 좀 더 심플한 방법으로 변경함. 겹치는건 결국 3가지중 하나임. A와 B 선분이 있을 경우, A선분안에 B의 양 끝중 하나가 포함 (24,25line)되거나, B 선분 내에 A선분이 포함되면 됨. (B선분이 A선분에 포함되는 경우는 B의 양 끝중 하나가 포함되는것과 동일함)
4. 아무튼 연관관계를 작성했다면 플로이드 와샬만 돌려주면 끝.
5. 이후 Q개 만큼 들어오는 대로 플로이드 와샬 돌려준거에서 꺼내서 출력해주면 됨.

 

 

  문제의 그림은 선분 형태이지만, 각 선분이 정점이라고 하고 겹치는 선분에 대해 간선이 존재한다고 생각해보자. 이 경우 겹치는 선분은 각각 가중치 1을 가지는 친구들이다. 여기서 알고싶은건 모든 N개의 정점에서 모든 N개의 정점으로 몇 단계 건너띄어야 갈 수 있냐이다. 즉, 정점과 간선으로 바꾸고 보면 모든 정점에서의 단순 BFS 문제가 된다.

 

  BFS를 써도 되지만, 모든 정점에서 모든 정점으로 향하는건 Floyd-warshall이라는 오래걸리지만 (O(N^3)이므로 이 문제에서는 N이 최대 300이라 적용 가능하다.), 구현 간단하고 강력한 알고리즘으로 한방에 해결이 가능하다. 그러므로 문제의 입력을 정점과 간선으로 변경해주기만 잘 하면 플로이드 와샬 한방에 해결되는 문제이다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] pos = new int[n+1][2];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            pos[i][0] = Integer.parseInt(st.nextToken());
            pos[i][1] = Integer.parseInt(st.nextToken());
        }

        // make adjacent list
        int[][] adj = new int[n+1][n+1];
        for (int i = 1; i <= n; i++)
            Arrays.fill(adj[i], 301);
        for (int i = 1; i <= n; i++) {
            for (int j = i+1; j <= n; j++) {
                if ((pos[j][0] >= pos[i][0] && pos[j][0] <= pos[i][1])
                        || (pos[j][1] >= pos[i][0] && pos[j][1] <= pos[i][1])
                        || (pos[j][0] < pos[i][0] && pos[j][1] > pos[i][1])) {
                    adj[i][j] = adj[j][i] = 1;
                }
            }
        }
        pos = null;

        // floyd-washall
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
                }
            }
        }

        // result
        int q = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            sb.append(adj[a][b] == 301 ? -1 : adj[a][b]).append('\n');
        }
        System.out.println(sb);
    }
}