[백준] 1260 : DFS와 BFS - 자바(JAVA)

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

1260번: DFS와 BFS

문제 해석

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력해야 한다.

방문할 수 있는 정점이 여러개면 정점 번호가 작은것이 우선순위이다.

정점 번호는 1번부터 N번까지이다.

---

입력

첫째 줄에 정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호 V가 주어진다.

제약조건

정점의 개수 N : 1<=N<=1,000

간선의 개수 M : 1<=M<=10,000

---

출력

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

---

문제 풀이 전 설계

우선 문제이름부터 DFS와 BFS다 보니 DFS와 BFS를 사용해야겠다는 생각을 하였습니다.

간선과 정점의 정보를 입력받는데 여기서 우선순위는 정점번호가 작은것입니다.

---

풀이하면서 고민해본 점

while(!isAllvisited()) 반복문을 통해 정점이 모두 방문되었다면 종료하도록 구현할계획이였으나 모든 정점이 연결되어 있다는 보장이 없으므로 visited를 통해 반복문을 확인하지 않습니다.

처음에는 ArrayList나 LinkedList에 정점을 순차적으로 저장하고 정점과 같은 값을 scan하여 최소값을 먼저 dfs 재귀호출할 생각이였습니다.

하지만 매번 FullScan 하는것이 너무 비효율적이라고 생각하였습니다.

//edgeList Full scan
for(Edge e: edgeList) {
	if (e.edgeA == currentEdge) {
    	//e.edgeB를 자료구조에 저장
	}
	if(e.edgeB == currentEdge) {				
    	//e.edgeA를 자료구조에 저장
	}    
}
//저장한 자료구조를 비교하여 최소값부터 dfs 호출

따라서 2차원 가변배열에서 아이디어를 얻어 하나의 차원은 정점의 번호를 저장하고, 하나의 차원에는 그 번호에 해당하는 간선의 정보들을 저장한다면 탐색을 할 때 index로 접근하기 때문에 빠르게 할 수 있을것이라고 예상됩니다.

 

자료구조에 값을 입력하는것은 한번이고 탐색은 n번 일어나기 때문에 탐색을 효율적으로 하는것이 중요하다고 생각합니다.

 

2차원 ArrayList를 만들었을때 1차원 ArrayList는 정점으로 하게된다면 만약 중간중간에 비어있는 정점이 발생하게되면 index = 현재노드 -1 으로 탐색하였을때 매칭이 적절하게 이루어지지 않을 수 있습니다.

따라서 Key-Value를 사용하고 Key에는 정점을 담고 Value에는 그 정점이 갈 수 있는 다른 정점들을 입력하도록 변경하였습니다. 

 

위의 방법들 보다는 2차원배열을 사용하면 그냥 해결이 가능했습니다.

vertex[n+1][n+1] 의 크기의 2차원배열을 선언합니다. (이때 n은 정점의 개수) , (n+1으로 하는 이유는 정점을 그대로 받기 위해)

만약 x정점과 y정점이 입력된다면 x와 y는 서로 연결되어 있음을 의미합니다.

따라서 vertex[x][y] = vertex[y][y] = 1 을 할당해주어 x, y가 서로 연결됨을 1으로 표시합니다.

다음에는 BFS, DFS를 돌며 배열의 값이 1인지 확인하여 서로 연결되어있는지 확인할 수 있습니다.

 

DFS는 재귀 호출 BFS는 큐를 사용해서 해결하였습니다.

출력 부분에서는 반복문에서 String을 더하게 되면 String은 가변적이지 않아 비효율적이므로 StringBuilder를 사용하였습니다.

---

코드

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

/*
	백준 1260 : DFS와 BFS
  	그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력해야 한다.
	방문할 수 있는 정점이 여러개면 정점 번호가 작은것이 우선순위이다.
	정점 번호는 1번부터 N번까지이다.
 */

public class DFSAndBFS {

	static List<Integer> dfsResultList = new ArrayList<Integer>();
	static List<Integer> bfsResultList = new ArrayList<Integer>();
	static int[][] vertex;
	static boolean[] visited;
	static int startEdge;
	static int edgeCount;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		readSolutionData();
		initializeVistedArray();
		DFS(startEdge);
		printResultOfDFS();
		initializeVistedArray();
		BFS(startEdge);
		printResultOfBFS();

	}

	static void readSolutionData() {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			edgeCount = Integer.parseInt(st.nextToken());
			int vertexCount = Integer.parseInt(st.nextToken());
			startEdge = Integer.parseInt(st.nextToken());
			vertex = new int[edgeCount + 1][edgeCount + 1];
			for (int i = 0; i < vertexCount; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				vertex[x][y] = vertex[y][x] = 1;
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	static void initializeVistedArray() {
		visited = new boolean[edgeCount + 1];
	}

	static void DFS(int startEdge) {
		dfsResultList.add(startEdge);
		visited[startEdge] = true;

		for (int j = 1; j <= edgeCount; j++) {
			if (vertex[startEdge][j] == 1 && visited[j] == false) {
				visited[startEdge] = true;
				DFS(j);
			}
		}
	}

	static void printResultOfDFS() throws IOException {

		StringBuilder sb = new StringBuilder();
		for (int i : dfsResultList) {
			sb.append(Integer.toString(i) + " ");
		}
		System.out.println(sb.toString());
		
	}

	static void BFS(int startEdge) {
		Queue<Integer> bfsQ = new LinkedList<Integer>();
		bfsQ.add(startEdge);
		visited[startEdge] = true;

		while (!bfsQ.isEmpty()) {
			int currentEdge = bfsQ.poll();
			bfsResultList.add(currentEdge);
			for (int j = 1; j <= edgeCount; j++) {
				if (vertex[currentEdge][j] == 1 && visited[j] == false) {
					bfsQ.add(j);
					visited[j] = true;
				}
			}
		}

	}

	static void printResultOfBFS() throws IOException {
		StringBuilder sb = new StringBuilder();
		for (int i : bfsResultList) {
			sb.append(Integer.toString(i) + " ");
		}		
		System.out.println(sb.toString());
	
	}

}