최's 먹공로그

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..

1. 예전에 BFS로 풀었던 적이 있어서 DFS로 풀어보려고 했지만 흠 최단거리라서 BFS로 풀어야 되는걸까?? 2. DFS돌면서 visit 체크 해주고 인접한 4방향 보면서 N M까지 찾도록 함 3. map에 cnt 값 업데이트 해주면서 진행하고 마지막에 map[N][M]에 있는 값 출력 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ2178_미로탐색 { static int N; static int M; static int[][] map; static int[][] visit; public sta..

1. 두개의 노드가 연결되어 있다는 어찌 표현할지 -> 2차원 배열에 연결되어 있는 노드는 1로 표현 1,2가 연결인 경우 0 1 0 0 1 0 0 0 이런식으로 2. visit은 방문한 노드만 체크 -> 1차원 배열로 노드만 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 BOJ1260_BFSDFS { static int[] visit; static int[][] map; static int N, M; publ..

1. 지민이가 만들고 싶은 상태의 체스판과 비교해서 cnt 비교하여 최종 cnt 갱신 2. 검사할 때 +8 할 경우 map을 넘어가지 않는지 검사 필수 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ1018_체스판 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new ..