BFS

BFSで白俊2644号をJavaに解く.
最初は問題の理解が足りなかったので、自分で変な条件を作って、過去に戻りましたが、理解してみると簡単なBFS問題であることがわかりました.

1本の足にまたがってナビゲートする

BFSの意味で、まず幅検索を行い、私が探している相手の番号と一致するかどうかを計算します.
Qのサイズに合わせてドアを繰り返し回し、条件に合ったやつを加え、Q乞いまでwhileドアを回し、世代を上げればいい.
Qのサイズのように重文を回す理由は、親の方向も子供の方向も同じなので、一つの段階に加わる人には同じ節度があるからです.
途中で私が探している相手に出会ったら、returnを打つので、相手が見つからない場合は、whileのドアを離れて、彼を-1に戻させます.
以下は私が書いたbfs(int人1,int人2)コードです.

static Integer bfs(int p1, int p2){
        int result = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(p1);

        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int cur = q.poll();
                visited[cur] = true;
                if(cur==p2) return result;
                for (int child = 1; child <= n; child++) {
                    if (map[cur][child] == 1) {
                        if (!visited[child])
                            q.add(child);
                    }
                }
            }
            result++; // 촌수 늘려주기
        }
        return -1;
    }

親と子を区別しない関連面を表示

最初のエラーはmap[][]でmap[parent][[child]にのみ接続マークが付けられていたことです.その結果,親の向上と子の向上の動作の間に差が生じ,方向性に応じて処理する問題が生じた.もちろん、単独で処理しても結果は間違っています.
重要なのは、互いにつながっている限り、map[][]の上の両側にマークをつけなければならない.上下に違いはない.
これはどういう意味ですか.次のコードを見るともっとよく理解できるはずです.

for(int i=0; i<m; i++){
            stk = new StringTokenizer(bfr.readLine());
            int parent = Integer.parseInt(stk.nextToken());
            int child = Integer.parseInt(stk.nextToken());
            map[parent][child] = 1; \\ 
            			    양 방향 모두!!
            map[child][parent] = 1; //
        }

次は私が提出したコードです.

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

public class boj2644 {
    static int n,m, p1,p2;
    static int[][] map;
    static boolean[] visited;

    public static void main(String args[]) throws IOException {
        BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bfw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bfr.readLine());
        n = Integer.parseInt(stk.nextToken());
        map = new int[n+1][n+1];    visited = new boolean[n+1];
        stk = new StringTokenizer(bfr.readLine());
        p1 = Integer.parseInt(stk.nextToken()); p2 = Integer.parseInt(stk.nextToken());
        stk = new StringTokenizer(bfr.readLine());
        m = Integer.parseInt(stk.nextToken());
        for(int i=0; i<m; i++){
            stk = new StringTokenizer(bfr.readLine());
            int parent = Integer.parseInt(stk.nextToken());
            int child = Integer.parseInt(stk.nextToken());
            map[parent][child] = 1;
            map[child][parent] = 1;
        }

        bfw.write(String.valueOf(bfs(p1,p2)));
        bfw.close();
    }

    static Integer bfs(int p1, int p2){
        int result = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(p1);

        while(!q.isEmpty()){
            int size = q.size();
            for(int i=0; i<size; i++){
                int cur = q.poll();
                visited[cur] = true;
                if(cur==p2) return result;
                for (int child = 1; child <= n; child++) {
                    if (map[cur][child] == 1) {
                        if (!visited[child])
                            q.add(child);
                    }
                }
            }
            result++;
        }
        return -1;
    }
}