[Day08]JAVA- 백준 촌수계산(DFS)

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

 

 

 

촌수계산 문제를 풀기 위해서는 DFS , BFS 와 같은 탐색방법을 알고 있어야한다. 

 

입력값 을 노드로 그려보면 아래와 같은 모양이다. 

9
7 3 
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

 

 

쉽게 말해 두 노드 사이의 간선의 개수 를 센다고 생각하면 쉽다. 

 

* DFS(깊이 우선탐색) 활용 방식

 

기본적인 DFS 방식을 활용하면 되지만 주의해야할 점이 있다!

 

처음에는 result 배열에 각 시작 노드와의 간선의 개수를 저장하도록 했다.

int count=1;
public static void DFS(int y)
    {
        Stack<Integer> stack = new Stack<>();

        stack.push(y);
        result[y] = count;
        visited[y] = true;

        while(!stack.isEmpty())
        {
            int c = stack.pop();

            for(int g : graph.get(c))
            {  
                if(!visited[g])
                {                    
                   result[g] = count++;           
                    stack.push(g);   
                    visited[g] = true;

                    System.out.println("자식노드" + g + ",촌수: " + result[g]);
                }
            }
        }
    }

 

 

결과 값 : 

자식노드1,촌수: 1
자식노드2,촌수: 2
자식노드7,촌수: 3
자식노드8,촌수: 4
자식노드9,촌수: 5

 

자식노드 7,8,9 는 같은 자식레벨로 동일하게 촌수가 3이 되어야 하는데 방문할때마다 간선의 개수를 증가시키니 문제와는 맞지 않은 결과 값이 나왔다. 

 

*수정

int count = 0;
public static void DFS(int y)
{
    Stack<Integer> stack = new Stack<>();

    stack.push(y);
    result[y] = count;
    visited[y] = true;

    while(!stack.isEmpty())
    {
        int c = stack.pop();

        for(int g : graph.get(c))
        {  
            if(!visited[g])
            {                    
                result[g] = result[c]+1;          
                stack.push(g);   
                visited[g] = true;

                System.out.println("자식노드" + g + ",촌수: " + result[g]);
            }
        }
    }
}

 

결과 값: 

자식노드1,촌수: 1
자식노드2,촌수: 2
자식노드7,촌수: 3
자식노드8,촌수: 3
자식노드9,촌수: 3

 

부모 노드의 간선 + 1 로 자식노드는 동일한 간선을 갖게 하도록 수정했다. 

 

*최종코드 

import java.util.*;
import java.io.*;
public class Main{
static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
static boolean[] visited; 
static int[] result;
static int count=0;    

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

    //전체사람 수 
    int n = Integer.parseInt(br.readLine());

    StringTokenizer st = new StringTokenizer(br.readLine());
    //찾는 두사람
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());

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

    visited = new boolean[n+1];
    result = new int[n+1];

    //노드 초기화
    for(int i=0;i<=n;i++)
    {
        graph.add(new ArrayList<>());
        visited[i]= false;        
    }

    for(int i=0;i<m;i++)
    {
        st = new StringTokenizer(br.readLine()," ");
        int u =    Integer.parseInt(st.nextToken());
        int v =    Integer.parseInt(st.nextToken());
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    DFS(y);

    int answer = result[x];

    if(answer == 0)
        answer = -1;

    System.out.println(answer);    

}

public static void DFS(int y)
{
    Stack<Integer> stack = new Stack<>();

    stack.push(y);
    result[y] = count;
    visited[y] = true;

    while(!stack.isEmpty())
    {
        int c = stack.pop();

        for(int g : graph.get(c))
        {  
            if(!visited[g])
            {                    
                result[g] = result[c]+1;          
                stack.push(g);   
                visited[g] = true;

                System.out.println("자식노드" + g + ",촌수: " + result[g]);
            }
        }
    }
}   
}