Dev.baelanche

이차원 배열을 짜서 DFS 를 수행하면 된다. 노드에 간선이 있을 경우 노드를 계속 타고 들어가며 방문한 노드 배열 정보를 1로 표시한다. public class Main { static int n; static int a[][]; static int path[][]; static boolean visited[]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); a = new int[n+1][n+1]; path = new int[n+1][n+1]; visited = new boolean[n+1]; for(int i=1; i

탐색을 여러번 할뿐 컴포넌트 개수를 세는건 여타 기본 DFS 문제와 똑같다. 필자는 R, G, B 탐색 후 R, G 는 같은 값으로 배열을 채워 넣어 풀었다. public class Main { static int n; static String a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); a = new String[n][n]; for(int i=0; i

영역이 아닌 곳을 탐색하여 컴포넌트의 크기를 구하면 된다. 좌표가 배열의 인덱스와 반전되니 그 부분을 신경써서 풀자. public class Main { static int asc[] = new int[5001]; static int a[][]; static int m; static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); m = sc.nextInt(); n = sc.nextInt(); a = new int[n][m]; int k = sc.nextInt(); while(k-->0) { int x1 = sc.nextInt(); int y1 = sc.nextInt(); int x2 = sc.next..

그래프에서 컴포넌트의 개수와 각 컴포넌트의 크기를 구하는 문제이다. public class Main { static int n; static int a[][]; static int asc[] = new int[625]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); a = new int[n][n]; for(int i=0; i

그래프 컴포넌트 중 가장 큰 컴포넌트의 크기를 구하는 간단한 문제이다. public class Main { static int n; static int m; static int a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); a = new int[n+1][m+1]; int k = sc.nextInt(); int max = 0; while(k-->0) a[sc.nextInt()][sc.nextInt()] = 1; for(int i=1; i

DFS, BFS 를 이용하여 푸는 기본 문제이다. 풀이 1. n*m 의 배열을 만들어 0 또는 1을 대입한다. 2. 배열의 값이 1일때 상하좌우로 1이 있는지 탐색한다. 3. 탐색한 인덱스에 0을 대입한다. 4. 가로 n, 세로 m 은 배열에서 a[m][n] 이므로 실수하지 말자. public class Main { static int mx[] = {-1, 0, 1, 0}; static int my[] = {0, 1, 0, -1}; static int a[][]; static int m; static int n; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-..

public class Main { int adj[][]; boolean visited[]; int n; Main(int n) { this.n = n; adj = new int[n+1][n+1]; visited = new boolean[n+1]; visited[0] = true; } public void addEdge(int u, int v) { adj[u][v] = v; adj[v][u] = u; } public void dfs() { for(int i=1; i

박스의 가로, 세로 길이가 3, 4 일때 크기 5의 성냥도 들어가는걸로 봐서 성냥을 대각선으로 넣는것도 허용된다. 대각선의 길이가 박스내부의 길이 중 가장 크니 피타고라스 공식으로 풀면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int w = sc.nextInt(); int h = sc.nextInt(); while(n-->0) { int t = sc.nextInt(); int box = (int)Math.sqrt(w*w + h*h); if(t