1. 문제 1번 정점으로부터 각 정점으로 가는 최소 간선 수를 차례대로 출력하시오. 입력 6 9 1 3 1 4 2 1 2 5 3 4 4 5 4 6 6 2 6 5 출력 2 : 3 3 : 1 4 : 1 5 : 2 6 : 2 2 - 1. 나의 풀이 ArrayList, Queue 를 사용한다는 걸 보고 바로 풀이에 들어갔다. (풀이 도구에 대한 힌트만 봤다.) 간선의 길이를 나타내는 변수 L을 설정했다. BFS의 흐름을 따라가는 코드를 작성하는 건 쉬웠지만 L을 제대로 저장하기가 쉽지 않았다. //실패한 초기 코드 while(!q.isEmpty()){ int tmp = q.poll(); L++; for (int x : graph.get(tmp)) { if (ch[x] == 0) { ch[x] = 1; q.off..

1. 문제 ArrayList를 사용해서 정점 1에서 정점 5까지 가는 경우의 수를 출력하시오. 입력 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 출력 6 2 - 1. 나의 풀이 먼저 강의를 수강하고 여러가지 풀이(?)로 풀어보려함 (핵심은 같다.) ArrayList 를 담는 ArrayList를 생성하는 것이 핵심 (ArrayList graph) 2 - 2. 나의 코드 풀이 1. public static void DFS(int num) { ArrayList tmp = graph.get(num); for (int x : tmp) { if(x==5) count++; if(ch[x] == 0){ ch[x] = 1; DFS(x); ch[x] = 0; } } 풀이 2. public sta..

1. 문제 1번 정점에서 5번 정점으로 가는 모든 경로의 수를 출력하는 프로그램을 작성하시오. 이미 지난 정점은 다시 지날 수 없다. (1번 정점도 포함) 1번 정점에서 5번 정점으로 가는 가짓수는 6가지로 아래와 같다. 1 2 3 5 6 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 2 - 1. 나의 풀이 일단 DFS로 푸는 건 알았다. 그림을 그려보면서 손코딩으로 대충 짜보고 실제로 코드 넣으면서 문제를 풀었다. 일단 DFS(int vertex)가 실행될 때 graph[vertex][edge] == 1 이면 DFS(edge)인 재귀함수를 호출해서 꼬리에 꼬리를 무는 방식으로 풀면 된다는 감을 잡았다. 문제는 지나간 정점을 다시 지나지 않기 위함이다. 자연스럽게 체크배열을 설정했다..

이 글에서는 그래프를 인접행렬로 표현하는 방법만 소개한다. (매우 쉬움) 배열(행렬)의 0번째 인덱스는 생략한다. 기본적으로 그래프는 Vertex와 Edge를 사용해서 G(V,E)로 표현된다. 정점 1 2 3 4 5 1 1 1 2 1 1 1 3 1 1 4 1 1 5 1 무방향 그래프는 방향이 따로 없으므로 배열에서 대칭을 띄며 그냥 행렬에 이어진 것끼리 1로 표시하면 된다. 방향 그래프에서는 V와 E, 방향의 의미가 있다. 정점 1 2 3 4 5 1 1 1 2 1 3 1 4 1 5 가중치 방향그래프에는 1대신 가중치 값을 저장하면 된다. 정점 1 2 3 4 5 1 2 4 2 5 3 5 4 2 5 * 자기자신을 가리키면 [n][n]에 저장하면된다.

1. 문제 최소 간선의 길이를 BFS로 풀기 2 - 1. 나의 풀이 그냥 기본적인 BFS에 Node.lt ==null &&Node.rt == null 이면 해당 계층을 반환하면된다. 주의할 점은 for문에서 i < q.size()를 쓰면 안되고 int len = q.size()를 한다음 i < len으로 적어야한다. for문을 돌면서 q의 사이즈가 계속 늘어나기 때문이다. 2 - 2. 나의 코드 package BFS_DFS; import java.util.*; class Node { int data; Node lt, rt; Node(int value) { this.data = value; } } public class bfs10 { static Node root; public static int BFS(..

1. 문제 말단 노드 중에서 간선의 길이가 가장 짧은 길이를 출력하시오. 2. 나 강의 보고 진행 3 - 1. 강의 풀이 강의에서는 완전 이진트리에서만 풀이가 가능하다는 전제를 세웠다. 양 쪽 자식노드가 null이면 말단 노드라는 뜻이므로 해당 계층 L을 리턴한다. 해당 L은 옆에있는 노드의 말단 노드의 계층과 min으로 비교되어서 리턴된다. 커뮤니티에서 불완전 이진트리에 대한 풀이도 있다. 3 - 2. 강의 코드 완전 이진트리 package BFS_DFS; import java.util.*; class Node { int data; Node lt, rt; Node(int value) { this.data = value; } } public class dfs09 { static Node root; pub..

1. 문제 한 번의 점프로 앞으로 5, 1칸 뒤로 1칸갈 수 있다. 현수의 위치 S와 송아지의 위치 E가 주어졌을 때 현수가 송아지의 위치까지 도달할 점프의 최소 횟수를 구하시오. 입력 5 14 출력 3 2 - 1. 나의 풀이 이전 강의에서 BFS에 대한 이해를 위해선 송아지 찾기 문제가 좋다해서 이전 강의를 보고 바로 이 문제를 풀려고 왔다. answer = E - S 라 하고 0에서 부터 +5, +1, -1 만의 수식으로 answer까지 가는데 걸리는 최소 회수를 구하는 문제와 같다. 큐에 맨처음 0을 넣고 0에 5를 더한 값, 1을 더한 값, 1을 뺀값을 넣는다. 큐를 poll해서 answer와 같은지 확인하고 아니면 위 과정을 반복한다. poll한 값이 answer이면 해당 계층을 반환하고 끝낸다..

1. 문제 위 그림과 같은 이진트리를 레벨 탐색 연습하시오. 레벨 탐색 순회 출력: 1 2 3 4 5 6 7 2. 나의 풀이 강의 보고 진행 3 - 1. 강의 풀이 트리 선언 후 0, 1, 2 레벨의 트리들을 순회한다. Q에 root 를 넣는다. (순회) root를 Q에서 빼고 root.lt와 rt를 Q에 넣는다. 이를 반복한다. 3 - 2. 강의 코드 package BFS_DFS; import java.util.*; class Node{ int data; Node lt; Node rt; Node(int value) { this.data = value; } } public class bfs07 { static Node root; public static void BFS(Node root) { //bfs로..

1. 문제 각 줄에 하나씩 부분 집합을 아래와 같은 순서로 출력한다. 단 공집합은 출력하지 않는다. 입력 3 출력 1 2 3 1 2 1 3 1 2 3 2 3 2. 나의 풀이 도통 모르겠어서 강의 봄 3 - 1. 강의 풀이 D(1)부터 시작해서 왼쪽 트리는 D(num)의 num을 사용하는 트리 오른쪽 트리는 D(num)의 num을 사용하지 않는 트리 사용함과 사용하지 않음은 int[n+1] 만큼의 배열에 표시한다. 1부터 3까지의 부분 집합을 출력하고자 하면 DFS는 (3+1) 즉 4까지 생성하고 num이 4이면 for(int i = 1 ; i