최's 먹공로그

1. DFS로 몇덩어리인지 검사 2. BFS로 얼음녹여 3. 반복 4. return 되는 경우는 (1) 덩어리가 2 이상 되는경우 (2) 얼음이 다 녹았는데 (1)인 경우로 return 안된 경우 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 BOJ2573_빙산 { static int[][] map, map_copy; static int[][] visit; static Queue q; static int yea..

1. 이건 그냥 dfs든 bfs든 돌리면 되는 문제 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2468_안전영역 { static int n; static int[][] map = new int[102][102]; static int[][] visited = new int[102][102]; static int[] dx = {-1,0,1,0}; static int[] dy = {0,-1,0,1}; public static void dfs(int x, int y, int rain) { int nx ..

1. 숨바꼭질과 완전 똑같음 2. 큐에 front, back으로 인덱스 컨트롤 해주면서 front에 있는거를 Up, Down 해주면서 G 층에 간 경우를 찾기 3. Up의 경우 최대층을 넘길 수 없음 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ5014_스타트링크 { static int F, S, G, U, D, front = -1, back = -1; static int[] Q, visit, d; public static void main(String[] args) throws IOExcepti..

1. BFS 같긴 한데.... 어떤식으로 BFS로 적용 가능할까?? 2. BFS라기 보다는 큐 구조체를 사용해서 푸는 문제로 접근(처음에는 순열조합 생각 했는데 시간 터질거 같음) 3. 큐의 front에 넣는 애로 세가지 연산을 다 해가면서 K랑 같은 애를 찾을 때 까지 반복 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ1697_숨바꼭질 { static int N, K, front = -1, back = -1; static int Q[] = new int[100002]; static int vis..

1. 익은 토마토들은 하루 지나면 인접 토마토를 익게함(인접 : 위,아래,오,왼,상,하) 2. 토마토가 다 익는데 걸리는 최소 일 수 3. 동시간대 퍼지는 토마토인지 어떤식으로 구분할 수 있을까?? 큐의 크기로 구분 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 BOJ7569_토마토 { static int[][][] map; static int day = 0; static int[][][] visit; stat..

1. 사람 수 만큼의 N by N map에 촌수가 연결된 번호들을 1로 표시 2. 계산해야 되는 촌수의 노드 중 앞번호 먼저 탐색 시작 3. 연결된 다른 노드가 있는지 보고 해당 노드를 다시 탐색 반복 4. 노드를 타고 들어갈 때 마다 cnt++ 5. for i가 계산해야 되는 촌수의 뒤번호랑 일치되면 flag 표시 해줘서 나머지 탐색에서 다 return 6. 백트레킹 해서 찾아야되는 경우 고려(cnt, visit_node 복구) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2644_촌수계산 { ..

1. 예전에 DFS로 푼 흔적이 있어서 BFS로 풀이 2. pair class 만들어서 단지내에 집이 있는 위치 x,y 저장하면서 인전한 곳 집이 있는지 계속 검사 q.add, q.poll 반복 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class BOJ2667_단지번호붙이기 { static int[][] map; static int[][] visit; static int[..

1. BOJ1260 DFS와 BFS의 DFS 풀이법과 똑같은 문제이다 2. map에 간선을 연결하고 노드의 방문의 체크하며 카운트! 3. map이 연결되어 있지 않거나( != 1) Node에 이미 방문 했을 경우(== 1)에는 넘어가고 아닌 경우에는 연결된 Node 니깐 카운트 해준다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2606_바이러스 { static int[][] map; static int cnt; static int[] visit; static int map_size; publi..