[백준] 1260 DFS와BFS (자바/java)

문제

- 문제 출처 : https://www.acmicpc.net/problem/1260

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 

1 2 4 3
1 2 3 4

예제 입력 2 

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2 

3 1 2 5 4
3 1 4 2 5

예제 입력 3 

1000 1 1000
999 1000

예제 출력 3 

1000 999
1000 999

 

 

---

 

먼저, 문제에서 주어지는 그래프는 방향그래프나 가중치그래프라는 언급이 없기 때문에 무방향 그래프라고 생각한다.

참조 :2021.12.22 - [알고리즘/자바 알고리즘 문제풀이: 코딩테스트 대비] - [알고리즘/java] 경로탐색(DFS 인접리스트, ArrayList)

 

 

			graph.get(v1).add(v2);
			graph.get(v2).add(v1);

: 그래프를 인접리스트를 이용해 표현하고 정점을 서로 연결해준다.

 

 

 

	// 이동할 정점이 여러 개라면 작은 정점부터 이동하도록 정렬.
		for (int i = 1; i <= N; i++) {
			Collections.sort(graph.get(i));
		}

 

: 그리고 문제에서  "단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, .." 라고 했으므로 dfs와 bfs를 하기 전에 정점리스트를 정렬시켜 작은 것부터 방문할 수 있도록 한다.

 

 

이제 인접리스트로 만들어진 그래프를 이용하여 dfs와 bfs 구현을 하면 된다.

 

 

< DFS와 BFS 전체코드 >

public class Main {

	private static StringBuilder sb;
	private static ArrayList<ArrayList<Integer>> graph;
	private static boolean[] check;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		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()); // 탐색 시작 정점 번호

		graph = new ArrayList<ArrayList<Integer>>();

		// 정점 방문 여부 체크 배열
		check = new boolean[N + 1];

		// 정점 개수만큼 ArrayList 안에 ArrayList 만들기.
		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());

			// 정점 서로 연결.
			graph.get(v1).add(v2);
			graph.get(v2).add(v1);
		}

		// 이동할 정점이 여러 개라면 작은 정점부터 이동하도록 정렬.
		for (int i = 1; i <= N; i++) {
			Collections.sort(graph.get(i));
		}

		sb = new StringBuilder();

		dfs(V);
		Arrays.fill(check, false); // bfs를 위해 check배열 초기화
		sb.append("\n");

		bfs(V);
		System.out.println(sb);

	}

	static void dfs(int v) {
		if (check[v] == true) { // 방문한 정점이면 종료
			return;
		}

		else {
			check[v] = true; // 방문 처리
			sb.append(v + " ");

			// 각 정점과 연결된 정점을 탐색
			for (int i = 0; i < graph.get(v).size(); i++) {
				int nv = graph.get(v).get(i);
				if (!check[nv]) { // 각 정점에 연결된 정점(들)을 방문했는지 여부
					dfs(nv);
				}
			}

			
		}

	}

	static void bfs(int v) {
		Queue<Integer> q = new LinkedList<>();

		q.offer(v); // 탐색 시작 정점 큐에 삽입
		check[v] = true;

		while (!q.isEmpty()) {
			v = q.poll(); // 큐에 추가된 정점 가져오기.
			sb.append(v + " ");

			for (int i = 0; i < graph.get(v).size(); i++) {
				int nv = graph.get(v).get(i);
				if (!check[nv]) { // 방문하지 않은 정점.
					q.offer(nv);
					check[nv] = true; // 방문처리
				}
			}
		}

	}

}