깊이우선탐색(DFS)
-
백준 1937번: 욕심쟁이 판다깊이우선탐색(DFS) 2019. 1. 20. 18:38
https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 키워드 - DFS, 구현 Source #include #include #include #include #include #include..
-
백준 14716번: 현수막깊이우선탐색(DFS) 2018. 8. 12. 14:35
https://www.acmicpc.net/problem/14716 키워드 - DFS, FLOOD FILL Source #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #define ll long long #define c_reverse(s) reverse(s.begin(), s.end()) #define c_sort(s) sort(s.begin(), s.end()) #define ..
-
백준 10026번: 적록색약깊이우선탐색(DFS) 2018. 7. 5. 20:01
https://www.acmicpc.net/problem/10026 1. 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 키워드 - DFS 해당 영역에서 구할 수 있는 영역은 4 구역이다. R,G,B 기준 일반인이 구별하는 색상 이다. 적록색약인 사람은 G 를 못보기 때문에 G 영역을 ..
-
백준 2606번: 바이러스깊이우선탐색(DFS) 2018. 7. 1. 20:46
https://www.acmicpc.net/problem/2606 1. 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 2. 알고리즘 키워드 - DFS, BFS 참고 - 다음엔 BFS 로 풀어 봐야겠다. 3. 코드 #inc..
-
백준 2573번: 빙산깊이우선탐색(DFS) 2018. 7. 1. 20:06
https://www.acmicpc.net/problem/2573 DFS 응용 문제 탐색 되는 영역이 2 개가 되는 횟수를 출력 키워드 - DFS 참고 - 일년이 지나면 주변 경계값에 0 이 있는 개수 만큼 줄어 든다. DFS 코드 작성한 거보다 next 코드 작성 한게 더 힘들 었다. Source #include #include #include #include #include #include #include #include #include #include #include #include #include // vs 에서는 안필요 한대 BOJ 에서 필요함 using namespace std; #define MAX_SIZE 100 #define INF 0x7fffffff #define CENDL "\n" #..
-
백준 10451번: 순열 사이클깊이우선탐색(DFS) 2018. 6. 24. 13:58
https://www.acmicpc.net/problem/10451 1. 문제1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 (1234567832781456) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.순열을 배열을 이용해 (1…i…nπ1…πi…πn) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이..
-
백준 2468번: 안전 영역깊이우선탐색(DFS) 2018. 6. 23. 20:34
https://www.acmicpc.net/problem/2468 1. 문제물에 잠기지 않는 영역을 구하는 문제 2. 알고리즘키워드 - DFS, FloodFill 높이가 2 일때 다 잠긴다. 높이 3 일 때 안전한 영역 4개 높이 4 일 때 안전 영역 5개 높이 5 일 때 안전 영역 5개 높이 6 일 때 안정 영역 4 개 높이 7 일 때 안전 영역 2 개 높이 8 일 때 안전 영역 1 높이 9 일때 없다. 탐색할 노드의 값이 높이 보다 큰 경우 DFS 탐색 횟수를 카운트 하여 가장 많은 영역을 구한다. 3. 코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859..
-
백준 11724번: 연결 요소의 개수깊이우선탐색(DFS) 2018. 6. 23. 16:50
https://www.acmicpc.net/problem/11724 1. 문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 2. 알고리즘키워드 - DFS [ Figure 1 ]1번 TestCase 는 연결 요소가 두 개다. [ Figure 2 ]2 번 TestCase 에서는 모든 정점이 연결되어 있어 연결 요소는 하나다. 3. 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include #include #i..