[백준] 2644번 촌수계산 JAVA (자바) 풀이

문제 2644번

 :  부모와 자식 사이 1촌
    나와 할아버지 사이 2촌
    나와 아버지 형제 사이 3촌

 :  주어진 두 사람의 촌수를 계산하는 프로그램 작성

 

 [입력]

 :  첫째 줄에는 전체 사람 수 n

 :  둘째 줄에는 촌수를 계산할 두 사람의 번호 r1, r2
 :  셋째 줄부터 쌍을 이루는 관계 개수 m

 :  넷째 줄부터 부모 자식의 관계를 나타내는 x, y

 

 [출력]

 :  두 사람의 촌수를 나타내는 정수 출력
 :  두 사람의 친척 관계가 없다면 -1 출력

 [DFS 코드]

import java.io.*;
import java.util.*;
public class Main{
    static int arr[][];
    static boolean visit[];
    static int n, r1, r2, m;
    static int result = -1;
    
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        n = Integer.parseInt(br.readLine());
        
        st = new StringTokenizer(br.readLine());
        r1 = Integer.parseInt(st.nextToken());
        r2 = Integer.parseInt(st.nextToken());
        
        m = Integer.parseInt(br.readLine());
        
        arr = new int[n+1][n+1];
        visit = new boolean[n+1];
        
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[x][y]=arr[y][x]=1;
        }
        DFS(r1,0);
        
        System.out.print(result);   
    }
    public static void DFS(int now, int count){
        visit[now] = true;
        
        if(now==r2){
            result=count;
            return;
        }
        
        for(int i =1; i<=n; i++){
            if(arr[now][i] == 1 && visit[i]==false){
                DFS(i, count+1);
                
            }
        }
    }
}

 

 [해설]
     

 :  static int arr[][];  2차원 배열 설정

    static boolean visit[];  방문기록 설정

    static int n, r1, r2, m;  첫째줄, 둘째줄, 넷째줄 입력

    static int result = -1;  결과값 -1 로 초기화

 

 :  n = Integer.parseInt(br.readLine());  총 사람 수 (첫째 줄 입력)

    st = new StringTokenizer(br.readLine());  
    r1 = Integer.parseInt(st.nextToken());  촌수 계산할 사람 1 (둘째 줄 입력)
    r2 = Integer.parseInt(st.nextToken());  촌수 계산할 사람 2 (둘째 줄 입력)
    m = Integer.parseInt(br.readLine());  쌍을 이루는 관계 수 (셋째 줄 입력)

 

 :  arr = new int[n+1][n+1];  배열 1부터 시작하게끔 + 1 하기

    visit = new boolean[n+1];  배열 1부터 보려고 +1 하기

 :  for(int i=0; i<m; i++) {  쌍을 이루는 개수만큼만 계산

          st = new StringTokenizer(br.readLine());  공백 단위로 단어 끊어 읽기

          int x = Integer.parseInt(st.nextToken());  연결 부모 (넷째 줄부터)

          int y = Integer.parseInt(st.nextToken());  연결 자식 (넷째 줄부터)

          arr[x][y] = arr[y][x] = 1;   arr[1][2] 과 arr[2][1] 은 같다는 표시 
    }                                           값이 1이면 촌수 계산 가능 (= arr에서 이동가능)

 :  DFS(r1,0);  dfs에 r1을 넣고 시작 (촌수 계산할 두사람 중 한사람 먼저 고정해놓고 계산)

 

 :  System.out.println(result);  결과 출력

 :  static void DFS(int now, int count) {  now는 현재 비교대상 / count는 결과값
         visit[now] = true;  현재의 노드를 방문 처리 ( visit[r1]=true 로 초기값 고정) 

 

         if(now==r2){ 현재노드가  둘째줄에서 입력받은 [사람2]라면 끝내기
                 result=count;  결과값 -1이 아닌 새로운 값으로 갱신
                 return;
         }

         for(int i=1; i<n+1; i++) {  1부터 사람 수 만큼 반복
                  if(arr[now][i] == 1 && visit[i] == false) {  now와 연결됐지만 방문 기록은 false

                                                                                   arr[사람1][사람2]   /   visit[사람2]

                           DFS(i, count+1);                              DFS(r1,0)으로 시작했으니까 [사람1]은 r1으로 고정

                                                                                   값이 1이면 x, y의 관계로 이동이 가능하단 뜻 (위아래로)

                                                                                   다음번 DFS는 [사람2] 자리의 노드를 [사람1] 로 지정

                                                                                   (해당 i노드와 연결된 또다른 사람 찾기)
                  }

         }

   }   

 

 

 [문제 과정]

출처&nbsp;https://hianna.tistory.com/163

 

	visit[now]	arr[now][i]	DFS	count
1 단계	visit[7]	arr[7][2]	DFS(7,0+1)	1
2 단계	visit[2]	arr[2][1]	DFS(2,1+1)	2
3 단계	visit[1]	arr[1][3]	DFS(1, 2+1)	3
4 단계	i = 3 = now = r2		result = count = 3

▶ 1 단계
    : DFS(7, 0)
      visit[now] 초기값 = visit[r1] = visit[7]
      아예 [사람1]은 방문처리 하고 시작
      arr[7][i]에서 i는 7과 쌍을 이루는 또 다른 노드이다 = 2번 노드 
      DFS(7, 1) = count는 1이다

▶ 2 단계
    : visit[now]는 visit[i]로 갱신한다 = visit[2]
      arr[2][i]에서 i는 2과 쌍을 이루는 또 다른 노드이다 = 1, 8 , 9번 노드
     숫자가 작은 노드들부터 검사 = 1번 노드
      DFS(2, 2) = count는 2이다

▶ 3 단계
    : visit[now]는 visit[i]로 갱신한다 = visit[1]
      arr[1][i]에서 i는 1과 쌍을 이루는 또 다른 노드이다 = 3번 노드 
      DFS(1, 3) = count는 3이다

▶ 4 단계
    : now = r2이면 현재노드 = 끝나야할 노드 (3번 노드) 같다면 
      arr[now][i] == arr[3][i]
      result를 count 값으로 대체
      이때 result ++ 하지 않고 count를 따로 쓴 이유는 애초에 result 초기값을 -1로 설정해둬서
      +1하면 계산하기가 복잡하다
      그래서 count를 따로 쓰고 그 값으로 맨 마지막에 대체해서 출력하면 된다

 

 

      

이제 풀어보러 갈께요 :)

 

 

 

 

 

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

2644번: 촌수계산

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *