[백준] 1260번 : DFS와 BFS

문제

 

 

접근 방식

DFS와 BFS 방식으로 탐색하는 순서를 순서대로 출력하면 된다.

문제를 대충 보고 인접 리스트로 풀었더니 예제가 틀리길래

다시보니 작은 번호의 정점부터 방문하는 조건이 있어서 인접 행렬로 바꿔 풀었다.

 

양방향 그래프이기 때문에 양쪽 간선에 모두 이동할 수 있게

인접 행렬에 표시해주고 DFS와 BFS 순서대로 탐색을 진행해주면서

정점에 방문할 때마다 출력해주면 된다.

 

풀이

public class Main {

	private static int n;
	private static int[][] nearArr;
	private static boolean[] isVisited;
	private static StringBuilder sb = new StringBuilder();

	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());
		int m = Integer.parseInt(st.nextToken());
		int v = Integer.parseInt(st.nextToken());

		isVisited = new boolean[n + 1];
		nearArr = new int[n + 1][n + 1];

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			nearArr[x][y] = 1;
			nearArr[y][x] = 1;
		}

		dfs(v);
		sb.append("\n");

		bfs(v);

		System.out.println(sb);
	}

	private static void bfs(int start) {
		isVisited = new boolean[n + 1];

		Queue<Integer> q = new ArrayDeque<>();

		q.offer(start);
		isVisited[start] = true;
		sb.append(start).append(" ");

		while (!q.isEmpty()) {
			int cur = q.poll();

			for (int i = 1; i <= n; i++) {
				if (isVisited[i] || nearArr[cur][i] != 1) continue;
				q.offer(i);
				isVisited[i] = true;
				sb.append(i).append(" ");
			}
		}
	}

	private static void dfs(int cur) {
		isVisited[cur] = true;
		sb.append(cur).append(" ");

		for (int i = 1; i <= n; i++) {
			if (isVisited[i] || nearArr[cur][i] != 1) continue;
			dfs(i);
		}
	}
}