Coding Story

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } } public class Main { static Queue queue = new LinkedLis..

그래프를 인접 행렬과 인접 리스트로 표현했을 때 진입/진출 차수 계산, 엣지수를 계산할 때 각각의 시간 복잡도를 C언어 코드로 구현하였다. int matrixCalculateOutDegree(GraphType* g, int v) { int i, degree = 0; for (i = 0; in; i++) { if (g->adj_mat[v][i] != 0) degree++; } return degree; // 시간 복잡도는 O(n) } int matrixCalculateInDegree(GraphType* g, int v) { int i, degree = 0; for (i = 0; i n; i++) { if (g->adj_mat[i][v] != 0) degree++; } return degree; /..

그래프 탐색 알고리즘 그래프 탐색은 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것이다. 많은 문제들이 단순히 그래프의 노드를 탐색하는 것으로 해결된다. 그래프의 탐색 방법은 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 두가지가 있다. 깊이 우선 탐색(DFS: depth first search) 그래프의 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행한다. 알고리즘 자기 자신을 다시 호출하는 순환 알고리즘의 형태를 띈다. 그래프의 시작 정점에서 출발하여 시작 정점 v를 방문하였다고 표시한다. v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택하여 깊이 우선 탐색을 다시 시작한다..

DFS import java.util.Scanner; public class Main{ static int n, answer=0; static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1}; public void DFS(int x, int y, int[][] board){ for(int i=0; i=0 && nx=0 && ny