99클럽 코테 스터디 8일차 TIL : DFS(백준 2644번)

 

 

촌수계산

 

 

 

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

 

 

---

⭐나의 풀이

 

💡 아이디어) 

 

부모 - 자식 1촌

 

할아버지

ㅣ

아빠 --- 삼촌1

ㅣ

나 

 

DFS 알고리즘을 사용해 깊이를 찾으면 몇촌인지 계산할 수 있다.

 

 

 

 

✔ 최종 제출한 코드)

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

class Main {
    private static List<Integer>[] graph;
    private static int[] visited;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());//사람 수 1<=n<=100
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s);

        int p1 = Integer.parseInt(st.nextToken()); //사람1
        int p2 = Integer.parseInt(st.nextToken()); //사람2

        int m = Integer.parseInt(br.readLine());//부모자식간의 관계의 개수

        graph = new ArrayList[n+1];
        visited = new int[n+1];
        
        for(int i=1;i<n+1;i++){
            graph[i] = new ArrayList<>(); 
        }
        
        for(int i=1;i<m+1;i++){
            s = br.readLine();
            st = new StringTokenizer(s);

            int r1 = Integer.parseInt(st.nextToken()); //사람1
            int r2 = Integer.parseInt(st.nextToken()); //사람2
            
            graph[r1].add(r2);
            graph[r2].add(r1);
        }

        int answer = searchRelationship(p1, p2, 0);
        
        System.out.println(answer);
    }

    private static int searchRelationship(int p1, int p2, int depth){
        int answer = -1; //아무관계도 없으면

        visited[p1] = 1;

        for(int i:graph[p1]){
            //p1에 관계가 있는사람들 가져오기
            if(visited[i]==0){
                    //방문한적없으면
                if(i==p2){
                    //찾던 사람이면
                    answer = depth+1;
                }else{
                    answer = Math.max(answer, searchRelationship(i,p2,depth+1));
                }
            }
        }
            

        return answer;
    }
}

 

결과

걸린 시간: 45분 16초

---

 ⭐오늘의 회고

DFS 알고리즘을 일주일 새 여러번 사용했더니 많이 적응한 것 같다.

바로 DFS 사용해야겠다는 생각도 하고, 알고리즘 작성하는데 별로 어려움을 느끼지 않았다.

뿌듯하다. 일주일 동안 열심히 한 결과인가 ! 

 

아 그리고 할로윈데이 이벤트로 선물도 받았다. 

럭키데이네 ㅎㅎ