99클럽 코테 스터디 17일차 TIL + 오늘의 학습 키워드

☑️ 문제: 촌수 계산

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

 

☑️ Code

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static int N, M, start, end;
    static int[][] link;

    public static void main(String args[]) {
        input();
        int degree = bfs();
        System.out.print(degree);
    }
    
    static void input() {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        link = new int[N+1][N+1];
        start = sc.nextInt();
        end = sc.nextInt();
        
        M = sc.nextInt();
        int x, y;
        for (int i = 0; i < M; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            link[x][y] = 1;
            link[y][x] = 1;
        }
    }
    
    static int bfs() {
        // 1. init depth
        int[] depth = new int[N+1];
        for (int i = 1; i <= N; i++) {
            depth[i] = -1;
        }
        
        // 2. BFS
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        depth[start] = 0;

        int v;
        while (!q.isEmpty()) {
            v = q.poll();
            
            for (int w = 1; w <= N; w++) {
                if (link[v][w] == 1 && depth[w] == -1) {
                    depth[w] = depth[v] + 1;
                    if (w == end) {
                        return depth[w];
                    }
                    q.offer(w);
                }
            }
        }
        return -1;
    }
}

 

☑️ 기억하자: Java에서의 Queue

• Queue 선언 및 초기화: Queue<T> queue = new LinkedList<>();
• queue에 값을 삽입
  • queue.offer(value): 실패 시, false
  • queue.add(value): 실패 시, Exception
• 가장 처음 넣은 값을 반환하며 "삭제"
  • queue.poll(): 가장 처음 넣은 값을 반환하며 삭제, 공백 queue면 null 반환
  • queue.remove(): 가장 처음 넣은 값을 반환하며 삭제, 공백 queue면 Exception
• queue.peek(): 가장 처음 넣은 값을 반환. ""삭제하지 않는다"", ""공백 queue면 null 반환""

참고
https://kwin0825.tistory.com/157