[백준] 1260 - DFS와 BFS (Java)

문제

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

문제 설명

문제 이름 그대로 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 Main {
	static StringBuilder result = new StringBuilder(); 
	static boolean[] check; 
	static int[][] arr;
	static int node, line, start;
	static Queue<Integer> q = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		node = Integer.parseInt(st.nextToken());
		line = Integer.parseInt(st.nextToken());
		start= Integer.parseInt(st.nextToken());
		
		arr = new int[node+1][node+1];
		check = new boolean[node+1]; 
		
		for(int i = 0 ; i < line ; i ++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			
			arr[a][b] = arr[b][a] =  1;	
		}

		dfs(start);
		result.append("\n");

		check = new boolean[node+1]; 
		bfs(start);
		
		System.out.println(result); 

	}

	public static void dfs(int start) {
		
		check[start] = true;
		result.append(start + " ");
		
		for(int i = 1 ; i <= node ; i++) {
			if(arr[start][i] == 1 && !check[i]) 
				dfs(i); 
		}
		
	}
	
	public static void bfs(int start) {
		q.add(start);
		check[start] = true;
		
		while(!q.isEmpty()) {
			
			start = q.poll();
			result.append(start + " ");
			
			for(int i = 1 ; i <= node ; i++) {
				if(arr[start][i] == 1 && !check[i]) { 
					q.add(i); 
					check[i] = true;
				}
			}
		}
		
	}

}

결과

---

정리

개념

DFS와 BFS에 대한 개념은 이전 글(파이썬으로 풀어서 정리한 글)에서 정리했으니까 생략하고 자바 개념을 정리해보겠음

StringBuilder 사용하는 이유

• String은 immutable(불변) 객체로 값을 수정하면 새로운 객체를 만든다. 따라서 메모리와 시간을 잡아먹는다.
  String+String을 하게 되면 새로운 String을 만들고 메모리 할당, 메모리 해제를 발생시키므로 연산이 많아진다면 성능적으로 좋지 않다.
• StringBuilder는 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식이기 때문에 속도도 빠르고 성능적으로도 부하가 적은 편이다.
  따라서 문자열을 많이 변경하는 경우나 긴 문자열을 더하는 상황이 있을때는 StringBuilder를 사용하는 것이 좋다!

주석있는 코드

package BaekJoon_java;

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 boj_1260 {
	static StringBuilder result = new StringBuilder(); //결과값 저장
	static boolean[] check; //노드 방문여부 체크
	static int[][] arr;
	
	static int node, line, start;
	static Queue<Integer> q = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		
		//입력 버퍼
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//공백 기준으로 문자열 자르기
		StringTokenizer st = new StringTokenizer(br.readLine());
		node = Integer.parseInt(st.nextToken());
		line = Integer.parseInt(st.nextToken());
		start= Integer.parseInt(st.nextToken());
		
		arr = new int[node+1][node+1];
		check = new boolean[node+1]; 
		
		for(int i = 0 ; i < line ; i ++) {
			StringTokenizer str = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(str.nextToken());
			int b = Integer.parseInt(str.nextToken());
			
			arr[a][b] = arr[b][a] =  1;	//양방향 간선이기 때문
		}

		//sb.append("\n");
		dfs(start);
		result.append("\n");

		//bfs 구하기 위해 방문여부 초기화
		check = new boolean[node+1]; 
		bfs(start);
		
		System.out.println(result); //결과 출력
		
	}

	public static void dfs(int start) {
		
		check[start] = true;
		result.append(start + " ");
		
		for(int i = 1 ; i <= node ; i++) {
			if(arr[start][i] == 1 && !check[i]) //현재 정점과 연결되어 있고 이전에 방문하지 않았다면
				dfs(i); //재귀함수 부르기
		}
		
	}
	
	public static void bfs(int start) {
		q.add(start);
		check[start] = true;
		
		while(!q.isEmpty()) {
			
			start = q.poll();
			result.append(start + " ");
			
			for(int i = 1 ; i <= node ; i++) {
				if(arr[start][i] == 1 && !check[i]) { //현재 정점과 연결되어 있고 이전에 방문하지 않았다면
					q.add(i); //큐에 넣기
					check[i] = true;
				}
			}
		}
		
	}

}

느낀점

DFS, BFS 자바버전도 눈에 익도록 많이 봐둬야겠다..!