백준 2644 촌수계산 JAVA

solved.ac 티어 = 실버2

BFS 기초 문제 중 하나이다.

 

1. 접근

 

정점의 최대 갯수는개수는 100개이며 완전 그래프라 가정해도 간선의 개수는 n * (n - 1) / 2 = 100 * (100 - 1) / 2 = 4,950개, 그에 따른 무방향 그래프의 차수의 개수는 4,950 * 2 = 9,900개로 시간제한에 여유 있게 풀 수 있다.

 

2. 풀이

 

두 번째 입력값인 두 사람의 촌수, 즉 예제로 보자면 다음 그림과 같다.

 

그림판 괴발 ....

다른 기초 BFS 문제와 같이 이동할 때 마다 배열에 1씩 누적하며 최종 목적지의 값을 출력하면 끝이다.

 

전역 변수 및 input

static int V, E, start, end;
static ArrayList<Integer>[] graph;
static int[] dist;
public static void main(String[] args) throws IOException {
    V = Integer.parseInt(br.readLine()); // 정점의 갯수
    st = new StringTokenizer(br.readLine());
    start = Integer.parseInt(st.nextToken()); // 출발지
    end = Integer.parseInt(st.nextToken()); // 목적지
    E = Integer.parseInt(br.readLine()); // 간선의 갯수
    dist = new int[V + 1];
    graph = new ArrayList[V + 1];
    for (int i = 1; i <= V; i++) {
        graph[i] = new ArrayList<>();
    }
    for (int i = 1; i <= E; i++) { // 그래프 연결
        st = new StringTokenizer(br.readLine());
        int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
        graph[x].add(y); // x -> y
        graph[y].add(x); // y -> x
    }
    solution();
}

 

배열 초기화 및 BFS 호출

static void solution() {
    Arrays.fill(dist, -1);
    BFS(start);
    System.out.println(dist[end]);
}

 

BFS

static void BFS(int x) {
    Queue<Integer> Q = new LinkedList<>();
    Q.add(x);
    dist[x] = 0;

    while(!Q.isEmpty()) {
        x = Q.poll();

        for (int y : graph[x]) {
            if (dist[y] != -1) continue; // 이미 방문했다.
            Q.add(y);
            dist[y] = dist[x] + 1; // 이동횟수 증가
        }
    }
}

 

3. 전체코드