/ BOJ

BOJ_1260_DFS와BFS_JAVA

문제 : DFS와BFS

링크 : BOJ_1260_DFS와BFS

접근 방식

주어진 노드를 읽어들여 그래프를 만들고, 그 그래프를 DFS와 BFS를 이용한 순회 결과를 출력하면 되는 문제이다.

BFS와 DFS는 아래 링크의 게시글을 참고하여 공부하였다.

링크 : DFS와 BFS

풀이 방법

  1. 인접 행렬을 통해 주어진 인접 상태 좌표를 읽어들여 그래프를 구현한다.

  2. BFS를 이용하여 먼저 그래프를 순회한다. 인자값으로 boolean 배열(노드 수만큼), 생성한 그래프 배열, 시작할 노드를 받는다.

  3. 큐를 생성한다. 초기 노드를 방문처리하고 큐에 추가한다.

  4. 큐가 모두 비어있을 때까지 반복한다.

  5. 큐에서 값을 꺼내어 StringBuilder에 저장한다. 그 후 배열의 크기만큼 반복한다.

  6. 만약 해당 노드의 행에 아직 방문하지 않고, 인접한 노드가 있다면 큐에 해당 노드를 추가하고 방문처리한다.

  7. BFS 이용한 순회가 끝나면, DFS 이용하여 순회를 한다. 인자값으로는 BFS와 같다.

  8. DFS는 재귀로 구현한다. 먼저, 해당 노드를 방문처리하고 StringBuilder에 저장한다.

  9. 배열의 크기만큼 반복하는데, 해당 노드의 행에 아직 방문하지 않은 상태의 인접한 노드가 있다면, 해당 노드를 방문처리하고 재귀함수를 호출한다.

  10. 모든 순회가 끝나면 StringBuilder에 저장한 문자열을 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1260_DFS와BFS {
	static StringBuilder sb;
	static int N;
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));




		StringTokenizer st = new StringTokenizer(in.readLine(), " ");

		N = Integer.parseInt(st.nextToken());

		int M = Integer.parseInt(st.nextToken());

		int V = Integer.parseInt(st.nextToken());

		int[][] adjMatrix = new int[N+1][N+1];



		for(int i=0;i<M;i++) {
			st = new StringTokenizer(in.readLine()," ");
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			adjMatrix[v1][v2] = 1;
			adjMatrix[v2][v1] = 1;
		}

		boolean[] visited = new boolean[N+1];
		Arrays.fill(visited, false);
		sb = new StringBuilder();
		// dfs
		dfs(V, visited, adjMatrix);
		sb.setLength(sb.length()-1);
		sb.append('\n');

		Arrays.fill(visited, false);

		bfs(V,visited, adjMatrix);

		System.out.println(sb);

	}
	public static void bfs(int v, boolean[] visited, int[][] adjMatrix) {

		Queue<Integer> queue = new LinkedList<Integer>();

		visited[v] = true;
		queue.offer(v);

		while(!queue.isEmpty()) {
			int current = queue.poll();

			sb.append(current + " ");

			for(int i=1;i<=N;i++) {
				if(!visited[i] && adjMatrix[current][i] != 0) {
					queue.offer(i);
					visited[i] = true;
				}
			}
		}


		sb.setLength(sb.length()-1);

	}

	public static void dfs(int v, boolean[] visited, int[][] adjMatrix) {
		visited[v] = true;
		sb.append(v + " ");
		for(int i=1;i<=N;i++) {
			if(!visited[i] && adjMatrix[v][i] != 0) {
				visited[i] = true;
				dfs(i, visited, adjMatrix);
			}
		}
	}



}