(JAVA) [BOJ]백준 2644번, 촌수계산

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

2644번: 촌수계산

2644, 촌수계산

[ 난이도 : 실버 2 ]

이번 문제도 BFS를 이용해서 푸는 문제이다.

 

직전에 풀었던 스타트 링크와 굉장히 유사한 풀이기에 참조하면 좋을 것 같다 !

 

https://seung-seok.tistory.com/60

(JAVA) [BOJ]백준 5014번, 스타트링크

# Process

input

: 사람의 수와 시작&목표 좌표 그리고 연결 관계를 차례로 입력받는다. 

양방향성 그래프를 표기하기 위해 ArrayList 를 사용하여 서로에게 값을 넣어준다.

(연결되는 선이 많을 수 있기 때문에 인덱스별로 ArrayList 를 생성!)

static int N, M, ox, oy;
static ArrayList<Integer>[] adj;
static int[] dist;

static void input() 
{
    N = scan.nextInt();
    adj = new ArrayList[N+1];

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

    ox = scan.nextInt(); oy = scan.nextInt();

    M = scan.nextInt();
    while(M-- >0)
    {
        // 양방향 연결
        int x = scan.nextInt(); int y = scan.nextInt();
        adj[x].add(y);
        adj[y].add(x);
    }
}

 

BFS

: 시작 좌표부터 BFS 탐색을 진행해서 목표좌표까지의 거리를 구해주면 된다.

// start 에서 시작해서 갈 수 있는 모든 점점 탐색
static void bfs(int start) 
{
    Queue<Integer> Q = new LinkedList<>();
    dist = new int[N+1];
    for(int i=1; i<=N; i++) dist[i] = -1;

    Q.add(start);
    dist[start] = 0;

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

        for(int y : adj[x])
        {
            // 방문한 적이 있다면 pass
            if(dist[y] != -1) continue;

            Q.add(y);
            dist[y] = dist[x] + 1;
        }
    }
}

전체 코드

: 이렇게 구현하면 연결 관계가 아닌 경우에 자연스레 -1 을 출력할 수 있다.

조건에 연결할 수 없다면 -1 을 출력하라는 문구가 추후에 힌트로도 작용할 수 있을 것 같다.

static int N, M, ox, oy;
static ArrayList<Integer>[] adj;
static int[] dist;

static void input() 
{
    N = scan.nextInt();
    adj = new ArrayList[N+1];

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

    ox = scan.nextInt(); oy = scan.nextInt();

    M = scan.nextInt();
    while(M-- >0)
    {
        // 양방향 연결
        int x = scan.nextInt(); int y = scan.nextInt();
        adj[x].add(y);
        adj[y].add(x);
    }
}

static void pro() 
{
   bfs(ox);
   System.out.println(dist[oy]);
}

// start 에서 시작해서 갈 수 있는 모든 점점 탐색
static void bfs(int start) 
{
    Queue<Integer> Q = new LinkedList<>();
    dist = new int[N+1];
    for(int i=1; i<=N; i++) dist[i] = -1;

    Q.add(start);
    dist[start] = 0;

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

        for(int y : adj[x])
        {
            // 방문한 적이 있다면 pass
            if(dist[y] != -1) continue;

            Q.add(y);
            dist[y] = dist[x] + 1;
        }
    }
}

public static void main(String[] args) 
{
    input();
    pro();
}