[BOJ] 2644번 : 촌수계산

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

간단한 dfs/bfs 문제

난 bfs로 풀었다...원래 List로 자주 풀었는데, 이번에는 인접행렬로 풀었다.

왜냐. A형에 인접행렬이 나왔어서 그냥 글케 해따. 히히 

public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 전체 사람 수

        st = new StringTokenizer(br.readLine());
        n1 = Integer.parseInt(st.nextToken());
        n2 = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());

        map = new int[n+1][n+1];
        v = new int[n+1];

        for(int i=0;i<m;i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            map[x][y]=map[y][x]=1;
            // 가족 혹은 친척들 사이의 관계 -> 촌수
        }

        bfs(n1);

        System.out.println(ans);

    }

 

입력받는걸 한 바가지로 받아주고 bfs 돌려주면 된다.

처음에 메모리 초과 났었는데, 정신 나가서 visited 배열 안써서 메모리 초과 났었다. 

static void bfs(int u) {
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(u, 0));
        v[u] = 1;

        while(!q.isEmpty()) {
            Node cur = q.poll();
            int x = cur.x;
            int d = cur.d;

            if(x==n2) {
                ans = d;
                break;
            }

            for(int i=1;i<=n;i++) {
                if(map[x][i]==1 && v[i]==0) {
                    q.add(new Node(i, d+1));
                    v[i] = 1;
                }
            }
        }
    }

 

https://141227.tistory.com/237

[DFS/BFS] 백준 2644번 촌수계산(Java)

이 사람이 아주 정리를 잘해놨다...

내가 정리할 기운이 없다...그냥 이거랑 방식 똑같다.

https://trillium.tistory.com/50

[BOJ] 2644 : 촌수계산(Java)

이건 list로 푼거...그냥 다음부터는 list로 풀어야지 히힛

[전체코드]

import java.io.*;
import java.util.*;

class Solution {
    static int n, x, y, n1, n2, m, ans=-1;
    static int map[][], v[];

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 전체 사람 수

        st = new StringTokenizer(br.readLine());
        n1 = Integer.parseInt(st.nextToken());
        n2 = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());

        map = new int[n+1][n+1];
        v = new int[n+1];

        for(int i=0;i<m;i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());
            map[x][y]=map[y][x]=1;
            // 가족 혹은 친척들 사이의 관계 -> 촌수
        }

        bfs(n1);

        System.out.println(ans);

    }

    static void bfs(int u) {
        Queue<Node> q = new ArrayDeque<>();
        q.add(new Node(u, 0));
        v[u] = 1;

        while(!q.isEmpty()) {
            Node cur = q.poll();
            int x = cur.x;
            int d = cur.d;

            if(x==n2) {
                ans = d;
                break;
            }

            for(int i=1;i<=n;i++) {
                if(map[x][i]==1 && v[i]==0) {
                    q.add(new Node(i, d+1));
                    v[i] = 1;
                }
            }
        }
    }
}

class Node{
    int x;
    int d;
    Node(int x, int d) {
        this.x = x;
        this.d = d;
    }
}