지나공 : 지식을 나누는 공간
Java 코딩테스트를 위한 코드 총정리 본문
계속 추가되어 수정될 예정입니다.
- 입력받기 (BufferedReader, Scanner)
- 컬렉션 프레임워크와 종류, 차이, 주요 메소드
- 스택, 큐 등
- 해시, 해시 순회 등
- 다양한 정렬 : comparable, comparartor, stream 활용 등
- BFS, DFS
- 투포인터
- 다익스트라
- MST : 크루스칼, 프림
입력 받기
Scanner와 BufferedReader 차이
1) Scanner의 버퍼 크기는 1024 chars, BufferedReader는 8192 chars
2) BufferedReader는 문자열을 단순히 읽고 저장하지만 Scanner는 문자열을 구분해서 분석할 수 있다.
3) BufferedReader는 동기화가 지원되어 Thread-safe하고 Scanner는 지원되지 않는다.
4) BufferedReader는 즉시 IOException을 던지지만 Scanner는 숨긴다.
차이 설명
1) 의 특징에 따라, 큰 파일을 읽을 때 BufferedReader가 좋다.
2) 는 둘의 메소드 차이다.
Scanner는 구문기호를 쓸 수 있어서, 아래처럼 사용할 수 있다.
public static void main(String [] args) {
Scanner sc = new Scanner("Anna Mills/Female/18");
sc.useDelimiter("/"); // /로 쪼갬
while(sc.hasNext()) {
System.out.println(sc.next());
}
sc.close();
}
/*
Anna Mills
Female
18
*/3) 의 특징에 따라, 동기화가 지원되는 BufferedReader는 멀티 스레드에서 안전하고 그렇지 않은 Scanner는 안전하지 않다. 멀티 스레드는 여러 스레드가 같은 프로세스 내의 공유 자원을 만지는데 여기서 동시에 공유자원에 접근해도 프로그램 실행에 문제가 없어야 한다.
4) 는 그냥 그렇다는 말이다. ㅎㅎ
사용하기
띄어쓰기 유무에 따라 다양하게 사용해보자.
(1) BufferedReader 띄어쓰기가 있는 것과 없는 것
/*
5 6
101010
111111
000001
111111
111111
* */
public class Main{
public static int[][] map = new int[200][200];
public static int n, m;
public static void main(String [] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//띄어쓰기가 있는 부분 읽기
String [] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
//띄어쓰기 있는 부분 읽기
for(int i = 0; i < n; i++) {
String input2 = br.readLine();
for(int j = 0; j < m; j++) {
map[i][j] = input2.charAt(j) - '0';
}
}
}
}/*
5 6
1 0 1 0 1 0
1 1 1 1 1 1
0 0 0 0 0 1
1 1 1 1 1 1
1 1 1 1 1 1
* */
public class Main{
public static int[][] map = new int[200][200];
public static int n, m;
public static void main(String [] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//띄어쓰기가 있는 부분 읽기
String [] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
//띄어쓰기 있는 부분 또 읽기
for(int i = 0; i < n; i++) {
String [] input2 = br.readLine().split(" ");
for(int j = 0; j < m; j++) {
map[i][j] = Integer.parseInt(input2[j]);
}
}
}
}
(2) Scanner 띄어쓰기가 있는 것과 없는 것
주의할 점은 nextInt()를 한 뒤에 nextLine()을 할 때다. nextInt()는 \n이나 " "(공백) 바로 직전까지의 숫자를 입력받는다. 그리고 nextLine()은 \n까지 포함해서 입력을 받는다. 그래서 예를 들어 아래와 같이 입력한다면
12
example
실제 구성은 12 \n example인건데, 여기서 nextInt()를 한 뒤 nextLine을 하면 아래와 같이 받아진다.
nextInt() //개행문자 전까지의 숫자 12가 받아짐
nextLine() //12 뒤에 남은 개행문자가 받아지고 끝
nextLine() //한번 더 해줘야 example이 받아짐.
nextLine()을 한번 더 해서 버퍼 상태를 제거해 줘야 한다!!
/*
5 6
101010
111111
000001
111111
111111
* */
public class Main{
public static int[][] map = new int[200][200];
public static int n, m;
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine(); //버퍼 비우기
for(int i = 0; i < n; i++){
String str = sc.nextLine();
for(int j = 0; j < m; j++) {
map[i][j] = str.charAt(i) - '0';
}
}
}
}/*
5 6
1 0 1 0 1 0
1 1 1 1 1 1
0 0 0 0 0 1
1 1 1 1 1 1
1 1 1 1 1 1
* */
public class Main{
public static int[][] map = new int[200][200];
public static int n, m;
public static void main(String [] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//띄어쓰기가 있는 부분 읽기
n = sc.nextInt();
m = sc.nextInt();
//띄어쓰기 있는 부분 또 읽기
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
map[i][j] = sc.nextInt();
}
}
}
}컬렉션 프레임워크
java.util 패키지에 있는 컬렉션 프레임워크에 대해 알아보자.
배열은 크기가 고정적이라서 불편함이 있다. 이를 해결하기 위해 널리 알려져 있는 자료구조를 바탕으로 객체나 데이터를 효율적으로 관리(추가, 삭제, 검색, 저장)할 수 있는 자료구조를 만들어 놨다.
List 컬렉션
List는 컬렉션 프레임워크를 상속받고 있고, 객체를 일렬로 늘어놓은 구조를 가진다.
- 객체 자체가 아닌 객체의 번지를 참조한다.
- 동일한 객체를 중복 저장하면 동일한 번지가 참조된다.
- 대표적인 클래스로 ArrayList, Vector, LinkedList가 있다. 차이도 알아볼 예정이다.
List의 공통 메소드
| boolean add(E e) | 맨 끝에 객체 추가 |
| void add(int index, E element) | 주어진 인덱스에 객체 추가 |
| set(int index, E e) | 주어진 인덱스에 있는 객체를 주어진 객체로 바꿈 |
| boolean contains(Object o) | 주어진 객체가 있는지 반환 |
| E get(int index) | 주어진 인덱스에 저장된 객체를 반환 |
| isEmpty() | 컬렉션이 비어있는지 확인 |
| int size() | 객체 수 반환 |
| E remove(int index) | 인덱스로 객체 삭제 |
| void clear() | 모든 객체 삭제 |
| boolean remove(Object o) | 주어진 객체를 삭제 |
ArrayList와 Vector와 LinkedList 차이
1. Vector
자바1에서 먼저 등장한 애이고, 동기화를 보장해서 공유자원이나 복수의 사용자가 존재할 때 좀 더 안전하게 프로그램을 작성할 수 있다. 하지만 하나의 스레드가 하나의 자원을 이용하는 경우 오히려 성능 저하가 발생한다. 그리고 공간이 모자랄 때 모자란공간의 두 배 만큼 공간을 확보하기 때문에 메모리를 많이 잡아먹는다는 단점이 있다.
2. ArrayList
Array라는 이름이 들어간 것에서 알 수 있듯 인덱스가 있어서 검색에 용이하다.
Vector와 달리 동기화를 보장하지 않고 공간이 모자랄 때는 모자란 만큼만 확보한다.
그러나 삽입/삭제를 할 때 전부 밀거나 당겨야 해서 삽입과 삭제가 빈번한 데이터에 부적합하다.
3. LinkedList
노드들이 줄줄이 연결된 리스트고, 맨 마지막을 검색하려면 처음부터 끝까지 노드를 줄줄이 이동해야 해서 검색에 부적합하다. 하지만 삽입/삭제에서는 중간 노드의 주소지만 바꾸면 되니까 삽입/삭제가 빈번한 데이터에 적합하다.
ArrayList와 LinkedList를 활용한 Stack, Queue 구현
큐의 주요 메소드.
| 큐(Queue) by LinkedList | |
| boolean offer(E e) | 추가, 실패 시 false 리턴 |
| E poll() | 맨 앞의 원소를 리턴한 뒤, 그걸 삭제. 빈 큐면 null 반환 |
| E peek() | 맨 앞의 원소 리턴. 빈 큐면 null 반환 |
| 스택(Stack) by Stack | |
| E push(E item) | 추가. 추가된 원소를 리턴 |
| E pop() | 맨 위의 원소를 삭제 |
| E peek() | 맨 위의 원소를 리턴만 함. 스택이 비어있으면 exception |
package com.company.study.dfs_bfs;
import java.util.*;
public class StackQueue {
public static void main(String[] args) {
}
public static void makeStack() {
Stack<Integer> s = new Stack<>();
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();
while (!s.isEmpty()) {
System.out.println(s.peek());
s.pop();
}
}
public static void 스택메소드들() {
Stack<Integer> s = new Stack<>();
s.push(5);
s.push(2);
s.push(3);
s.push(7);
s.pop();
s.push(1);
s.push(4);
s.pop();
s.clear(); // 스액 전체 값 없앰.
s.peek(); //스택 최상단 값 출력
}
public static void makeQueue(){
Queue<Integer> q = new LinkedList<>(); //큐는 util 내의 큐와 util 내의 LinkedList가 모두 import되어야 함.
q.offer(5);
q.offer(2);
q.offer(3);
q.offer(7);
q.poll();
q.offer(1);
q.offer(4);
q.poll();
while(!q.isEmpty()){
System.out.println(q.poll()); //삭제와 함께 리턴
}
}
}
Set 컬렉션
- List와 달리 저장 순서가 유지되지 않는다. index로 객체를 가져오는 경우도 없다.
- 중복을 제거한다.
- 대신 전체 객체를 한번씩 반복해서 가져오는 Iterator를 제공한다.
- HashSet, TreeSet 이 있다.
Set의 공통메소드
| boolean add(E e) | 객체를 추가 후 성공하면 true, 실패 시 false |
| boolean contains(Object o) | 주어진 객체가 있는지 반환 |
| Iterator<E> iterator() | 반복자 반환 |
| isEmpty() | 컬렉션이 비어있는지 확인 |
| int size() | 객체 수 반환 |
| E remove(int index) | 해당 인덱스의 객체 삭제 |
| void clear() | 모든 객체 삭제 |
| boolean remove(Object o) | 주어진 객체를 삭제 |
HashSet과 TreeSet 차이
Set의 가장 큰 장점은 중복을 자동으로 제거해준다는 점이다.
Set의 구현체 중에서는 HashSet이 가장 성능이 좋다.
HashSet과 TreeSet 모두 중복을 허용하지 않고 저장 순서를 유지하지 않는다.
HashSet은 해싱이고, TreeSet은 이진타색트리라서 속도는 HashSet이 더 좋고 정렬은 TreeSet이 더 좋다.
(이진탐색트리는 데이터의 추가와 삭제는 시간이 걸리지만 검색과 정렬이 뛰어나다.)
LinkedHashSet은 저장 순서를 유지한다.
구현
HashSet<Integer> hs = new HashSet<>();
hs.add(5);
hs.add(1);
hs.add(3);
hs.add(1);
System.out.println("--hash set : 저장 순서를 유지하지 않고 중복을 제거한다. --");
hs.forEach(e -> System.out.print(e + " "));
System.out.println();
LinkedHashSet<Integer> lhs = new LinkedHashSet<>();
lhs.add(5);
lhs.add(1);
lhs.add(3);
lhs.add(1);
System.out.println("--linked hash set : 저장 순서를 유지하면서 중복을 제거한다. --");
lhs.forEach(e -> System.out.print(e+ " "));
System.out.println();
TreeSet<Integer> ts = new TreeSet<>();
ts.add(5);
ts.add(1);
ts.add(3);
hs.add(1);
System.out.println("--tree set : hash set과 마찬가지로 저장 순서를 유지하지 않고 중복을 제거한다. --");
ts.forEach(e -> System.out.print(e + " "));//결과
-- hash set : 저장 순서를 유지하지 않고 중복을 제거한다. --
1 3 5
-- linked hash set : 저장 순서를 유지하면서 중복을 제거한다. --
5 1 3
-- tree set : hash set과 마찬가지로 저장 순서를 유지하지 않고 중복을 제거한다. --
1 3 5
Map 컬렉션
key와 value로 구성된 자료구조이다.
- key는 중복으로 저장할 수 없고, 중복된 key가 들어오면 기존의 값이 갱신된다.
- value는 중복으로 저장할 수 있다.
- HashMap, Hashtable, LinkedHashMap, TreeMap 등이 있다.
Map의 공통메소드
| V put(K key, V value) | 키와 값을 추가, 있는 키면 값만 업데이트. |
| boolean containsKey(Object Key) | 키가 있는지 확인 |
| boolean containsValue(Object Value) | 값이 있는지 확인 |
| Set<Map.Entry<K,V>> entrySet() | 모든 Map.Entry 객체를 Set에 담아 리턴 |
| Set<K> keySet() | 모든 키를 set 객체에 담아서 리턴 |
| V get(Object key) | 키에 해당하는 값을 반환 |
| boolean isEmpty() | 컬렉션이 비어있는지 조사 |
| int size() | 저장된 전체 객체의 수 리턴 |
| Collection<V> values() | 저장된 모든 값을 컬렉션에 담아서 리턴 |
| void clear() | 전체 Map.Entry 삭제 |
| V remove(Object Key) | 주어진 key에 따른 Map.Entry를 삭제 |
자주 쓰일 메소드
| getOrDefault(key, defaultValue) | key가 존재하면 기존 value 반환, 없으면 defaultValue 반환 |
| putIfAbsent(key, value) : absent일 때 put한다. | key가 존재하면 기존의 value만 반환하고 업데이트 안함. key가 존재하지 않으면 value를 저장 후 반환 |
| computeIfAbsent(key, mappingFunction) : absent일 때 compute한다. | key가 존재하면 기존의 value만 반환하고 업데이트 안함. key가 존재하지 않으면 mappingFunction값으로 저장 후 반환. |
HashMap, TreeMap, LinkedHashMap, HashTable
1. HashMap
key-value로 이뤄진 Entry를 저장하긴 하는데 내부적으로 해시값에 의해 어떤 버킷에 담길지 결정된다. 만약 해시값이 같으면 버킷에 List로 연결될 것이다. 그리고 해시값으로 저장하기 때문에 저장하는 순서는 유지되지 않는다. 하지만 해시라서 조회 시 성능은 매우 빠르다.
2. TreeMap
Entry가 트리 구조로 저장되어 있다. 트리 구조이기 때문에 특정 Entry에 접근하려면 O(logN)의 성능을 보인다. key값을 기준으로 정렬되는데 comparator를 통해 정렬 순서를 변경할 수 있다.
3. LinkedHashMap
큰 흐름은 HashMap과 동일한데 Entry 가 저장된 순서를 유지한다.
구현
import java.util.*;
public class 해시 {
public static void main(String[] args) {
HashMap<String, Integer> hm = new HashMap<>();
hm.put("사과", 1);
hm.put("배", 5);
hm.put("바나나", 2);
hm.put("포도", 4);
hm.put("포도", 7);
hm.remove("사과"); //key값으로 제거
System.out.println("---contains테스트---");
System.out.println(hm.containsKey("배"));
System.out.println(hm.containsValue(5));
//출력1. stream
System.out.println("--순회--");
hm.forEach((key, value) -> {
System.out.println(key + " " + value);
});
//출력2. Iterator
System.out.println("--Iterator--");
Iterator<String> keys = hm.keySet().iterator();
while(keys.hasNext()) {
String key = keys.next();
Integer value = hm.get(key);
System.out.print(value + " ");
}
System.out.println();
//출력3. EntrySet
System.out.println("--EntrySet 출력--");
for(Map.Entry<String, Integer> entry : hm.entrySet()) {
System.out.print(entry.getKey() + "-" + entry.getValue()+",");
}
System.out.println();
//출력4. KeySet
System.out.println("--KeySet 출력--");
for(String key: hm.keySet()) {
System.out.println(key + "-" + hm.get(key) + ",");
}
System.out.println();
System.out.println("---putIfAbsent 테스트---");
System.out.println(hm.putIfAbsent("putIfAbsent", 11)); // 없으니 저장한 뒤 null 반환
System.out.println(hm.putIfAbsent("putIfAbsent", 12)); // 이미 있다면 그냥 기존 값 반환. 인자로 받은 값으로 바꾸지는 않는다. -> 지금상태로 출력하면 그냥 기존 값 11나온다.
System.out.println("--출력--");
hm.forEach((key, value) -> {
System.out.println(key+" "+value);
});
System.out.println("---computeIfAbsent 테스트---");
System.out.println(hm.computeIfAbsent("computeIfAbsent", String::length)); // 없으니 저장한 뒤 null 반환
System.out.println(hm.computeIfAbsent("computeIfAbsent", key -> key.length() * 2)); // 이미 있다면 그냥 기존 값 반환. 인자로 받은 값으로 바꾸지는 않는다. -> 지금상태로 출력하면 그냥 기존 값 10나온다.
System.out.println("--출력--");
hm.forEach((key, value) -> {
System.out.println(key+" "+value);
});
}
}---contains테스트---
true
true
--순회--
배 5
포도 7
바나나 2
--Iterator--
5 7 2
--EntrySet 출력--
배-5,포도-7,바나나-2,
--KeySet 출력--
배-5,
포도-7,
바나나-2,
---putIfAbsent 테스트---
null
11
--출력--
배 5
포도 7
바나나 2
putIfAbsent 11
---computeIfAbsent 테스트---
15
15
--출력--
배 5
포도 7
computeIfAbsent 15
바나나 2
putIfAbsent 11
정렬
일반 배열을 정렬하는 것과, ArrayList를 정렬하는 것, 그리고 Comparator와 Comparable 을 사용한 정렬을 알아본다.
package com.company.basic;
import java.util.*;
import java.util.stream.*;
public class Sort {
public static void ArrayListSort() {
System.out.println("----ArrayList를 정렬하기----");
ArrayList<String> list = new ArrayList<String>(Arrays.asList("C", "A", "B", "a"));
System.out.println("원본: "+ list);
//오름차순
Collections.sort(list);
System.out.println("오름차순: "+ list);
//내림차순
Collections.sort(list, Collections.reverseOrder());
System.out.println("내림차순: "+list);
//대소문자 구분 없이 오름차순
Collections.sort(list, String.CASE_INSENSITIVE_ORDER);
System.out.println("대소문자 구분 없이 오름차순: "+list);
Collections.sort(list, Collections.reverseOrder(String.CASE_INSENSITIVE_ORDER));
System.out.println("대소문자 구분 없이 내림차순: "+list);
/*
원본: [C, A, B, a]
오름차순: [A, B, C, a]
내림차순: [a, C, B, A]
대소문자 구분 없이 오름차순: [a, A, B, C]
대소문자 구분 없이 내림차순: [C, B, a, A]
**/
}
public static void ArraySort(){
System.out.println("----일반 배열을 정렬하기----");
String [] arr = {"banana", "orange", "apple", "peer"};
//오름차순
Arrays.sort(arr);
System.out.print("오름차순 : ");
for(String i : arr) {
System.out.print(i + " ");
}
System.out.println();
//내림차순
Arrays.sort(arr, Collections.reverseOrder());
System.out.print("내림차순 : ");
for(String i : arr) {
System.out.print(i + " ");
}
System.out.println();
//일부분만 정렬
Arrays.sort(arr, 0, 2);
//Arrays.sort(arr, 0, 2, Collections.reverseOrder());
System.out.print("0-2만 정렬 : ");
for(String i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
public static class Player implements Comparable<Player> {
private String name;
private int score;
public Player(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Player o) {
// return o.score - score; //넘어온 인자값이 더 크다! 큰 것부터 정렬
return score - o.score; // 넘어온 인자값이 더 작다! 작은 정수부터 정렬
}
}
public static void ObjectSortInt() {
System.out.println("----원하는 대로 객체 정렬하기----");
ArrayList<Player> players = new ArrayList<>();
players.add(new Player("alice", 899));
players.add(new Player("bob", 982));
players.add(new Player("chloe", 1090));
players.add(new Player("dale", 982));
players.add(new Player("eric", 1018));
/**
* 첫 방법은 Player 클래스를 implements Comparable<Player>
*/
System.out.println("--- 1. Comparable 결과---");
Collections.sort(players); //정렬 기준 없이 호출하면 compile error
for(Player p : players){
System.out.print(p.name+"-"+p.score+" ");
}
System.out.println();
/**
* 둘째 방법은 Comparator 인터페이스
*/
Comparator<Player> comparator = new Comparator<Player>() {
@Override
public int compare(Player a, Player b) {
return b.score - a.score; //뒤에거가 더 크게!
// return a.score - b.score;
}
};
System.out.println("--- 2. Comparator 결과---");
Collections.sort(players, comparator); //정렬 기준 없이 호출하면 compile error
for(Player p : players){
System.out.print(p.name+"-"+p.score+" ");
}
System.out.println();
/**
* 셋째 방법은 comparator 람다 사용 (1)
*/
Comparator<Player> comparatorLambda = (a, b) -> {
return b.score - a.score; //뒤에거가 더 크게!
};
System.out.println("--- 3. Comparator 람다 (1) 결과---");
Collections.sort(players, comparator); //정렬 기준 없이 호출하면 compile error
for(Player p : players){
System.out.print(p.name+"-"+p.score+" ");
}
System.out.println();
Collections.sort(players, (a,b) -> b.score - a.score);
/**
* 기존 객체는 그대로 두고 정렬한 값을 새 객체에 할당 할 때
* */
List<Player> players1 = players.stream().sorted((a,b) -> b.score - a.score).collect(Collectors.toList());
}
public static void ObjectSortString() {
System.out.println("----원하는 대로 객체 정렬하기 String 정렬 ----");
ArrayList<Player> players = new ArrayList<>();
players.add(new Player("alice", 899));
players.add(new Player("bob", 982));
players.add(new Player("chloe", 1090));
players.add(new Player("dale", 982));
players.add(new Player("eric", 1018));
Collections.sort(players, new Comparator<Player>() {
@Override
public int compare(Player a, Player b) {
return a.name.compareTo(b.name);
}
});
for(Player p : players){
System.out.print(p.name+"-"+p.score+" ");
}
System.out.println();
System.out.println("----원하는 대로 객체 정렬하기 String 정렬 역순으로----");
Collections.sort(players, new Comparator<Player>() {
@Override
public int compare(Player a, Player b) {
return b.name.compareTo(a.name);
}
});
for(Player p : players){
System.out.print(p.name+"-"+p.score+" ");
}
}
public static void main(String [] args){
ArrayListSort();
ArraySort();
ObjectSortInt();
ObjectSortString();
}
}
----ArrayList를 정렬하기----
원본: [C, A, B, a]
오름차순: [A, B, C, a]
내림차순: [a, C, B, A]
대소문자 구분 없이 오름차순: [a, A, B, C]
대소문자 구분 없이 내림차순: [C, B, a, A]
----일반 배열을 정렬하기----
오름차순 : apple banana orange peer
내림차순 : peer orange banana apple
0-2만 정렬 : orange peer banana apple
----원하는 대로 객체 정렬하기----
--- 1. Comparable 결과---
alice-899 bob-982 dale-982 eric-1018 chloe-1090
--- 2. Comparator 결과---
chloe-1090 eric-1018 bob-982 dale-982 alice-899
--- 3. Comparator 람다 (1) 결과---
chloe-1090 eric-1018 bob-982 dale-982 alice-899
----원하는 대로 객체 정렬하기 String 정렬 ----
alice-899 bob-982 chloe-1090 dale-982 eric-1018
----원하는 대로 객체 정렬하기 String 정렬 역순으로----
eric-1018 dale-982 chloe-1090 bob-982 alice-899
BFS, DFS
package com.company.study.dfs_bfs;
import java.util.*;
/**
* 꼭 기억하기!!!!
* 큐에 넣을 때부터 미리 방문처리를 해야 해!!!!
* 큐에서 꺼낼 때에 방문처리를 해버리면 계속 중복해서 또 들어갈 수 있음.
* 큐에 들어가는 순간 방문처리로 해야 해.
*/
public class Bfs {
public static boolean[] visit = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
public static void bfs(int start) {
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visit[start] = true;
while(!q.isEmpty()) {
int x = q.poll();
System.out.print(x + " ");
for(int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if(!visit[y]) {
q.offer(y);
visit[y] = true;
}
}
}
}
public static void main(String [] args) {
for(int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
bfs(1);
}
}package com.company.study.dfs_bfs;
import java.util.*;
public class Dfs {
public static boolean[] visit = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static void dfs(int x){
visit[x] = true;
System.out.println(x+ " ");
for(int i = 0; i < graph.get(x).size(); i++){
int y = graph.get(x).get(i);
if(!visit[y]) dfs(y);
}
}
public static void main(String [] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
dfs(1);
}
}728x90
Comments