1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 import java.io.*; import java.util.*; public class Main { static int M,N,K; static boolean[][] visit; static int[][] ad; static int[] dx = {0,0,1,-1}; static int[] dy = {1,-1,0,0}; static int..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 import java.net.Inet4Address; import java.util.*; import java.io.*; public class Main { static boolean[][] visit; static int[][] ad; static int N,M,K; public static void main(String[] args) throws IOException{ BufferedReader br = new Bu..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 import java.net.Inet4Address; import java.util.*; import java.io.*; public class Main { static int n,m; static int [][] ad; static boolean [][] visit; static int draw_size; //그림의 크기 public static void main(String..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 import java.util.*; import java.io.*; public class Main { static boolean[][] visit; static int[][] ad; static int N; //행의 개수 static int M; //열의 개수 static int K; //간선의 개수 static int dx[] = {0,0,1,-1}; static int dy[] = {-1,1,0,0..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 import java.util.*; import java.io.*; public class Main { static boolean[]visit; static ArrayList []ad; static int nV; //노드의 개수 static int leaf_Node; public static void main(Strin..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import java.util.Scanner; public class Main { static int w,h; static boolean[][] visit; static int[][] ad; static int[] dx = {1,1,1,0,0,-1,-1,-1}; static int[] dy = {0,-1,1,1,-1,1,0,-1}; static int island; public static void main(String []arg..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 import java.util.*; import java.io.*; public class Main { static boolean[]visit; static ArrayList []ad; static int result[]; static int nV; //노드의 개수 static int nE; //간선 public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import java.lang.reflect.Array; import java.util.*; import java.io.*; public class Main { static ArrayList [] ad; static boolean[] visit; static int nV, nE; static int component = 0; public static void main(String[] args) throws IOExceptio..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 import java.lang.reflect.Array; import java.util.*; import java.io.*; public class Main { static ArrayList [] ad; static boolean[] visit = new boolean[101]; static int nV, nE; static int n, m; static int result = -1; public static void main(S..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 import java.util.*; import java.io.*; public class Main { static int[][] ad = new int[5][5]; static Set set = new HashSet(); public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; for(int i = 0; i

이번에 백준 1325번 문제를 풀고 인접 행렬과, 인접 리스트의 차이에 대해 공부를 했다. 인접 행렬은 2차원배열로 dfs 그래프를 구현한 것이다. 그래서 장점으로는 구현이 쉽고, 노드끼리 연결이 되어있는지 아닌지 O(1)로 쉽게 알 수 있다. fc [i][j]에서 0인지 1인지만 구분하면 되기 때문이다. 단점은 노드 i에 연결되있는 노드들을 확인하기 위해서는 fc [i][0] ~ fc [i][V]까지 전체 노드를 방문해야 하기 때문에 O(V)만큼 걸리기 때문이다. 만약에 노드가 수천만개이고, 간선이 달랑 3,4개라고 생각해보면 노드들이 어떻게 연결되어있는지 알아보기 위해서는 O(V^2)만큼 걸리는데, 간선이 노드에 비해 매우 적기 때문에 손해이다. 그래서 이러한 단점을 커버 치기 위해 인접 리스트가 존..

이 문제는 할 때마다 시간 초과가 나올 수도 있고, 맞았습니다라고 뜬다. 이 경우는 시간 복잡도가 코드 제한시간에 걸쳐서 제출했을 때, 되는 경우도 있고, 안 되는 경우도 있다고들 한다. 비록 많은 문제를 풀진 않았지만 이런 경우도 있다고들 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 import java.io.*; import java.util.*; public class Main { sta..