[백준 : 실버2] DFS와 BFS(1260번) : Java

이번문제는 그야말로 DFS와 BFS의 구현을 하는 내용이였다.

 

첨에 문제가 뭔소린지 이해를 못했지만 입력문을 자세히보니 무슨소린지 이해가 갔다 일단 문제부터 살펴보자.

 

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

 

 

문제 해설

 

뭐 사실 해설 할게 없지만 난 입력문이 뭔소린지 이해를 못했다. 따라서 설명을 하자면

가장 위에 있는 것은

정점개수, 간선개수, 시작정점 이렇게 입력 받은것이고

그 밑에부터는 간선들을 입력 받은것이다.

 

그리고 출력문을 보면 수가 작은것부터 방문을 하는데 이부분을 해결하기위해선 인접리스트 정렬이 필요하다.

 

 

이번 문제는 사실 DFS, BFS 구현 부분이기때문에 소스만 올려두고 자세한 설명은 내가 이전에 올려두었던 

DFS와 BFS 설명 링크를 올려두겠다.

 

DFS 설명

https://wpioneer.tistory.com/130?category=1023663 

[자료구조] DFS(Depth First Search) Java 구현

 

BFS 설명

https://wpioneer.tistory.com/131?category=1023663 

[자료구조] BFS(Breadth First Search) Java 구현

 

 

소스

import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Run {
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Run a = new Run();
		Scanner sc = new Scanner(System.in);
		System.out.println("정점 개수, 간선개수, 시작 정점을 차례대로 입력하세요");
		int node = sc.nextInt();
		int m = sc.nextInt();
		int start = sc.nextInt();
		
		
//		int node = 4;
//		int m = 5;
//		int start = 1;
//		
//		int graph[][] = {{1,2},{1,3},{1,4},{2,4},{3,4}};
		
		System.out.println("정점 개수 : "+node+"\n간선개수 : "+m+"\n시작 정점 : "+start);
		
		boolean[] visit1 = new boolean[node+1];
		boolean[] visit2 = new boolean[node+1];
		
		//인접리스트를 이용해서 값을 대입
		LinkedList<Integer>[] list = new LinkedList[node+1];
		for(int i = 0; i<=node;i++) {
			list[i] = new LinkedList();
		}
		
		System.out.println("간선들을 입력하세요");
		//인접리스트에 간선을 넣었다.
		for(int i = 0; i<m;i++) {
			int node1 = sc.nextInt();
			int node2 = sc.nextInt();
			
			list[node1].add(node2);
			list[node2].add(node1);
		}
		
		//LinkedList 안에 들어가 있는 내용들 정렬
		for(int i = 0; i<= node;i++) {
			Collections.sort(list[i]);
		}
		
		for(int i = 0; i<list.length;i++) {
			System.out.println("node "+i+" 와 인접 노드 : "+ list[i]);
		}
		
		a.dfs(visit1,list,start);
		System.out.println();
		a.bfs(visit2,list,start);
	}

	public void bfs(boolean[] visit, LinkedList<Integer>[] list, int start) { //너비우선 탐색
		// TODO Auto-generated method stub
		
		Queue<Integer> que = new LinkedList<>();
		
		que.add(start); //queue에 값을 추가
		visit[start] = true; //해당 정점 방문 처리
		while(!que.isEmpty()) { //queue가 비어 있을때까지 진입
			int su = que.poll(); //큐에 해당 지점 뺀다.
			System.out.print(su+" ");
			for(int i = 0; i< list[su].size();i++) {
				int link = list[su].get(i);
				if(!visit[link]) {
					visit[link] = true;
					que.add(link); //해당 정점과 연결 되어 있는애들을 큐에 추가해준다.
				}
				
			}
			
		}
		
	}

	public void dfs(boolean[] visit, LinkedList<Integer>[] list, int start) { //깊이 우선 탐색
		// TODO Auto-generated method stub
		visit[start] = true; //출발지점 방문 처리
		System.out.print(start+" "); //방문된점 출력
		for(int i = 0; i<list[start].size();i++) { //방문된 지점과 연결된 정점에 접근
			int link = list[start].get(i);
			if(!visit[link]) {
				dfs(visit,list,link);
			}	
		}
		
	}
}