1260 DFS와 BFS

728x90

한동안 쉬었던 알고리즘을 다시 시작했다...

한 때에는 익숙했던 것들이지만 몇개월만에 DFS/BFS 조차도 헷갈리는 상태였다.

DFS와 BFS의 기본을 찾기위해서 ..! 선택한 문제이다 ㅎ

 

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

public class Main {
	
	static boolean visited[]; // 해당 숫자에 다녀갔는지 확인하는 boolean 배열 !
	static List<Integer> [] list;
	
	public static void main (String [] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 정점의 갯수
		int M = Integer.parseInt(st.nextToken()); // 간선의 갯수
		int V = Integer.parseInt(st.nextToken()); // 시작정점의 수
		
        //정점은 1 부터이기에 index 0부터인 것을 신경쓰지 않으려 배열의 길이를 N+1로 설정했다.
		list = new ArrayList[N+1]; // N+1짜리 배열 ~!
		
		for(int i = 1; i<N+1; i++) { // index 1부터 N+1직전 ( N까지 ) 반복하면서 !
			list[i] = new ArrayList<>();	//모든 index마다 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());
			
			list[a].add(b);
			list[b].add(a);
		}
		
        // 방문할 수 있는 정점이 여러개라면 작은 수부터 방문하기 위해서 배열을 정렬해주고 !
		for(int i = 1; i<N+1; i++) {
			Collections.sort(list[i]);
		}
		
		visited = new boolean [N+1]; // visited를 N+1길이로 선언해주고 !
		dfs(V); // 시작정점인 수 V를 가지고 dfs시작! 46번 줄로 가보자
		System.out.println();
		visited = new boolean [N+1]; // 이미 한번 사용했었기때문에 새로운 boolean 배열을 만들어준다 !
		bfs(V); // 시작정점인 수 V를 가지고 bfs 시작 ! 58번 줄로 가보자
		
	}

	public static void dfs(int v) { // dfs 함수 시작
		visited[v] = true;	// 일단 visited의 V자리를 true ( 방문상태 ) 로 만들어준다.
		System.out.print(v+" ");	// 출력도 미리 해주고 !
		
        //// V에 해당하는 list[V]의 크기 ( V와 연결되어있는 모든 정점의 수 ) 만큼 반복하면서 !
		for(int i = 0; i<list[v].size(); i++) { 
			int num = list[v].get(i); // 각 정점들의 수를 가져와서 ~
			if(visited[num]) continue; // 이미 방문한 곳이라면 지나가주고 !
			dfs(num);	// 아직 방문하지 않은 곳이라면 해당 숫자를 인자값으로 dfs()를 시킨다!
		}
	}

	public static void bfs(int v) {	//bfs 함수 시작
		Queue<Integer> q = new LinkedList<>();	// bfs를 위해 큐를 만들어 준다.
		
		q.offer(v);	// 일단 인자값으로 가져온 v를 넣어주고 !
		
		while(!q.isEmpty()) { // 이 큐가 싹 빌때까지 반복해준다 !
			int num = q.poll(); // 숫자하나를 꺼내서 ~
			if(visited[num]) continue; // 이미 방문한 곳이라면 지나가고,
            // 방문하지 않은 곳이라면
			visited[num] = true; // 방문처리해주고
			System.out.print(num+" "); // 해당숫자 + 여백 출력해주고 
			for(int i = 0; i<list[num].size(); i++) { // dfs와 같이 인접한 수들을 
				int n = list[num].get(i); // 차례로 데려와서 ~
				if(!visited[n]) { // 방문하지 않은 숫자라면 큐에 넣어준다 !
					q.offer(n);
				}
			}
		}
	}
}

 

설명을 위해 주석을 달면서 보니 bfs에서 큐에 들어갈 때에 이미 들어가있는 숫자라면 넣지않는 조건을 추가하면 더 좋을 것 같다는 생각을 했다.

 

추가 고려사항 있다면 알려주시면 감사합니다 ~!

 

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

1260번: DFS와 BFS