99클럽 코테 스터디 5일차 TIL BFS(알고리즘 수업 - 너비 우선 탐색 1)

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

 

어제와 동일한데 DFS가 아닌 BFS로 푸는 문제였다. 같은 깊이의 정점을 우선 탐색하는!

오늘은 어제와 같은 실수를 하지 않았다! 방문하는 순서대로 순서 잘 저장함.

어제랑 너무 비슷해서 더 할말이 없다,,

https://dev-zsunny.tistory.com/25

99클럽 코테 스터디 4일차 TIL DFS(알고리즘 수업 - 깊이 우선 탐색1)

 

제출 코드는 아래와 같음

 

package STUDY;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;

public class Day05_BOJ_24444 {

    static int n, m, r;
    static int cnt;
    static int[] visited;
    static List<Integer>[] list;

    public static void bfs(int x){
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        visited[x] = ++cnt;
        while(!q.isEmpty()){
            int p = q.poll();
            for(int i=0; i<list[p].size(); i++){
                int now = list[p].get(i);
                if(visited[now] != 0) continue;
                q.add(now);
                visited[now] = ++cnt;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        list = new ArrayList[n+1];
        for(int i=0; i<n+1; i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
            list[y].add(x);
        }

        for(int i=0; i<n+1; i++){
            Collections.sort(list[i]);
        }

        visited = new int[n+1];
        bfs(r);

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<n+1; i++){
            sb.append(visited[i] + "\n");
        }
        System.out.println(sb.toString());
    }
}