알고리즘(BOJ)/Silver

백준 - 1260(DFS&BFS)

ch.0 2023. 1. 21. 15:08


문제 분석

DFS에서도 방문여부를 체크 해줘야 했다. 이미 출력한 정점은 또다시 방문하지 않기 위함이다.

처음에는 배열에 정점의 값을 넣어주려고 했지만, 배열의 위치에 1을 넣어주는게 일반적인것 같다.

 

탐색순서

전체 소스

import java.io.*;
import java.util.*;

public class Main {

	static int[][] array;
	static int repeat;
	static int dat;
	static int[] visited;
	static boolean[] check;

	public static void dfs(int point) {

		visited[point] = 1;

		System.out.print(point + " ");

		for (int i = 1; i <= dat; i++) {
			if (array[point][i] == 1 && visited[i] == 0) {
				dfs(i);
			}
		}

	}

	public static void bfs(int point) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(point);
		check[point] = true;
		


		while (!q.isEmpty()) {
			point = q.poll();
			System.out.print(point + " ");
			for (int i = 1; i <= dat; i++) {
				if (array[point][i] == 1 && check[i] == false) {
					q.offer(i);
					check[i] = true;
				}
			}
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		dat = Integer.parseInt(st.nextToken());
		repeat = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());

		array = new int[dat + 1][dat + 1];
		visited = new int[dat + 1];
		check = new boolean[dat + 1];

		for (int i = 0; i < repeat; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			array[x][y] = array[y][x] = 1;
		}

		dfs(start);
		System.out.println();
		bfs(start);

	}
}