[백준] 6118번 숨바꼭질 (BFS_JAVA)

처음에 DFS로 풀어보려다가 잘 안되어서

바로 BFS로 바꿔 풀었다!

 

BFS는 익숙한데 DFS는 아직 익숙하지 않아서 연습해야겠다

그래도 맞혀서 기분 좋다ㅎㅎ

 

---

문제

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

6118번: 숨바꼭질

 

 

---

 

설계

알고리즘 설계[접근 방법] : BFS

서로 연결된 노드들을 인접리스트로 구현한다.

양방향 연결이기 때문에 A_i와 B_i를 서로 연결해준다.

1부터 시작해 연결된 노드들를 탐색하며, BFS로 1번과 얼마나 떨어져 있는지 계산한다.

BFS이기 때문에 방문체크배열 isvisited을 만들어줬고, 얼마나 떨어져있는지의 값을 result배열에 담는다.

result배열에 담긴 값 중 최고값을 찾고, 최고값인 노드 중 작은 값과 개수를 출력한다.

 

 

---

코드

import java.util.*;

public class Main{
    
	static boolean[] isvisited;
    static int[] result;
    static List[] list;
    
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	
        int n = sc.nextInt();    //헛간 개수
        int m = sc.nextInt();    //간선 개수
        
        //거리를 저장할 배열
        result = new int[n+1];   
        
        //방문 체크 배열
        isvisited = new boolean[n+1];
        
        //인접리스트 만들기
        list = new ArrayList[n+1];
        for(int i=0; i<n+1; i++){
            list[i] = new ArrayList<Integer>();
        }
        
        //연결 입력받기
        for(int i=0; i<m; i++){
            int conn1 = sc.nextInt();
            int conn2 = sc.nextInt();
        
            list[conn1].add(conn2);
            list[conn2].add(conn1);
        }
        
        BFS(new int[] {1, 0});
        
        //최대 거리 찾기
        int max=Integer.MIN_VALUE;
        for(int i=0; i<result.length; i++) {
        	if(max<result[i]) max=result[i]; 
        }
        
        //최대 거리 개수 찾기
        int count=0;
        int first=0;
        for(int i=0; i<result.length; i++) {
        	if(result[i]==max) count++;
        	if(result[i]==max && first==0) first=i;
        }
        
        //출력
        System.out.println(first + " " + max + " " + count);
    }
    
    public static void BFS(int[] location){
        
    	Queue<int[]> queue = new LinkedList();
    	
    	queue.add(location);
    	isvisited[location[0]]=true;
    	
    	while(!queue.isEmpty()) {
    		
    		//현재 좌표
    		int[] curr = queue.poll();	
    		int idx=curr[0];
    		int depth=curr[1];
    		
    		//거리 저장
    		result[idx] = depth;
    		
    		for(int i=0; i<list[idx].size(); i++) {
    			int newIdx = (int)list[idx].get(i);
 
    			if(isvisited[newIdx]) continue;		//이미 방문한 곳 패스
    			isvisited[newIdx]=true;
    			queue.add(new int[] {newIdx, depth+1});
    		}
    	}
    }
}

 

 

 

(❁´◡`❁)

끝!