반응형
그래프 사용이유
1. 여러 객체간의 관계를 논리적이고 시각적으로 표현할 수 있음
└ 두 개체간의 경로, 연결여부 등을 표시함
2. 경로 탐색이나 최단 경로 계산을 할 수 있음
StringTokenizer : 문자열을 구분자(delimiter)로 분리하여 토큰(token)으로 나누는 클래스. 구분자를 지정하지 않으면 기본적으로 공백을 구분자로 사용
hasMoreTokens(): 다음 토큰이 있는지 확인하여 boolean을 반환합니다.
nextToken(): 다음 토큰을 반환하고, 토큰이 없으면 예외를 발생시킵니다.
countTokens(): 남아 있는 토큰의 개수를 반환합니다.
BufferedReader : 문자 데이터를 버퍼에 담아 한 번에 읽고 처리
InputStreamReader : System.in과 같은 콘솔입력 등을 바이트 스트림을 문자 스트림으로 변환
BufferedReader는 단순히 데이터를 읽어와 한 줄 단위로 문자열로 반환하는 반면, Scanner는 입력을 토큰화하고 데이터 타입에 맞게 변환
StringBuilder 사용해서 한번 출력하는게
매번 System.out.print 찍는것보다 미세하게 빠름
배열 생성시 정점 개수로 하느냐, 간선 개수로 하느냐 때문에 메모리 초과 떴었음
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int n, m, v; //n=정점의 개수, m=간선의 개수, v=시작 정점 번호
public static int[][] arr;
public static boolean[] isVisited;
public static Deque<Integer> queue = new ArrayDeque<>();
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer strtk = new StringTokenizer(br.readLine());
n = Integer.parseInt(strtk.nextToken());
m = Integer.parseInt(strtk.nextToken());
v = Integer.parseInt(strtk.nextToken());
arr = new int[n+1][n+1]; //간선 배열
isVisited = new boolean[n+1]; //정점 방문 여부 배열
for(int i=0; i<m ; i++){ //간선 읽어서 배열에 저장
strtk = new StringTokenizer(br.readLine());
int a = Integer.parseInt(strtk.nextToken());
int b = Integer.parseInt(strtk.nextToken());
arr[a][b] = arr[b][a] = 1; //선이 연결된 경우 1
}
dfs(v);
Arrays.fill(isVisited,false);
System.out.print("\n");
bfs(v);
}
//depth first search
public static void dfs(int start){
isVisited[start] = true;
System.out.print(start + " ");
for(int i=1; i<= n; i++){
//간선이 연결되어 있고 방문한적 없는 정점인 경우
if(arr[start][i] == 1 && !isVisited[i]){
dfs(i);
}
}
}
//breadth first search
public static void bfs(int start){
isVisited[start] = true;
queue.offer(start);
while(!queue.isEmpty()){
int s = queue.poll();
System.out.print(s + " ");
for(int i=1; i<=n; i++){
if(arr[s][i] == 1 && !isVisited[i]){
queue.offer(i);
isVisited[i] = true;
}
}
}
}
}반응형