[BOJ] 2644.촌수계산(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  

가족, 부모, 자식이라고 문제에 나오니까

너무 트리에만 폭 빠져있었더니 잘 풀리지가 않았었다.

관계에만 포인트를 두고 관계를 따라가면서 촌수를 계산하면

금방 풀릴 문제였다.

고정관념을 버리자..

#. Code

먼저 사람 간의 관계를 잘 저장해주는게 포인트(?)이다.

우리는 연결된 관계를 타고 타고 가면서 촌수를 카운트해야 하므로..

다음 찾을 두 사람(a, b) 중 한 사람을 기준으로 시작하자.

그 사람(a)부터 관계를 타고 가면서 촌수를 저장해주고

대상(b)을 만나면 그 때의 촌수를 출력해주면 된다.

BFS를 활용해서 이미 촌수를 확인한 사람은 pass 해주고

확인을 안한 사람들은 촌수를 증가시켜주면서 관계를 타고 가는 것이다.

촌수를 확인할 수 없을 때는, 

res 값이 갱신되지 않으므로 결국 -1 을 출력하고 종료될 것이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ2644 {       static int N, a, b, res = -1, dist[];     static ArrayList<Integer> relation[];          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st;                  N = Integer.parseInt(br.readLine());    // 전체 사람 수         dist = new int[N+1];    // 촌수         relation = new ArrayList[N+1];    // 관계 정보         for (int i = 1; i <= N; i++)              relation[i] = new ArrayList<Integer>();         Arrays.fill(dist, -1);                  st = new StringTokenizer(br.readLine(), " ");         // a, b 의 촌수를 구해야 함         a = Integer.parseInt(st.nextToken());         b = Integer.parseInt(st.nextToken());                  int M = Integer.parseInt(br.readLine());    // 관계의 개수                  // 관계 정보 저장         for (int i = 0; i < M; i++) {             st = new StringTokenizer(br.readLine(), " ");             int p = Integer.parseInt(st.nextToken());             int ch = Integer.parseInt(st.nextToken());             relation[p].add(ch);             relation[ch].add(p);         }                  Queue<Integer> q = new LinkedList<Integer>();         // a와 b의 촌수를 찾아야 하므로, a부터 출발         dist[a] = 0;         q.add(a);         while(!q.isEmpty()) {             // 확인할 사람을 queue에서 빼고             int now = q.poll();             // 비교 대상을 찾으면 촌수(결과값) 저장             if(now == b) {                 res = dist[now];                 break;             }             // 해당 사람과 관계있는 사람들을 확인             for (int i = 0; i < relation[now].size(); i++) {                 int tmp = relation[now].get(i);                 // 이미 촌수를 확인한 사람이면 pass                 if(dist[tmp] != -1) continue;                 // 다음 관계는 현재까지 촌수 + 1                 dist[tmp] = dist[now] + 1;                 q.add(tmp);             }         }                  System.out.println(res);     }          }   Colored by Color Scripter

cs