[JAVA][백준] 1260. DFS와 BFS

🔗링크

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

---

📑문제

---

🤔접근 방법

사실 아직 DFS / BFS 구현하는게 어려워서 수업시간에 적어놨던 코드 컨닝하면서 작성했다..
N과 M 시리즈 풀면서 DFS는 많이 익숙해졌는데 BFS는 한참 먼 사이 같다 ㅠ ㅠ
더 열심히 해야지!!!

다음 번엔 인접 행렬 말고 인접 리스트로 구현해보고 싶다.

---

🗝️코드

package boj;

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

public class Boj_1260_DFS와BFS {

	static int N, M, V;
	static int[][] map;
	static boolean[] visited;
	static StringBuilder sb = new StringBuilder();
	static Queue<Integer> queue = new LinkedList<>();

	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()); // 정점의 개수
		M = Integer.parseInt(st.nextToken()); // 간선의 개수
		V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점

		// 인접행렬을 만들기 위해 2차원 배열을 만들어줌
		// 인덱스를 노드 번호 그대로 쓰기 위해 N+1
		map = new int[N + 1][N + 1];
		visited = new boolean[N + 1];

		for (int i = 0; i < M; i++) { // 간선의 개수만큼
			st = new StringTokenizer(br.readLine(), " ");

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			map[a][b] = map[b][a] = 1; // 인접행렬, 간선 표시해주기

		}
		dfs(V);
		sb.append("\n");
		visited = new boolean[N + 1]; // 방문처리 배열 초기화
		bfs(V);
		System.out.println(sb);

	}// main

	static void dfs(int v) {
		visited[v] = true; // 시작정점 방문체크
		sb.append(v + " ");

		for (int i = 0; i <= N; i++) {
			// 현재 내 위치의 노드와 인접해있고 (간선이 있고) 방문하지 않았다면 재귀
			if (map[v][i] == 1 && !visited[i])
				dfs(i);
		}

	}// dfs

	static void bfs(int v) {
		queue.add(v); // 시작정점 큐에 넣어주기
		visited[v] = true; // 방문체크

		// 큐가 비어있지 않은 동안(모든 노드 방문할 때까지)
		while (!queue.isEmpty()) {

			int now = queue.poll(); // 방문 노드 꺼내고
			sb.append(now + " ");

			for (int i = 1; i <= N; i++) {
				// now와 인접해있고 방문하지 않았다면
				if (map[now][i] == 1 && !visited[i]) {
					queue.add(i); // q에 추가 ( poll 아님!! )
					visited[i] = true; // 방문처리
					// 여기서 방문처리 안하면 방문이 계속 반복될 수 있으니 주의하기
				}
			}

		}

	}// bfs

}