[백준] 14496. 그대, 그머가 되어

문제 링크

[백준] 14496. 그대, 그머가 되어

풀이 과정

BFS 탐색 문제입니다.

for (int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

for (int i = 0; i < M; i++) {
    int u = sc.nextInt();
    int v = sc.nextInt();

    adj[u].add(v);
    adj[v].add(u);
}

System.out.println(bfs());

먼저 문제의 입력으로 인접 리스트를 구현합니다. 무방향 그래프이므로, 양쪽 정점 모두를 연결시켜 줍니다. 그래프가 만들어졌다면 bfs 메소드 를 호출해 정점 a에서 정점 b로의 최소 거리를 구합니다.

static int bfs() {
    Queue<int[]> q = new LinkedList<>();
    visit[a] = true;
    q.add(new int[]{a, 0});

    while (!q.isEmpty()) {
        int[] now = q.poll();

        if (now[0] == b) {
            return now[1];
        }

        for (int next : adj[now[0]]) {
            if (visit[next]) continue;
            visit[next] = true;
            q.add(new int[]{next, now[1] + 1});
        }
    }

    return -1;
}

bfs 메소드 는 정점 a를 시작으로 정점 b까지의 최소 거리를 구해 리턴합니다.

• 큐는 1차원 배열로 구성되어 있으며, 0번째 요소는 정점 번호를, 1번째 요소는 해당 정점까지의 거리를 의미합니다.
• 정점 b에 도달할 수 있으면, 그 때까지 지나온 거리를 리턴하며, 도달할 수 없다면 -1을 리턴합니다.

코드

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

public class Main {
    static int a, b, N, M;
    static ArrayList<Integer> adj[];
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a = sc.nextInt();
        b = sc.nextInt();
        N = sc.nextInt();
        M = sc.nextInt();
        adj = new ArrayList[N + 1];
        visit = new boolean[N + 1];

        for (int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            adj[u].add(v);
            adj[v].add(u);
        }

        System.out.println(bfs());
    }

    static int bfs() {
        Queue<int[]> q = new LinkedList<>();
        visit[a] = true;
        q.add(new int[]{a, 0});

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[0] == b) {
                return now[1];
            }

            for (int next : adj[now[0]]) {
                if (visit[next]) continue;
                visit[next] = true;
                q.add(new int[]{next, now[1] + 1});
            }
        }

        return -1;
    }
}