[백준] 1260번 : DFS와 BFS - JAVA [자바]

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

---

dfs와 bfs 알고리즘을 구현하는 문제이다.

작은 수부터 탐색하기 위해서는 한 노드에서 갈 수 있는 노드를 저장한 배열을 오름차순으로 정렬하면 된다.

for (int i = 0; i < M; i++) {
    String line1 = br.readLine();
    String[] split1 = line1.split(" ");
    
    int from = Integer.parseInt(split1[0]);
    int to = Integer.parseInt(split1[1]);
    
    edgeList[from].add(to);
    edgeList[to].add(from);
    
    // 새로운 갈 수 있는 노드를 추가할 때 마다
    // 작은 수 부터 탐색하기 위해 정렬해서 저장한다.
    Collections.sort(edgeList[from]);
    Collections.sort(edgeList[to]);
}

먼저 dfs 알고리즘이다.

private static void dfs(int start) {
	visited[start] = true;
    sb.append(start).append(" ");
    
    for (int to : edgeList[start]) {
    	if (!visited[to]) {
    		dfs(to);
		}
	}
}

1. 처음 시작은 주어지기에 start를 방문 처리 해준다.
2. 정답에 start를 이어 붙인다.
3. start 노드에서 갈 수 있는 노드들 중 방문하지 않은 노드를 방문한다.
4. dfs 알고리즘의 start 인자를 현재 start에서 간 노드(to)로 변경하여 대입한다.

다음으로 bfs 알고리즘이다.

private static void bfs(int start) {
	bfs.add(start);
    visited[start] = true;

	while (!bfs.isEmpty()) {
    	start = bfs.poll();
        sb.append(start).append(" ");
        for (int to : edgeList[start]) {
        	if (!visited[to]) {
            	bfs.add(to);
                visited[to] = true;
			}
        }
	}
}

먼저 bfs라는 큐를 정의한다.

1. 큐에 현재 start 값을 add 한다.
2. start를 방문처리 해준다.
3. 큐에서 제일 앞에 값을 poll 해준다.
4. 그 값을 start에 대입하고 정답에 붙인다.
5. start 에서 갈 수 있는 노드를 탐색한다.
6. 아직 방문하지 않았다면 방문하고 큐에add 해준다.
7. 큐가 빌때 까지 반복한다.

---

public class bj1260 {

    public static int N;
    public static int M;
    public static int start;
    public static ArrayList<Integer>[] edgeList;
    public static boolean[] visited;
    public static int[] dfsArr;
    public static Queue<Integer> bfs = new ArrayDeque<>();
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();
        String[] split = line.split(" ");

        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);
        start = Integer.parseInt(split[2]);
        dfsArr = new int[N];
        edgeList = new ArrayList[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < N + 1; i++) {
            edgeList[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            String line1 = br.readLine();
            String[] split1 = line1.split(" ");
            int from = Integer.parseInt(split1[0]);
            int to = Integer.parseInt(split1[1]);
            edgeList[from].add(to);
            edgeList[to].add(from);
            // 작은 수 부터 탐색하기 위해
            Collections.sort(edgeList[from]);
            Collections.sort(edgeList[to]);

        }

        dfs(start);
        sb.append("\n");
        visited = new boolean[N + 1];
        bfs(start);

        bw.write(sb + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int start) {
        visited[start] = true;
        sb.append(start).append(" ");

        for (int to : edgeList[start]) {
            if (!visited[to]) {
                dfs(to);
            }
        }
    }

    private static void bfs(int start) {
        bfs.add(start);
        visited[start] = true;

        while (!bfs.isEmpty()) {
            start = bfs.poll();
            sb.append(start).append(" ");
            for (int to : edgeList[start]) {
                if (!visited[to]) {
                    bfs.add(to);
                    visited[to] = true;
                }
            }
        }

    }
}