[JAVA] 백준 1260번

[백준 1260번 DFS와 BFS]

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

• 문제 재정의:

https://mygumi.tistory.com/102

---

• 생각한 것:

일단 인접 행렬에 input값들을 저장해 트리 구조를 저장 (양방향임을 주의)

DFS는 따라 따라 가면됨. 끊기면 오른쪽으로 이동

BFS는 한 번 내려가고 바로 오른쪽, 맨 오른쪽까지 간다음 다시 왼쪽으로 돌아와 탐색

---

• 코드

//이클립스 코드
package till;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=null;

        st = new StringTokenizer(br.readLine());
        int n = 0,m=0,start=0,x=0,y=0;

            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            start = Integer.parseInt(st.nextToken());

        int[][] a = new int[n+1][n+1];

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
                x=Integer.parseInt(st.nextToken());
                y=Integer.parseInt(st.nextToken());
                a[x][y]=1;
                a[y][x]=1;
        }
         /*인접행렬 출력
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                System.out.print(a[i][j]+" ");
            }
            System.out.println("");
        }
        */

        boolean[] check = new boolean[n+1];
        Arrays.fill(check, Boolean.FALSE);

        boolean[] check2 = new boolean[n+1];
        Arrays.fill(check2, Boolean.FALSE);
        dfs(a, check, start);
        System.out.println("");
        bfs(a, check2, start);

    } 

    public static void dfs(int a[][],boolean[] check, int start){ //깊이 우선
        int n = a.length - 1; 
        check[start] = true; 
        System.out.print(start+" "); 
        for (int i = 1; i <= n; i++) 
        { 
            if (a[start][i] == 1 && !check[i]) 

                { dfs(a, check, i); }
        }

    }

    public static void bfs(int a[][],boolean[] check2, int start){ //너비 우선
        Queue<Integer> q = new LinkedList<>(); 
        int n = a.length - 1; 
        q.add(start); check2[start] = true; 

        while (!q.isEmpty()) { 
            start = q.poll(); 
            System.out.print(start + " "); 

            for (int i = 1; i <= n; i++) { 
                if (a[start][i] == 1 && !check2[i]) 
                    { q.add(i); check2[i] = true; } 
                } 
            }

    }
 }

---

• 피드백:

dfs/bfs 안에 int n은 전역으로 빼자
재귀이고 스택에 계속 쌓이니까