[백준] 2644번: 촌수계산 - JAVA

 

문제

 

 

 

풀이

 

전체 사람 수, 촌수를 계산해야하는 대상(A, B)을 입력받는다.

사람수만큼의 2차 배열을 만들고 자식관계를 입력받아 1로 변경한다.

 

Ex) 전체 사람이 3명이고 1-2, 1-3의 관계를 받은 경우

	0	1	2	3
0	0	0	0	0
1	0	0	1	1
2	0	1	0	0
3	0	1	0	0

 

대상 A의 촌수를 저장하는 1차 배열을 만들고 0으로 초기화한다.

DFS알고리즘을 사용하여 가족수만큼 반복하고, 대상 A를 기준으로 나머지 가족과의 촌수를 계산한다.

A와 관계가 있는 대상(A1)인 경우 1, (A1)을 기준으로 재반복하여 해당 대상과 관계가 있는 대상(A2)은 2,

A2를 기준으로 관계가 있는 대상(A3)은 3... 으로 반복하여 모든 대상과의 촌수를 입력한다.

배열의 대상B 위치의 값이 0이라면 -1을 값이 있다면 값을 출력한다.

 

 

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static int member;
    static int[][] family;
    static int[] dist;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        member = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine(), " ");
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int count = Integer.parseInt(br.readLine());

	// 대상 A와의 촌수가 저장될 배열
        dist = new int[member + 1];
        // 전체 가족관계에 대한 2차 배열
        family = new int[member + 1][member + 1];

        for(int i = 0; i < count; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int C = Integer.parseInt(st.nextToken());
            int D = Integer.parseInt(st.nextToken());

            family[C][D] = family[D][C] = 1;
        }

        dfs(A, B);

        System.out.println(dist[B] == 0 ? -1 : dist[B]);
    }

    static void dfs(int x, int y) {
        if(x == y) {
            return;
        }

        for(int i = 1; i <= member; i++) {
            // 관계가 있고 촌수계산이 되어있지 않다면
            if(family[x][i] == 1 && dist[i] == 0){
                dist[i] = dist[x]+1;
                dfs(i, y);
            }
        }
    }
}

 

 

문의사항이나 피드백은 댓글로 남겨주세요.