아침 학습 - 이코테 그래프 탐색 알고리즘 DFS/BFS
DFS : 깊이 우선탐색 (Depth-First Search)
DFS는 스택 자료구조 이용
동작과정
탐색 시작 노드를 스택에 삽입, 방문처리한다.
스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접노드를 스택에 넣고 방문처리한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
2번 과정을 더이상 수행할 수 없을때까지 반복한다.
O(N)의 시간 소요
재귀 함수를 이용하면 간결하게 구현가능
DFS 예제
public class DFSExam {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
// DFS 함수 정의
public static void dfs(int x) {
// 현재 노드 방문처리
visited[x] = true;
System.out.print(x + " ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited[y]) dfs(y);
}
}
public static void main(String[] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
graph.get(2).add(1);
graph.get(2).add(7);
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
graph.get(4).add(3);
graph.get(4).add(5);
graph.get(5).add(3);
graph.get(5).add(4);
graph.get(6).add(7);
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
graph.get(8).add(1);
graph.get(8).add(7);
dfs(1);
}
}
</> 실행 결과
1 2 7 6 8 3 4 5
각 노드가 방문된 정보를 표현하는 배열 visited
크기가 9인 이유?
→ 인덱스 0은 사용하지 않고, 1번 부터 8번까지의 노드가 있으니 하나 더 큰 크기로 9개 크기의 배열을 생성
graph의 0번 인덱스는 비운다.
어제 호눅스 수업과 아래의 두 블로그 참고
https://velog.io/@livenow/Java-VOValue-Object%EB%9E%80
VO 란?
The bad practice of using primitive types to represent an object in a domain is so common that has even a name : primitive obsession.
Immutability(불변성)
No setters allowed.
한번 파라미터 값을 주고 생성자를 통해 생성하면 바꿀 수 없다.
객체는 GC에 의해 사라지기 전까지 같은 값으로 유지되어야한다.
immutability 로 인한 장점
Hassle-free Sharing (번거로움 없는 공유)
코드의 다른부분에서 수정되지 않기때문에 참조로 Value Object를 공유할 수 있다.
버그를 피하기위해 작성되는 코드의 복잡성과 부하를 감소시킨다.
멀티 스레드 환경에서 이점이 된다.
Improved Semantics (향상된 의미)
무의미한 getter를 추가하지 마라
나중에 필요할거 같아서 메소드를 추가하는 것을 자제하라
초기 클래스는 생성자와 private 속성들로만 구성되어야한다.
Value Object를 다루는 방법
Value Equality(값 동등성)
나랑 친구가 다른 카드 덱에서 카드를 한장씩 뽑았다. 친구의 카드가 내 카드와 같은지 알아야 하는 상황이다.
친구의 카드, 내카드가 같은 숫자와 무늬라면 두장의 카드는 같은 속성을 가진 거라고 볼 수 있다.
이제 친구와 내가 카드를 교환해도 친구와 나의 카드는 동일하다.
두장의 카드가 Value Object 인 것이다.
Value Object는 값이 동일한 두개의 객체는 동일한 것이라고 본다. → 객체들의 내부 값이 같은지 확인하는 것을 통해서 동등성을 테스트할 수 있다.
Self Validation(자가 유효성 검사)
Value Object는 문맥에서 유효한 값만 허락한다.
유효하지 않은 값을 가진 객체는 생성할 수 없다.
생성자에 값을 넣을때 값의 유효성을 확인해야한다.
유효하지 않으면 예외가 발생시킨다.
모든 유효성 검사는 생성 시간에 이루어진다.
final class Rand {
private int value;
public Rand(int value) {
if (value < 1 || value > 13 {
throw new InvalidRankValue(value);
}
this.value = value;
}
}
PR 설명은 핵심만
distinguish()라는 메소드명이 다른 메소드에서 호출된걸 봤을때 무슨 역할을 하는지 잘 모르겠다. List를 반환하는 메소드이기 때문에 getPieceList()와 같은 이름이 더 좋을것이다.
private 메소드는 public메소드 뒤에 위치하는 것이 좋다.
관련 내용 학습
표준 자바 관례에 따른 클래스 안에서의 순서
블로그에 나와있는 SOLID 원칙과 예제코드도 더 살펴봐야겠다. 개구리책이랑 같이 봐야지
String과 StringBuilder의 문자결합
String empty = appendNewLine(getEmptyResult());
return appendNewLine(getBlackPieceResult()) +
appendNewLine(getBlackPawnResult()) +
empty + empty + empty + empty +
appendNewLine(getWhitePawnResult()) +
appendNewLine(getWhitePieceResult());
호눅스가 StringBuilder 로 바꿔서 바이트 코드를 비교해보라고 하셨다.
비교해보니 위의 코드(String에서 + 연산자 사용)의 바이트 코드에 StringBuilder.append라고 쓰여있다. 바이트 코드를 잘 모르지만 내부적으로 StringBuilder를 사용하는건가 하고 찾아보니 Java 1.5부터는 +연산자를 사용해도 StringBuilder로 변환해서 처리한다고 한다.
: 참고한 블로그
intelliJ에서 byte 코드 확인하기
View → ShowByteCode
try-with-resources문
자바의 정석(437p)
try의 괄호()안에 객체를 생성하는 문장을 넣으면 이 객체는 try블럭을 벗어나는 순간 자동으로 close() 해준다.
대신 AutoCloseable이라는 인터페이스를 구현한 클래스여야 try-with-resources문을 사용 가능하다.
자바 API 문서를 보니 Scanner도 AutoCloseable 인터페이스를 구현한 것이다.
Chess 클래스에서 사용자 입력받는 부분에서 try-with-resources 구문을 사용하려고 했으나 try의 괄호 안에 Scanner 객체를 생성해줘서 catch에서 스캐너 참조변수에 접근하지 못해서 다시 입력받는것을 실패해서 그냥 close() 해주었다.
Scanner sc = new Scanner(System.in);
while (true) {
try {
String input = sc.nextLine();
if (input.equals("y")) {
startChess();
}
if (input.equals("n")) {
System.out.println("체스를 종료합니다.");
break;
}
if (!input.equals("y") && !input.equals("n")) {
throw new NoSuchElementException();
}
} catch (NoSuchElementException e) {
System.out.println("잘못된 값입니다. y 또는 n을 입력해주세요.");
sc = new Scanner(System.in);
}
}
sc.close()
(내일)
인텔리제이에서 바이트 코드를 볼 수 있는 건 처음알았네요!
좋은 정보 감사합니다~