[JAVA] 백준 알고리즘 1260번 문제풀이 (DFS와 BFS)

 

 

 

 

 

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

1260번: DFS와 BFS

 

 

 

 

● DFS와 BFS (1260번)

 

 

 

 

 

 

 

import java.util.*;

public class Main {
	static ArrayList<Integer>[] a;
	static boolean[] c;

	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int start = sc.nextInt();
		a = (ArrayList<Integer>[]) new ArrayList[n + 1];
		for (int i = 1; i <= n; i++) {
			a[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			a[u].add(v);
			a[v].add(u);
		}
		for (int i = 1; i <= n; i++) {
			Collections.sort(a[i]);
		}
		c = new boolean[n + 1];
		dfs(start);
		System.out.println();
		c = new boolean[n + 1];
		bfs(start);
		System.out.println();
	}

	public static void dfs(int x) {
		if (c[x]) {
			return;
		}
		c[x] = true;
		System.out.print(x + " ");
		for (int y : a[x]) {
			if (c[y] == false) {
				dfs(y);
			}
		}
	}

	public static void bfs(int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.add(start);
		c[start] = true;
		while (!q.isEmpty()) {
			int x = q.remove();
			System.out.print(x + " ");
			for (int y : a[x]) {
				if (c[y] == false) {
					c[y] = true;
					q.add(y);
				}
			}
		}
	}

}

* 소스풀이

​

Arraylist인 a와 boolean배열 c를 static으로 만들어줍니다.

main메소드에서 정점의 갯수(n)와 간선의 갯수(m), 시작정점(start)를 입력받아줍니다.

입력한 정점의 갯수만큼 a배열에 Arraylist[] 배열을 만들어주고, 안전하게 형변환을 했습니다.

for문을 통해 각각의 정점을 입력받아줍니다.

입력받은 정점은 Arraylist가 각각 있기에 똑같이 인접 리스트방식으로 u,v에 교차로 add해줍니다.

정렬을해주고, dfs()메소드로 start를 파라미터로 넘겨줍니다.

dfs()메소드에서 c배열이 true(방문했다면) return해주고 그렇지않다면 true로 만들어주고

a배열에 arraylist에있는 것들을 하나씩 방문여부확인하고 false면 재귀함수로 계속 반복합니다.

다음으로, bfs()메소드도 동일하게 넘겨줍니다.

bfs()메소드에서 Queue를 생성해주고, q인스턴스에 add해주고, 해당 정점 방문여부 c배열을

true를 저장해줍니다.

while반복문을통해 dfs와 동일하게 c배열이 false라면 true로 바꿔주고 add해줍니다.

 

 

< 백준알고리즘 강의를 보고 참고하였습니다! >

 

 

---