[백준/JAVA] 2644번: 촌수계산

🔺 문제

2644번: 촌수계산

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, a, b, cnt;
    static ArrayList<Integer>[] A;
    static int[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());    // 전체 사람 수
        
        // 변수들 초기화
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        visited = new int[N + 1];
        
        // 촌수 계산할 두 사람 번호
        st = new StringTokenizer(br.readLine(), " ");
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        
        // 데이터 입력받기
        M = Integer.parseInt(br.readLine());
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            A[x].add(y);
            A[y].add(x);
        }
        
        bfs(a, b);
        System.out.println(visited[b] == 0 ? -1 : visited[b]);
    }
    
    private static void bfs(int s, int e) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            if(now == e)    return;
            
            for(int next : A[now]) {
                if(visited[next] == 0) {
                    visited[next] = visited[now] + 1;    // 🔔 촌수 누적 🔔
                    queue.add(next);
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ BFS / DFS
- 방문 배열을 int형으로 받아 촌수 계산

 

 

---

🔺 다른 풀이들

- DFS 풀이

https://loosie.tistory.com/165

 

- 2차원 배열 사용한 DFS풀이

https://namhandong.tistory.com/185

---

💬 느낀 점

어려운 문제도 아닌데 쫄지 말자!!!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔

https://dev2som.tistory.com/78