[백준/1260] DFS와 BFS - 자바

제가 풀어본 문제를 올리는 것으로 코드가 전혀 완벽하지 않습니다.

태클 걸어주세요.

 

문제

 

DFS와 BFS의 기본 문제 입니다. DFS와 BFS에 대해서는 차차 알고리즘 카테고리에 포스팅 할 예정입니다.

 

코드

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 Q1260 {
	//DFS와 BFS
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bf.readLine()," ");
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		int[][] map = new int[N+1][N+1]; //0 index 신경 안쓰기 위해 1추가
		int[] confirm = new int[N+1];	//확인 배열
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(bf.readLine()," ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[x][y] = map[y][x] = 1;	//값 추가
		}
		dfs(map,confirm,K);
		confirm = new int[N+1];	//confirm 배열 초기화
		System.out.println();
		bfs(map,confirm,K);
		
	}
	public static void dfs(int[][] map,int[] confirm,int K) {
		
		System.out.print(K+ " ");	//시작값 출력
		confirm[K] = -1;	//출력 한 곳 confirm에 표시
		
		
		for(int i=0;i<map.length;i++) {
			if(map[K][i]==1 && confirm[i]==0) {	//값 받은 곳과 확인 되지 않은 곳 다시 재귀로 넣어줌
				dfs(map,confirm,i);
			}
		}
		
	}
	public static void bfs(int[][] map,int[] confirm,int K) {
		
		Queue<Integer> queue = new LinkedList<Integer>();	
		queue.add(K);	//큐에 시작값 추가
		confirm[K] = -1;	//확인배열에 시작값 체크
		
		while(!queue.isEmpty()) {
			int x = queue.poll();	//값 꺼내기
			for(int i=0;i<map.length;i++) {
				if(map[x][i] == 1 && confirm[i] != -1) {	노드가 연결되어있고 확인 안되었으면
					queue.add(i);	//큐에 넣고
					confirm[i] = -1;	//컨펌 확인
				}
			}
			System.out.print(x + " ");	//꺼낸 값 출력
		}
		
	}

}

코드설명

가장 기본적인 코드입니다. 코드에 주석설명 참고!!

 

끝!!