백준 2644번: 촌수계산

풀이 1

• 부모노드, 자식노드의 정보를 가진 "Node" 클래스 정의
• tree 구조에서 자식노드->부모노드 순으로 탐색하도록 DFS

결과 : 오답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Problem2644 {
    static int nodeSize;
    static int[] object = new int[2];
    static int relNum;
    //노드의 인덱스 = 노드의 이름(0번 : null)
    static Node[] nodes;
    static int finalAns = -1;


    public static void dfs(int curNode, boolean[] visited, int answer){
        visited[curNode] = true;
        if(curNode == object[1]){
             finalAns = answer;
        }
        else {
            for(int node : nodes[curNode].chilNode){
                if(!visited[node]){
                    answer++;
                    dfs(node, visited, answer);
                }
            }

            if(!visited[nodes[curNode].parNode] && nodes[curNode].parNode != 0) {
                answer++;
                dfs(nodes[curNode].parNode, visited, answer);
            }

        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        nodeSize = Integer.parseInt(br.readLine());
        nodes = new Node[nodeSize+1];

        StringTokenizer objSt = new StringTokenizer(br.readLine(), " ");
        object[0] = Integer.parseInt(objSt.nextToken());
        object[1] = Integer.parseInt(objSt.nextToken());

        relNum = Integer.parseInt(br.readLine());
        for(int i = 0; i < relNum; i++){
            StringTokenizer relSt = new StringTokenizer(br.readLine(), " ");
            int parNum = Integer.parseInt(relSt.nextToken());
            int chiNum = Integer.parseInt(relSt.nextToken());
            //노드의 자속노드 설정
            if(nodes[parNum]==null){
                Node tempNode = new Node();
                tempNode.chilNode.add(chiNum);
                nodes[parNum] = tempNode;
            } else {
                nodes[parNum].chilNode.add(chiNum);
            }

            //노드의 부모노드 설정
            if(nodes[chiNum]==null){
                Node tempNode = new Node();
                tempNode.parNode = parNum;
                nodes[chiNum] = tempNode;
            } else {
                nodes[chiNum].parNode = parNum;
            }

        }
        if(object[0] == object[1]){
            System.out.println(0);
        } else {
            boolean[] visited = new boolean[nodeSize+1];
            int answer = 0;
            dfs(object[0], visited, answer);
            System.out.println(finalAns);
        }
    }

    public static class Node{
        int parNode = 0;
        ArrayList<Integer> chilNode;

        Node(){
            chilNode = new ArrayList<>();
        }
    }
}

• 최단경로가 존재해 틀린것으로 생각, BFS로 풀이했다.
• DFS로 푼 사람의 풀이를 보니 최단거리 문제는 아니었다. 부모, 자식노드를 구분하기 않고 인접 리스트(ArrayList<ArrayList>)로 풀이하던데, 이 방법이 훨씬 깔끔하고 좋았다.

풀이 2

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

public class Problem2644_2 {
    static int nodeSize;
    static int[] object = new int[2];
    static int relNum;
    //노드의 인덱스 = 노드의 이름(0번 : null)
    static Node[] nodes;
    static int finalAns = -1;
    static int[] visited;


    public static void bfs(int startNode){
        Queue<Node> queue = new LinkedList<>();
        visited[startNode] = 0;
        queue.add(nodes[startNode]);

        while(!queue.isEmpty()){
            Node curNode = queue.poll();
            //자식노드
            for(int node : curNode.chilNode){
                //처음 방문
                if(visited[node] == Integer.MAX_VALUE){
                    visited[node] = visited[curNode.name]+1;
                    queue.add(nodes[node]);
                } else {
                    //최소경로인 경우에만 이동, queue에 넣는다
                    if(visited[node] > visited[curNode.name]+1){
                        visited[node] = visited[curNode.name]+1;
                        queue.add(nodes[node]);
                    }
                }
            }

            //부모노드
            if(curNode.parNode != 0) {
                //처음 방문
                if(visited[curNode.parNode] == Integer.MAX_VALUE){
                    visited[curNode.parNode] = visited[curNode.name]+1;
                    queue.add(nodes[curNode.parNode]);
                } else {
                    //최소경로인 경우에만 이동, queue에 넣는다
                    if(visited[curNode.parNode] > visited[curNode.name]+1){
                        visited[curNode.parNode] = visited[curNode.name]+1;
                        queue.add(nodes[curNode.parNode]);
                    }
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        nodeSize = Integer.parseInt(br.readLine());
        nodes = new Node[nodeSize+1];

        StringTokenizer objSt = new StringTokenizer(br.readLine(), " ");
        object[0] = Integer.parseInt(objSt.nextToken());
        object[1] = Integer.parseInt(objSt.nextToken());

        relNum = Integer.parseInt(br.readLine());
        for(int i = 0; i < relNum; i++){
            StringTokenizer relSt = new StringTokenizer(br.readLine(), " ");
            int parNum = Integer.parseInt(relSt.nextToken());
            int chiNum = Integer.parseInt(relSt.nextToken());
            //노드의 자속노드 설정
            if(nodes[parNum]==null){
                Node tempNode = new Node(parNum);
                tempNode.chilNode.add(chiNum);
                nodes[parNum] = tempNode;
            } else {
                nodes[parNum].chilNode.add(chiNum);
            }

            //노드의 부모노드 설정
            if(nodes[chiNum]==null){
                Node tempNode = new Node(chiNum);
                tempNode.parNode = parNum;
                nodes[chiNum] = tempNode;
            } else {
                nodes[chiNum].parNode = parNum;
            }

        }
        if(object[0] == object[1]){
            System.out.println(0);
        } else {
           visited = new int[nodeSize+1];
            Arrays.fill(visited, Integer.MAX_VALUE);
            bfs(object[0]);
            if(visited[object[1]] == Integer.MAX_VALUE){
                System.out.println(-1);
            } else {
                System.out.println(visited[object[1]]);
            }
        }
    }

    public static class Node{
        int parNode = 0;
        int name;
        ArrayList<Integer> chilNode;

        Node(int name){
            this.name = name;
            chilNode = new ArrayList<>();
        }
    }
}