BOJ 백준/DFS + BFS 검색 결과

해당 글 4건

백준 02178 - 미로 탐색

출처 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 고려사항 BFS 를 활용 - BFS를 활용하면 레벨 (몇 번 움직였는지)가 작은 순서대로 탐색하기 때문에 먼저 (N, M) 에 도달하면 더이상 탐색 없이 return 해줄 수 있다. DFS를 사용하면 현재 움직인 cnt 값을 인자로 넘겨주며 값을 구할 수 있지만 N, M 에 도달해도 다른 가지까지 탐색을 진행해야 최소값인지를 알 수 있다. ( 가지치기를 이용하면, 연산을 줄일 수 있긴 하지만.. ) #include #i..
BOJ 백준/DFS + BFS 2020. 12. 20. 02:43

백준 02606 - 바이러스

출처 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 고려사항 BFS 1부터 시작이니 1은 카운트 하지 않는다. 양방향 그래프임을 주의! => network[src]에 dst 넣고, 반대로도! queue 에 넣는 순간 ++ans #include #include #include using namespace std; bool visit[101]; int main() { int n, m, src, dst, dstSize, ans = 0; vector ..
BOJ 백준/DFS + BFS 2020. 11. 10. 18:53

백준 11724 - 연결 요소의 개수

문제출처 : https://www.acmicpc.net/problem/11724 고려한 사항 - 모든 정점을 기준으로 연결된 정점을 큐에 넣고, 그 정점을 또 기준으로 연결된 요소들을 확장해 나간다 - 위 과정에서 이미 조사한 정점 즉, 방문한 정점은 위 과정을 반복하지 않는다. - 어떠한 정점과 간선으로 연결 안 된 정점도 존재한다. #include #include #define maxN 1000 #define maxM maxN*(maxN-1)/2 using namespace std; queue vertex; bool visit[maxN+1]; // 이미 방문한( 어떠한 세트에 포함된 ) 정점 체크 bool adjacent[maxN+1][maxN+1]; // 인접행렬 int N,M,answer; // ..
BOJ 백준/DFS + BFS 2020. 1. 5. 22:19

백준 10451 - 순열 사이클 (DFS)

문제 출처 : https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 문제 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열을 배열을 이용해 \(\begin{pmatrix} 1 www.acmicpc.net 나름 쉬운 dfs문제 인거 같다. 보통 풀던 dfs와 다르게 한 지점 방문마다 재귀를 하는게 아니라 순환인지 아닌지를 ..
BOJ 백준/DFS + BFS 2020. 1. 3. 00:03