[백준] 2644번: 촌수계산

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

 

 

 

문제 파악

-총 노드 갯수 n

-특정 노드 a,b (a: start, b: target)

-간선 m

-~연결관계~ : 단방향(부모-자식 관계 명확)

*StringTokenizer는 문자열 한 줄에서만 유효, 여러 줄일 시 새로운 st 선언해줘야 한다. 

*또한 띄어쓰기가 있는 문자열 쪼개는 데 쓴다.

*br.readLine으로 받아서 해당 String.charAt()으로 받는 건 띄어쓰기가 없을 경우에 사용!

 

접근 방법

-BFS함수 별도 작성

-시작점a로부터 도착노드b까지 top-bottom이 명확한 그래프이지만, 위로 거슬러 올라가는 로직을 별도로 추가하여

4방향 탐색하듯이 (경우 따져보고 전진), 

가능하면 전진하여 카운트하고 아니면 그 다음 경우로 부모까지 순회하여 큐에 모두 순서대로 담아준다.

-부모로 가든, 자식으로 가든 1노드씩 전진하므로 레벨을 잘 카운트해서 레벨 증가시키며 리스트에 담아주기

-만약, target을 찾으면 카운트 한 레벨 값을 리턴하고, 못찾으면 -1

-못찾았다 = 다른 네트워크에 있다. 다른 그래프다. 공통 조상 없다. 닿을 수 없는 남이다. 😂

 

코드 구현

package baekjoon;

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

public class p2644_촌수계산 {
    public void 촌수계산() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n=Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a=Integer.parseInt(st.nextToken());
        int b=Integer.parseInt(st.nextToken());
        int m=Integer.parseInt(br.readLine());//간선 갯수=관계 갯수
        Map<Integer, List<Integer>> map = new HashMap<>();
        Map<Integer, List<Integer>> reverseMap = new HashMap<>(); // 부모-자식 관계를 역으로 저장하는 맵

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int parent=Integer.parseInt(st.nextToken());
            int child=Integer.parseInt(st.nextToken());
            map.putIfAbsent(parent,new ArrayList<>());
            map.get(parent).add(child);
            // 자식에서 부모로의 관계도 추가
            reverseMap.putIfAbsent(child, new ArrayList<>());
            reverseMap.get(child).add(parent);
        }
        int distance = bfs(a,b,n,map,reverseMap);
        System.out.println(distance);
    }

    public int bfs(int start,int target,int n,Map<Integer,List<Integer>> map,Map<Integer,List<Integer>> reverseMap){
        Queue<Integer> que=new ArrayDeque<>();
        boolean[] visited = new boolean[n+1];
        Map<Integer, Integer> levelMap = new HashMap<>();

        que.offer(start);
        visited[start]=true;
        levelMap.put(start,0);
        while(!que.isEmpty()){
            int node=que.poll();
            int level=levelMap.get(node);
            if(node==target){
                return level;
            }
            //level=result.get(node); //result.get(node)+1 노드(이전 레벨)이 기록 된 레벨 불러와 +1
            //map.get(node)가 null이면 nullPointException 발생 가능성 있음
            List<Integer> temp = map.getOrDefault(node, new ArrayList<>());
            for(int i:temp){
                if(!visited[i]){
                    que.add(i);
                    visited[i]=true;
                    levelMap.put(i,level+1);
                }
            }//해당 노드의 자식 먼저 순회하고,
            List<Integer> toParent = reverseMap.getOrDefault(node, new ArrayList<>());
            for(int i:toParent){
                if(!visited[i]){
                    que.add(i);
                    visited[i]=true;
                    levelMap.put(i,level+1);
                }
            }//해당 노드의 부모까지 순회한다.
        }

        return -1;
    }
}

배우게 된 점

-일단 빨리 찾으면 이득이니 BFS로 찾고

-처음엔, 방향성이 명확하여 공통 조상을 찾아, top-down 방식으로 순회하는 방식으로 코드를 짰지만

nullPointError가 자꾸 발생했고, 정확한 답이 나오지 않아서 통과를 못했다.

-방식을 바꿔 자식에서 부모로 거슬러 올라가는 로직을 추가함

-처음 보는 유형이라 생각하기까지가 어려웠다.