[백준알고리즘] 그래프 - 1260번 DFS와 BFS

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

1260번: DFS와 BFS

dfs와 bfs 구현 연습용 문제같다
구현해본 경험이 거의 없어서 강의보고 공부하면서 풀었다

시행착오가 좀 있었다..
아직 잘 모르는 나는 이런 공부시켜주는 깔끔한 문제 좋아..^^

 

dfs 중간에 이부분이 꼭 있어야하나라고 주석 단 부분이 있는데 없으니 런타임 에러(InputDismatch)가 뜬다
디버깅 해보면서 이유를 찾아보려 애썼으나 아직 못찾았다..애초에 check되지 않은 원소일 경우에만 dfs가 수행되도록 했는데

대체 왜 저게 필요한거며..저 부분이 없으면 왜 InputDismatch가 뜨는건지...너무 궁금한데 모르겠다..

낼 찾아봐야겠다..

-> ??????

아무리 봐도 모르겠어서(그부분을 주석처리한 코드는 또 잘 맞았습니다가 뜬다..)

똑같이 다시 제출해봤는데 이번엔 맞았습니다가 뜬다....백준 뭐야.....가끔 이런식으로 오류나나보다

 

그리고 Arraylist의 특징에 대해 좀더 살펴봐야겠다

디버깅하며 살펴보니 get함수를 쓰면 해당 번지의 원소들을 꺼내다 쓰는 pop같은 동작일줄 알았는데

생각해보니 바로 또 bfs가 잘만 되는걸 보면 그건 아닌것같고..

근데 왜 for문을 종종 지나치는거니..??

-> 잘못 생각함...get은 그런거 아님

 

이 두 의문을 해결해보겠다..  해결

풀이코드

package baekjoonWeek4;

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

public class DFSandBFS {    //백준 1260번 DFS BFS문제
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] checked;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());;
        int V = Integer.parseInt(st.nextToken());;    //정점개수,간선개수,탐색 시작점
        graph = new ArrayList<>(N + 1);
        for (int i = 0; i < N+1; i++) {     //크기 신경써라
            graph.add(new ArrayList<>());   //그래프 초기화
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            graph.get(b).add(a);    //양방향은 꼭 반대로도!!
        }
        checked = new boolean[N + 1];   //0부터ㄴㄴ1부터 N까지

        for (int i = 1; i < graph.size(); i++) {
            Collections.sort(graph.get(i)); 
        }

        dfs(V);
        System.out.println();
        checked = new boolean[N + 1];   //배열 초기화해줌
        bfs(V);

    }
    static void dfs(int x) {
        if (checked[x]) {     //이부분이 굳이 있어야하나?
            return;
        }
        checked[x] = true;
        System.out.print(x + " ");
        for (int i : graph.get(x)) {
            if (!checked[i]) {   //방문안한 정점이면 dfs수행
                dfs(i);
            }
        }
    }

    static void bfs(int x) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(x);
        checked[x] = true;
        while (!q.isEmpty()) {  //큐가 빌때까지 반복
            int n = q.remove();
            System.out.print(n + " ");
            for (int i : graph.get(n)) {
                if (!checked[i]) {
                    checked[i] = true;
                    q.add(i);
                }

            }
        }
    }
}