저번 한 주간의 스터디 주제가 BFS&DFS였기에, 관련 문제를 하나씩 찾아봤다.. 사실 알고리즘 스터디때도 백엔드로 전향한다했지만 파이썬으로만 풀어가다가 너 백엔드로 틀었으니 JAVA로 풀어와봐ㅏ 풀어와 어쩌고 ... 라는 말을 듣기도 했고^^
JAVA라는 언어를 쓰기 시작한지 얼마 안 돼 .. 생소한 문법들도 있어서 풀었던 문제인데도 코드가 슥슥 생각 안나는 문제가 발생했다.
그래서 매일 하나씩 찾은 내용에 대해 간략하게라도 정리해보려한다 :)
우선 오늘은 백준 1260번 문제를 가지고 코드를 하나씩 뜯어보면서 String 관련 메서드들도 익혀보려한다.
우선 코드부터 !
// logic
// 1. dfs -> 재귀 or stack , bfs -> 큐로 LinkedList
// 2.
import java.util.*;
import java.io.*;
public class BFSDFS_1260 {
// StringBuilder ->
static StringBuilder sb = new StringBuilder();
// 방문했나 안했나 판정 위한 배열
static boolean[] visited;
static int[][] arr;
static int N, M, V;
// bfs
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());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
V = Integer.parseInt(st.nextToken());
// 인접행렬 방식으로 갈건데, 왜 [N+1][M+1] 행렬을 생성해줬을까.. 여기서 삽질함.
arr = new int[N+1][N+1];
visited = new boolean[N+1];
for (int i = 0; i < M; 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(V);
sb.append("\n");
visited = new boolean[N+1];
bfs(V);
System.out.println(sb);
}
public static void dfs (int V) {
visited[V] = true; // 방문처리 하고
sb.append(V + " ");
for (int i = 0; i <= N; i++) {
if (arr[V][i] == 1 && !visited[i]) {
dfs(i);
}
}
}
public static void bfs (int V) {
q.add(V);
visited[V] = true;
while (!q.isEmpty()) {
V = q.poll();
sb.append(V + " ");
for (int i = 1; i <= N; i++) {
if (arr[V][i] == 1 && !visited[i]) {
q.add(i);
visited[i] = true;
}
}
}
}
}
전형적인 dfs와 bfs 코드이다.
우선 해당 자료구조에 대한 설명은 생략하는 것으로 하고 .. 코드를 이제 하나씩 뜯어보려한다.
StringBuilder
- 자바에서 String 객체는
변경 불가능하다. 한 번 생성되면 내용을 바꿀 수 없다는 뜻이다! - StringBuilder는 변경 가능한 문자열을 만들어 주기 때문에, String을 합치는 작업 시 메모리 측면에서 내부적으로 크게 효율적이다.
BufferedReader
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));-
여기서 System.in은 콘솔에서 데이터를 입력받을 때 사용하며 inputStream 타입의 필드인 System클래스의 in 정적필드이다.
-
System.in으로 받은 Inputstream 객체에 read함수를 실행하면 1byte밖에 읽지 못해 2byte인 한글을 읽을 수 없다. =>
그래서 InputStreamReader을 사용하게 된다. -
InputStreamReader를 입력받아 문자열을 출력해준다.
-
enter가 입력되기 직전까지 받은 모든 텍스트를 저장하고 stream이 다 차거나 null이 아니라면 그 값을 계속 갖고 있는다.
-
데이터 많이 입력받는 경우, Scanner보다 메모리적으로 더 효율적이다.
InputStreamReader
- InputStream 객체를 입력으로 갖고 있어야하기 때문에,
new InputStreamReader(System.in)과 같은 형태가 되었다. - InputStreamReader가 되면서 byte -> char로 받을 수 있게 되었다.
- but, 배열 크기를 일일이 지정해줘야하기에 불편함이 있다.
StringTokenizer
- String을 쪼갤 때 사용한다.
- 우리가 받는 text는 stream이기 때문에 주욱 이어져있다. 1 2라고 입력했다면, 1과 2를 따로사용하기 위해 StringTokenizer로 쪼개준다.
readLine()
- 한 줄씩 읽어들일 때 사용한다.
- 여러 줄을 읽어들이지 않고 오직 한 줄만 읽는다.
- 만약, string 배열에 각 입력 행 별로 저장을 하고 싶은 경우가 생긴다면,
for (int i = 0; i < num.length; i++) {
s[i].br.readLine();이런 식으로! 줄 갯수만큼 반복문을 돌려줘야한다.
parseInt()
- BufferedReader는
String을 반환 - 이를 숫자처럼 반환할때 필요한 게 ! pareInt => text를 전부 int형으로 변환해준다.
nextToken()
- StringTokenizer로 쪼개주고, 변수에 하나씩 담아줄때
Integer.parseInt(st.nextToken());이런식으로 사용해주면 됨!
