Note) 그래프
- 그래프는 비선형 자료구조이다.
-> 노드와 엣지로 구성된다.
-> 방향성과 가중치(weight)를 줄 수 있다.
-> 자바에서는 그래프를 구성하는 노드와 엣지가 제공되지 않는다.
-> 직접 노드와 엣지를 구성해서 그래프를 만든다.
- 비선형 자료구조에서 원하는 데이터 찾기
1) 데이터 하나 읽기
2) 다음 번에 읽을 것을 예약 (연결된 데이터를 찾기)
3) 예약된 것을 하나 꺼내기
4) 2,3 반복
- 예약 목록을 스택, 큐에 따라 다르게 탐색할 수 있다.
-> 큐 이용: 너비우선탐색 (BFS)
-> 스택 이용: 깊이 이용 탐색 (DFS)
-> 두 가지는 탐색 순서만 다르다.
Ex) BFS
- Queue를 이용해서 만든다.
<hide/>
import java.util.*;
// 방향성과 가중치가 주어진 그래프
// A -> E까지 가는 그래프 만들기
// 노드와 노드 사이에 연결을 표현하는 Connection클래스 만든다.
class Connection{
Node node;
int weight;
public Connection(Node node, int weight) {
this.node = node;
this.weight = weight;
}
}
class Node{
String name;
List<Node> links;
boolean visited; // 방문여부 기록
public Node(String name) {
this.name = name;
this.links = new LinkedList<>();
}
void link(Node node) { // 노드끼리 연결시킨다. => 리스트 필요 없음
links.add(node);
}
void visit() {
this.visited = true;
}
boolean isVisited() {
return this.visited;
}
@Override
public String toString() {
return name;
}
//name만 비교
public boolean equals(Object o) {
if(this == o) return true;
if(o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return Objects.equals(name, node.name);
}
@Override
public int hashCode() {
return Objects.hash(name);
}
}
public class Graph {
public static void main(String[] args) {
List<Node> nodes = new LinkedList<>();
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
// 그래프를 만든다.
a.link(b);
a.link(d);
b.link(a);
b.link(c);
b.link(e);
c.link(b);
c.link(d);
d.link(a);
d.link(c);
d.link(e);
e.link(b);
e.link(d);
Node target = e;
// BFS 만들기 (큐 이용해서 예약목록 만든다.)
Queue<Node> queue = new LinkedList<Node>();
queue.offer(a);
while(!queue.isEmpty()) {
Node n = queue.poll(); // 비교대상을 하나 꺼낸다.
n.visit(); // 위에서 값을 확인 = 방문했다
System.out.println(n);
if(n.equals(target)) { // 타겟을 찾는다.
// find!
System.out.println("Found!"+ n);
break;
}
/* n.links.stream()
.filter(l -> !queue.contains(l))// 노드가 큐에 있는지 확인하고
.forEach(queue::offer); // 없으면 큐에 등록 (연결된 것들을 예약한다.)
아래코드 for문과 같음
*/
for (Node l : n.links) {
if(l.isVisited()) continue; // 방문했으면 건너 뛴다
if(queue.contains(l))continue; // 이미 들어가 있으면 건너 뛰고
queue.offer(l);
}
}
}
}
Ex) DFS
<hide/>
import java.util.*;
// 방향성과 가중치가 주어진 그래프
// A -> E까지 가는 그래프 만들기
// 노드와 노드 사이에 연결을 표현하는 Connection클래스 만든다.
class Connection{
Node node;
int weight;
public Connection(Node node, int weight) {
this.node = node;
this.weight = weight;
}
}
class Node{
String name;
List<Node> links;
boolean visited; // 방문여부 기록
public Node(String name) {
this.name = name;
this.links = new LinkedList<>();
}
void link(Node node) { // 노드끼리 연결시킨다. => 리스트 필요 없음
links.add(node);
}
void visit() {
this.visited = true;
}
boolean isVisited() {
return this.visited;
}
@Override
public String toString() {
return name;
}
//name만 비교
public boolean equals(Object o) {
if(this == o) return true;
if(o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return Objects.equals(name, node.name);
}
@Override
public int hashCode() {
return Objects.hash(name);
}
}
public class GraphDFS {
public static void main(String[] args) {
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
// 그래프를 만든다.
a.link(b);
a.link(d);
b.link(a);
b.link(c);
b.link(e);
c.link(b);
c.link(d);
d.link(a);
d.link(c);
d.link(e);
e.link(b);
e.link(d);
Node target = e;
// DFS 만들기 (스택 이용해서 예약목록 만든다.)
Stack<Node> stack = new Stack<>();
stack.push(a); // a를 예약목록에 넣는다.
while(!stack.isEmpty()) {
Node n = stack.pop(); // 비교대상을 하나 꺼낸다.
n.visit(); // 위에서 값을 확인 = 방문했다 체크
System.out.println(n);
if(n.equals(target)) { // 타겟을 찾는다.
// find!
System.out.println("Found!"+ n);
break;
}
for (Node l : n.links) {
if(l.isVisited()) continue; // 방문했으면 건너 뛴다
if(stack.contains(l))continue; // 이미 들어가 있으면 건너 뛰고
stack.push(l); // 연결된 모든 것을 목록에 넣는다.
} //for문
} //while문
}// 메인
}// 클래스- BFS에서 큐를 이용한 부분만 스택으로 바꾸면 DFS
Ex) 네트워크
- computers[i][j]: i번째, j번째 컴퓨터가 연결되어 있으면 1, 아니면 0
- n: 컴퓨터의 개수
- 큐만 스택으로 바꾸면 DFS로도 풀 수 있다.
- ex) n = 3, computers = [ [ 1 1 0] , [1 1 0 ] , [0 0 1] ] => return: 2
<hide/>
import java.util.*;
class Solution{
public int solution(int n , int[][] computers) {
int answer = 0;
boolean [] visited = new boolean[n];
for(int i = 0; i < n; ++i) { // computers행렬의 i번째 행 전체
if(visited[i]) continue; //i번째 컴퓨터가 방문했으면 건너뛴다.
++answer; // 새로 방문할때 +1된다.
visitAllConnectedComputers(computers, visited, i );
// 연결된 모든 컴퓨터를 색칠하는 과정
}
return answer;
}
//주어진 값을 참조만 하도록 상수처리
void visitAllConnectedComputers(final int[][] computers, boolean [] visited, int c ) {
// BFS니까 Queue이용
Queue<Integer> q = new LinkedList<>(); // q: 예약 목록
q.offer(c);
while(!q.isEmpty()) {
int i = q.poll(); // q에서 뽑아서 i에 저장하고 팝한 값을 q에서 제거
visited[i] = true; // 방문했으니까 예약목록에서 제거
for(int j = 0 ; j < computers[i].length; ++j) {
if(visited[j] == true) continue; // 방문했으면 색칠할 필요없다.
if(computers[i][j] == 1) q.offer(j);
// 1이면 i, j가 연결된 것이다. j번째 컴퓨터를 방문, 색칠하도록한다
}
}
}
}
Ex) 타겟 넘버
- n개의 음이 아닌 정수에 대해 순서를 바꾸지 않고 더하거나 뺴서 타겟넘버를 만든다.
- 사용할 수 있는 숫자가 배열 numbers에 있고 타겟 넘버 target이 매개변수로 주어진다.
- 재귀함수를 이용한다.
ex) numbers = [1 1 1 1 1] , target = 3 => return : 5
<hide/>
class Solution {
public int solution(int[] numbers, int target) { // [1 1 1 1 1 ] , 3
return sumCount(numbers, target, 0, 0);
}
// 주어진 배열 그대로 쓰기 위해 상수 처리
int sumCount(final int[] numbers, final int target, int i, int sum ){
if(i == numbers.length){ // 종료 조건
if(sum == target) return 1;
return 0;
}
return sumCount(numbers, target , i + 1, sum + numbers[i])
+ sumCount(numbers, target, i + 1, sum - numbers[i]);
// +, - 되는 경우를 모두 sum에 누적된다.
}
}
Ex) 단어 변환
- 두 개의 단어 begin, target과 단어의 집합 words가 있다.
- 예를 들어, begin: hit / target: cog / words: [ hot dot dog lot log cog ]
-> return : 4
- answer = 0이나 -1 넣는다.
- 찾는 단어가 아니면 변환가능한 다음 단어를 스택에 쌓는다. 다시 검사한다.
- 스택이 아니라 큐로 구현하면 BFS문제가 된다.
- stack
-> stack.push(); stack에서 제공하는 메서드 / 리턴값: <E>
-> stack.add(): List에서 제공 / 리턴값: boolean
<hide/>
import java.util.*;
class Solution {
class Word{ // 단어와 깊이를 묶어서 판단한다.
String word;
int depth;
Word(String w, int d) { word = w; depth = d;}
}
public int solution(String begin, String target, String[] words) {
if( !Arrays.asList(words).contains(target)) return 0; // 타겟이 없으면 리턴한다.
Set<String> used = new HashSet<>(); // 한 글자만 다른 단어를 판단하기 위해
Stack<Word> stack = new Stack<>(); // Word로 구성된 stack을 만든다.
stack.add(new Word(begin, 0));
while(!stack.isEmpty()){
Word now = stack.pop();
if(now.word.equals(target)){
return now.depth;
}
for(String w: words){ // 바꿀 수 있는 단어만 스택에 넣는다.
if(!changable(now.word, w)) continue;
if(used.contains(w)) continue; // 사용한 단어면 등록하지 않는다.
used.add(w); // 사용한 단어는 set에 넣기
stack.push(new Word(w, now.depth + 1)); // 1을 왜 더하지?
}
}
return 0;
// -1도 상관없다.
}
boolean changable(String w1, String w2){
// 한글자만 다른지 확인한다.
int len = Math.min(w1.length() , w2.length());
int count = 0;
for(int i = 0; i < len && count < 2 ; ++i){
if( w1.charAt(i) != w2.charAt(i) ) count++; // 글자가 다른 경우 count+
}
return count == 1; // 한 글자만 다르다면 바꿀 수 있다.
}
}Note) 오답
- stack.add( new Word(begin, 0 )); 스택에 초깃값으로 new Words( begin, 0 )을 넣는다.
- if(!changable(w, now.word)) continue; while문의 now와 for문의 w를 바꿀 수 없는 경우, 건너뛴다.
(즉, 한 글자만 바꿔서 바꿀수없는 경우)
- stack.push( new Word(w, now.depth + 1)) : 원래 String인 w을 Word형으로 바꾸고
depth에 1을 더한 상태로 스택에 push()한다.
Ex) 게임 맵 최단거리
- 대표적인 BFS, DFS문제이다.
<hide/>
import java.util.*;
class Solution {
class Location{
int x, y;
Location(int x, int y){this.x = x ; this.y = y; }
boolean equals(Location other){
return this.x == other.x && this.y == other.y;
}
Location left() {return new Location(x - 1, y);}
Location right() {return new Location(x + 1, y);}
Location up() {return new Location(x, y + 1);}
Location down() {return new Location(x, y - 1);}
}
class Position{
int steps; // 걸음수
Location location;
Position(Location l, int s){ location = l; steps = s; }
}
public int solution(int[][] maps){
final int mapSizeX = maps.length;
final int mapSizeY = maps[0].length;
final Location target = new Location(mapSizeX - 1, mapSizeY - 1);
// 인덱스라서 1 뺀다
boolean[][] visited = new boolean[mapSizeX][mapSizeY];
Queue<Position> queue = new LinkedList<>();
queue.add(new Position(new Location(0, 0), 1)); // 처음 위치, step은 1로 시작
while(!queue.isEmpty()){
Position now = queue.poll();
if(now.location.x < 0) continue; // 맵 밖
if(now.location.x >= mapSizeX) continue; // 맵 밖
if(now.location.y < 0) continue; // 맵 밖
if(now.location.y >= mapSizeY) continue; // 맵 밖
if(maps[now.location.x][now.location.y] == 0 ) continue; // 벽인 경우
if(visited[now.location.x][now.location.y] == true ) continue;
visited[now.location.x][now.location.y] = true;
// 타겟인 경우
if(now.location.equals(target)){
return now.steps;
}
// 타겟이 아닌 경우
queue.offer(new Position(now.location.left(), now.steps + 1 ));
queue.offer(new Position(now.location.right(), now.steps + 1 ));
queue.offer(new Position(now.location.up(), now.steps + 1 ));
queue.offer(new Position(now.location.down(), now.steps + 1 ));
}
return -1;
}
}
Note) queue.offer() Vs queue.add()
- 문제 발생시, add는 Exception을 발생시킨다.
- offer은 null이나 false를 반환한다.
출처: https://programmers.co.kr/learn/courses/13577
'자료구조와 알고리듬 With Java > [프로그래머스] Algorithm' 카테고리의 다른 글
| Part 09 Tree (0) | 2022.03.28 |
|---|---|
| Part 07 정렬 (Sort) (0) | 2022.03.24 |
| Part 06 선형탐색 (Linear Search) (0) | 2022.03.23 |
| Part 05 Stack과 Queue (0) | 2022.03.23 |
| Part 04 집합 (Set) (0) | 2022.03.22 |