-
[java] 백준 알고리즘 1260번 DFS와 BFS 풀이알고리즘/백준 알고리즘 2018. 7. 9. 16:49
깊이 우선 탐색, 너비 우선 탐색에 대한 문제였다.
이 개념들은 나도 모르던 개념이라 다른 분들의 블로그를 참고해서 구현하고 공부했다.
* 풀이 소스
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576public class Baekjoon1260 {private static boolean[] visited;private static int[][] adjacencyMatrix;private static Queue<Integer> queue;private static int vertex;private static StringBuilder sb;static StringTokenizer st;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));st = new StringTokenizer(br.readLine());sb = new StringBuilder();vertex = Integer.parseInt(st.nextToken()); // 정점int edge = Integer.parseInt(st.nextToken()); // 간선int startPoint = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점의 번호visited = new boolean[vertex+1]; // 방문했는지 체크 배열Arrays.fill(visited, false);adjacencyMatrix = new int[vertex+1][vertex+1]; // 인접배열for(int i=0; i<edge; i++) {st = new StringTokenizer(br.readLine());int firstVertex = Integer.parseInt(st.nextToken());int secondVertex = Integer.parseInt(st.nextToken());adjacencyMatrix[firstVertex][secondVertex] = adjacencyMatrix[secondVertex][firstVertex] = 1;}DFS(startPoint);sb.append("\n");queue = new LinkedList<>();Arrays.fill(visited, false);BFS(startPoint);bw.write(sb.toString());bw.flush();}private static void DFS(int startPoint) {visited[startPoint] = true;sb.append(startPoint+" ");for(int i=1; i<=vertex; i++) {if(adjacencyMatrix[startPoint][i] == 1 && !visited[i]) {DFS(i);}}}private static void BFS(int startPoint) {queue.add(startPoint);visited[startPoint] = true;while(!queue.isEmpty()) {startPoint = queue.poll();sb.append(startPoint+" ");for(int i=1; i<=vertex; i++) {if(adjacencyMatrix[startPoint][i] == 1 && !visited[i]) {visited[i] = true;queue.add(i);}}}}}cs '알고리즘 > 백준 알고리즘' 카테고리의 다른 글
[java] 백준 알고리즘 9020번 골드바흐의 추측 풀이 (0) 2018.07.09 [java] 백준 알고리즘 4948번 베르트랑 공준 풀이 (0) 2018.07.09 [java] 백준 알고리즘 1929번 소수 구하기 풀이 (0) 2018.07.04 [java] 백준 알고리즘 1181번 단어 정렬 풀이 (0) 2018.07.04 [java] 백준 알고리즘 1427번 소트인사이드 풀이 (0) 2018.07.04