출저 : https://www.acmicpc.net/problem/2839 "BFS를 이용한 탐색" 12345678910111213141516171819202122232425262728293031323334353637383940414243444546import java.util.Arrays;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; public class Main { static int N; static int min = -1; static int[] visited; static int[] weight = {3,5}; static boolean ok; static Queue q = new LinkedList()..
출저 : https://www.acmicpc.net/problem/7576 "단순 BFS" 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384import 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 ..
출저 : https://www.acmicpc.net/problem/1697 "단순 BFS" 수빈이가 이동할 수 있는 방법을 길이 3인 배열로 만들어 처리했음. 12345678910111213141516171819202122232425262728293031323334353637383940414243import 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,K; static int INF = 1000..
출저 : https://www.acmicpc.net/problem/4179 "불먼저 사람먼저 두 번의 BFS, 트리의 level을 카운터로" 지훈이가 불을 피해 가장자리 까지 가서 몇번 만에 탈출할 수 있는지 최단거리를 구하는 문제이다. 이 문제에서 중요한 것은 불과 지훈이용 큐 두개를 가지고 BFS를 두번 돌리는 것이다. 불을 먼저 보내고 그 후에 지훈이가 갈 수 있는 경로를 탐색해야함을 주의한다. 순서가 중요하다. 이동 횟수는 count 변수를 두어 BFS 전체에서 구한다. 이 값이 트리의 level 이라고 할 수 있다. 이 때 fs,ms 와 같은 size 변수를 두어 BFS 탐색을 함에 주의한다. 123456789101112131415161718192021222324252627282930313233..
출저 : https://www.acmicpc.net/problem/2667 "단순 BFS" BFS를 돌려서 상하좌우로 인접해 있는 집들을 탐색한다. 탐색하는 과정에서 각 단지를 넘버링 할 수 있는 변수를 하나 두고, BFS 탐색이 끝날 때마다 변수를 증가 시켜 넘버링을 이루게 한다. 이와 비슷한 형식으로 매 BFS 탐색마다 단지의 개수를 세는 count 변수를 하나 두어 단지의 개수를 세고, 아래 풀이에서는 이 카운트 값을 Array List에 넣어두고, 나중에 sort 하였다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768..
출저 : https://www.acmicpc.net/problem/11559 "BFS를 활용한 구현" 먼저 뿌요뿌요의 실행 순서를 보자. 1. 중력에 의해 모든 뿌요들이 밑으로 떨어진다. 2. 상하좌우로 4개 이상 인접한 같은 색깔의 뿌요들은 모두 동시에 터진다. 간단히 두개의 과정으로 나타낼 수 있다. 이를 구현해주면 끝. 먼저 뿌요들을 밑으로 내리는 코드를 보면 아래와 같다. 12345678910111213141516for (int i = 11; i >=0 ; i--) { for (int j = 0; j
출저 : https://www.acmicpc.net/problem/2146 "BFS 두번" 각각의 섬들에 2부터 시작하는 넘버링을 한다. 이 과정은 BFS를 사용한다. 넘버링 까지는 쉽게 할 수 있다. 체크한 땅들에 대해서는 visited 배열을 통해 중복을 제거해준다. 그렇게 2 ~ .. 넘버링을 하였으면 이제 isEdge 함수를 활용해 각 섬의 모든 가장자리에서 시작해서 탐색을 시작하여 다른 섬을 만날 때 까지 탐색을 한다. 다른 섬을 구분하는 구문은 아래와 같다. if(map[cur.x][cur.y] != idx && map[cur.x][cur.y] > 0) {q.clear();break loop;} 1234567891011121314151617181920212223242526272829303132..
출저 : https://www.acmicpc.net/problem/1600 "나이트 처럼 갈 수 있는 이동이 중요한 BFS" 처음에 해당 문제를 그냥 최단거리를 구하는것 처럼 int[][] visited 배열을 두어 최대값으로 세팅하고, 특정 위치에서 최소가 되는 경우만 탐색을 진행하도록 했다. 여기서 간과한 것이... 특정위치에 나이트를 한번 쓰고 온 것과 안 쓰고 온 것은 다르다는 것이다. 아래와 같은 경우를 보자. 먼저 나이트 이동으로 (0,0) 에서 (1,2) 로 이동해서 visited[1][2] = 1 (이동횟수) 이 된다고 하면, 원숭이의 걸음으로 3번 이동해서 온 경우는 더이상 탐색을 하지 못하게 된다. (이미 최소 크기로 해당경로를 지나갔기 때문에..) 정상적이라면 최단 거리는 4가 되지만..
출저 : https://www.acmicpc.net/problem/2606 "BFS" 해당 문제는 정말 단순한 BFS 문제이다. 1번 노드를 시작으로 연결된 모든 노드들의 개수를 세면 된다. 먼저 주어진 정보를 토대로 인접행렬 adj를 만든다. 그후 BFS 에 따라 queue 에 연결된 노드들을 하나씩 넣어주고 탐색한다. 간단하다. 1번 노드는 세지 카운트 하지 않음을 주의한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRead..
출저 : https://www.acmicpc.net/problem/2178 "BFS를 활용한 최단거리 탐색" 해당 문제는 BFS를 활용해서 왼쪽 상단에서, 오른쪽 하단까지의 최단거리를 탐색하는 문제이다. BFS 에서 중요한 것은 갈 수 있나 없나를 체크하는 것과 중복 경로를 줄이는 것이다. 아래 풀이에서는 int형 배열 visited를 활용한다. visited 배열에는 해당 지점에 지나온 칸의 개수가 저장된다. 그 전에, 경로 A가 특정 지점 x, y 를 지날 때, 이미 저장된 visited[x][y] 에 값이 자신보다 더 작은 경우라면 경로 A는 더 이상 탐색할 필요가 없다. 이미 자신보다 더 최단 경로로 지나간 경우가 있기 때문에... 이러한 경우들을 생각해서 중복을 줄여준다. 그 외에 우선순위 큐를..
- Total
- Today
- Yesterday