1260: DFS BFS

 public static void BFS(int start){
        Queue<Integer> q = new LinkedList<>();

        q.add(start);
        isVisited[start] = true;
        while(!q.isEmpty()){
            for(int i=1;i<arr.length;i++){
                if(!isVisited[i]&&arr[start][i]) {
                    isVisited[i] = true;
                    q.add(i);
                }
            }
            int x = q.poll();//이 코드를 여기다두면 틀림
            start = x;
            System.out.print(x + " ");
        }
        System.out.println();
    }

저코드가 있으면 안되는 이유는 일단 q에 넣은 값을 start로 잡아야하는데 start에 대해서 두번 검색을 하기때문이다. 일단 생각한것이랑 다르게 동작하고 있으므로 오답이 나올 수 있다.

 public static void BFS(int start){
        Queue<Integer> q = new LinkedList<>();

        q.add(start);
        isVisited[start] = true;
        while(!q.isEmpty()){
            int x = q.poll();//이위치
            start = x;//이위치
            for(int i=1;i<arr.length;i++){
                if(!isVisited[i]&&arr[start][i]) {
                    isVisited[i] = true;
                    q.add(i);
                }
            }
            System.out.print(x + " ");
        }
        System.out.println();
    }

11725

• 입력받을당시에는 뭐가 parent고 뭐가 child인지를 모른다.
  a랑 인접한 node가 어떤녀석들인지만 알 수있다. 그리고 우리는
  일단 루트노드부터시작해서 bfs 탐색을 해가면서. 큐에 넣어보면서
  큐에서 노드를 넣을시점에 큐에 넣을 data의 부모를 알 수 있다.
  왜냐하면. 큐에넣을 노드의 인접노드를 기준으로 for문을 돌려서 인접노드들을 찾아낼것이기때문에.
  그리고 또한 계속반복하는것을 막으려면 한번 방문한곳은 false처리를하든 해서 더이상 방문하면 안된다. 이를 위해 isVisited변수를 넣어주었고, parent를 idx별로 구하기위해 parents배열을 정의하였다

import com.sun.jdi.request.BreakpointRequest;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.OptionalInt;
import java.util.Queue;

public class Main{
    //1~n까지의 노드리스트를 담을 변수
    //이 노드를 1부터 시작해서 1의 이웃탐색 후 -> 큐에 쌓인 이웃노드 기준으로 계속탐색을 진행해나갈것임
    static Node[] nodeList;
    //i번째 애의 부모는 parents[i] = a 의 a값이다.
    static int[] parents;
    //방문했는데 계속방문하면안된다. 한번방문한곳은 q에 다시넣어지면안된다. 이 변수가 없으면 무한루프를 돌게된다
    static boolean[] isVisited;
    //node의 정의가 중요하다 left right parent같은 변수는 어차피 입력이 들어올떄 무엇이 parent인지 무엇이 left인지 모르기때문애
    //그냥 이웃한 노드들을 담는 리스트를 정의하였다
    public static class Node{
        int data;
        ArrayList<Integer> neighborList;
        //처음에 노드를 추가하는것을 생각해보자. 이웃노드는 여러번에 걸쳐들어올수있기때문에 일단 생성자로는 이웃노드까지 받는 코드대신
        //node가 가지고있는 값. data만 받도록하고 리스트를 초기화시켜준다
        public Node(int data){
            neighborList = new ArrayList<>();
            this.data = data;
        }
        //이웃노드 추가하는 코드
        public void addNeighbor(int data){
            neighborList.add(data);
        }
    }
    public static void solve(){
        //큐를 사용해서 bfs를돌린다. 그러면 이웃노드에 대해서만 계속 탐색을 할 수 있다
        Queue<Node> q = new LinkedList();
        //일단 1이 루트 노드이기때문에 큐에 nodelist[1]=1의 값을 가지는 노드 를 집어넣어주었다
        q.add(nodeList[1]);
        //q는 모든 노드를 방문하면 비어지게 될것이고, 그에 따라 반복문이 끝날것이다
        while(!q.isEmpty()){
            Node node = q.poll();
            int idx = node.data;
            //큐에서 빼낸 노드에 대해 반복문을 돌린다
            for (Integer item: node.neighborList) {
                //방문하지 않은 노드여야만 한다. 이전에 방문한 노드는 이미 부모가 밝혀졌거나. 내가 큐에 넣은 노드일 수 있다
                if(!isVisited[item]){
                    //예를들어 첫 노드 즉 data=1인 노드의 데이터는 idx값일것이다.
                    //item의 부모는 idx라고 설정해주는 코드이다
                    parents[item] = idx;
                    //방문처리
                    isVisited[item] = true;
                    //이웃노드에 대해 똑같은 행위를 반복할 수 있게 설정
                    q.add(nodeList[item]);
                }
            }
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        nodeList = new Node[n+1];
        parents = new int[n+1];
        isVisited = new boolean[n+1];
        for(int i=1;i<=n;i++){
            nodeList[i] = new Node(i);
        }
        for(int i=0;i<n-1;i++){
            String input[] = br.readLine().split(" ");
            int data1 = Integer.parseInt(input[0]);
            int data2 = Integer.parseInt(input[1]);
            nodeList[data1].addNeighbor(data2);
            nodeList[data2].addNeighbor(data1);
        }
        solve();
        for(int i=2;i<parents.length;i++){
            bw.write(parents[i]+"\n");
        }
        bw.flush();
        bw.close();

    }
}

2589

• 주석달아놓은거 이유 찾아야함

import com.sun.jdi.request.BreakpointRequest;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Collectors;

public class Main{
    static boolean isLand[][];
    static boolean isVisited[][];
    static int count;
    static int max;
    static class Point{
        int x;
        int y;
        int depth;
        Point(int x,int y, int depth){
            this.x=x;
            this.y=y;
            this.depth = depth;
        }
    }
    public static int bfs(int x, int y, int depth){
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x,y,depth));
        isVisited[y][x] = true;
        while(!q.isEmpty()){
            Point p = q.poll();
            if(max < p.depth) {
                System.out.println(p.depth);
            }
            max = Math.max(p.depth, max);
            //max의 위치가 여기면안된다 이유를 모르겠다
            add(q, p.x+1,p.y, p.depth);
            add(q, p.x-1,p.y, p.depth);
            add(q, p.x,p.y+1, p.depth);
            add(q, p.x,p.y-1, p.depth);
        }
        return max;
    }
    public static void add(Queue<Point> q, int x, int y, int depth){
        if(x>=0&&y>=0&&y<isLand.length&&x<isLand[0].length&&isLand[y][x] && !isVisited[y][x]){
            q.add(new Point(x,y,depth+1));
            isVisited[y][x] = true;

        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String input[] = br.readLine().split(" ");
        int m = Integer.parseInt(input[0]);
        int l = Integer.parseInt(input[1]);
        isLand = new boolean[m][l];
        for(int i=0;i<m;i++){
            char input2[] = br.readLine().toCharArray();
            for(int j=0;j<l;j++){
                isLand[i][j] = input2[j]=='L'?true:false;
            }
        }
        int max =0;
        for(int i=0;i<m;i++){
            for(int j=0;j<l;j++){
                isVisited = new boolean[m][l];
                if(isLand[i][j]) max = Math.max(bfs(j,i,0), max);
            }
        }
        bw.write(max+"\n");
        bw.flush();
        bw.close();

    }
}