[백준] 알고리즘 분류(너비 우선 탐색,JAVA)2644번, 촌수계산

문제 링크

2644번: 촌수계산

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 부모와 자식의 관계를 1촌으로 정의합니다.

2. 두 사람의 친척 관계를 촌수로 표현할 수 없을 때 -1을 결과로 출력합니다.

3. 요구한 두 사람의 촌수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 가족들의 관계를 그래프 형태로 구성한 뒤, BFS으로 요구한 두 사람의 촌수를 탐색합니다.

 

3. 탐색이 종료된 뒤 얻은 촌수를 결과로 출력합니다.

 

 

촌수 탐색.

 

부모와 자식의 관계를 가지는 친척들끼리는 연결되어있다고 그래프를 만듭니다.

 

1번 친척과 3번 친척이 부모 자식 관계이면 연결되어있다고 표현합니다.

 

요구한 사람 중 1명을 기준으로 BFS을 진행하여 다른 사람 1명을 만날 때까지 탐색을 진행합니다.

 

다른 사람 1명에게 도달하지 못하면 -1

 

도달하면 지금까지 건너간 인물의 수(촌수)를 결과로 출력합니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

n = 9

 

요구한 인물들 : 7, 3

 

m = 7

 

친척들의 관계

 

1 - 2

1 - 3

2 - 7

2 - 8

2 - 9

4 - 5

4 - 6

2. 가족들의 관계를 그래프 형태로 구성한 뒤, BFS으로 요구한 두 사람의 촌수를 탐색합니다.

가족들의 관계 그래프

 

BFS 탐색 진행!

요구한 친척 7부터 탐색 진행

 

3번째 진행하는 과정에서 다른 요구한 친척 3에게 도착!

 

3. 탐색이 종료된 뒤 얻은 촌수를 결과로 출력합니다.

 

지나간 친척 : 7 → 2 → 1 → 3

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용하여 친척 관계에 대한 정보를 띄어쓰기 기준으로 나누었습니다.
• 친척 관계를 가지고 ArrayList<ArrayList<Integer>>()에 그래프 형태로 저장합니다.
• bfs함수를 이용하여 요구한 두 사람의 촌수를 확인하기 위해 탐색합니다.
• 탐색 종료한 뒤 결과를 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• bfs함수는 BFS으로 친척 관계에 대한 그래프를 탐색하여 촌수를 확인합니다.

결과코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    //BFS탐색에 사용할 정보 클래스
    static class info{
        int index, count;	//현재 친척, 지나간 친척 수
        //생성자
        public info(int index, int count){
            this.index = index;
            this.count = count;
        }
    }
    //그래프 정보
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int answer = -1;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        //그래프 초기화
        for(int i=0;i<=n;i++)
            graph.add(new ArrayList<>());
        int m = Integer.parseInt(br.readLine());
        //친척간의 관계 그래프 형태로 구현
        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine()," ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        bfs(s, e, n);	//BFS탐색 진행
        bw.write(answer + "");	//탐색 종료한 뒤 결과 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //친척간의 관계로 촌수를 구하는 BFS탐색하는 함수
    static void bfs(int start, int end, int N){
        Queue<info> q = new LinkedList<>();	//BFS탐색에 사용할 Queue
        boolean[] visited = new boolean[N+1];	//방문 확인 배열
        visited[start] = true;	//출발 친척 방문 확인
        q.add(new info(start, 0));	//출발 친척 Queue 저장
        //탐색 진행
        while(!q.isEmpty()){
            info cur = q.poll();
            if(cur.index == end){	//요구한 다른 친척 방문
                answer = cur.count;	//지나간 촌수 저장
                break;	//탐색 종료
            }
            //인접한 친척들 탐색
            for(int next : graph.get(cur.index)){
                if(!visited[next]){	//방문하지 않은 인접한 친척일 때
                    visited[next] = true;
                    q.add(new info(next, cur.count+1));
                }
            }
        }
    }
}