백준/그래프 이론
-
18405 경쟁적 전염백준/그래프 이론 2024. 6. 22. 23:17
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.LinkedList;import java.util.List;import java.util.Queue;import java.util.StringTokenizer;class Position{ int x; int y; int virus; Position(int x, int y, int virus) { this.x = x; this.y = y; this.virus..
-
1707 이분 그래프백준/그래프 이론 2024. 6. 19. 21:24
이분 그래프란, 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프.즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는(같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 한다.그림으로 설명하자면, 1번의 정점에 빨간색을 칠하자. 그 후 인접한 정점 2에는 다른색, 파랑색을 칠해준다. 정점 2에 인접한 3에는 빨간색을 칠해준다. 이런식으로 하다보면 결과적으로 이 그래프는 이분 그래프가 맞다.인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프이기 때문이다. 다른 그래프를 보자면, 1번 정점에 빨간색을 칠해주고.. 순서대로 하면..
-
16928 뱀과 사다리 게임백준/그래프 이론 2024. 6. 18. 22:01
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int move[]; static boolean visit[]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st ..
-
3055 탈출백준/그래프 이론 2024. 6. 18. 11:20
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;class Position { int x; int y; Position(int x, int y) { this.x = x; this.y = y; } }public class Main { static String map[][]; static Queue water; static Queue animal; static int R; static int C; public static ..
-
1068 트리백준/그래프 이론 2024. 6. 12. 22:15
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.StringTokenizer;public class Main { static boolean visit[]; static ArrayList [] tree; static int result; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer ..
-
14502 연구소백준/그래프 이론 2024. 6. 10. 21:01
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;class Position{ int x; int y; Position(int x, int y) { this.x = x; this.y = y; } }public class Main { static int N; static int M; static ..
-
17265 나의 인생에는 수학과 함께백준/그래프 이론 2022. 5. 29. 17:35
1. 풀이 dfs를 이용해서 풀면된다. (1,1) 에서 시작해서, max 배열에는 연산 결과가 큰 값으로, min 배열에는 연산 결과가 작은 값으로 채우면 된다. 그 후 max[N][N] 과, min[N][N] 을 출력하면 정답이 된다. 아래 그림은 예제에서 일부분을 가져온 것이다. 5가 입력되어 있는 부분은 (1,1)의 위치이다. 이 때, (2,2) 위치에는 두가지 연산이 있다. 1) 오른쪽, 아래 이동 5+3 = 8 이 먼저 연산되었다고 하자. 그러면 max[2][2] = 8 이 된다. 2) 아래, 오른쪽 이동 그 이후에 아래, 오른쪽 이동으로 5 * 3 = 15 가 결과로 나왔다면 더 큰 값, 15로 바꿔주어 max[2][2] = 15 가 된다. 2. 최종 코드 import java.io.Buffe..
-
2606 바이러스백준/그래프 이론 2022. 1. 24. 22:54
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int N; static int M..