DFS
-
백준 14502번 연구소 :: 마이구미알고리즘 풀이/그래프 2017. 10. 3. 21:43
이 글은 백준 알고리즘 14502번 "연구소" 를 풀이한다.삼성 SW 역량 테스트의 기출 문제이다.DFS를 통해 문제를 해결할 수 있지만, 다소 복잡한 문제이다.14502번 - https://www.acmicpc.net/problem/14502DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로..
-
백준 1967번 트리의 지름 :: 마이구미알고리즘 풀이/그래프 2017. 10. 3. 21:24
이 글은 백준 알고리즘 1967번 "트리의 지름" 를 풀이한다.DFS를 통해 문제를 해결할 수 있다.1967번 - https://www.acmicpc.net/problem/1967기본 지식이 부족하다면 관련 글을 참고 바란다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된..
-
백준 1941번 소문난 칠공주 :: 마이구미알고리즘 풀이/그래프 2017. 9. 15. 23:52
이 글은 백준 알고리즘 문제 1941번 "소문난 칠공주" 를 풀이한다.기본적인 DFS를 통한 백트래킹을 활용해서는 이 문제를 해결할 수 없다.문제 접근에 있어, 아이디어가 필요한 문제이다.1941번 - https://www.acmicpc.net/problem/1941DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지..
-
백준 2026번 소풍 :: 마이구미알고리즘 풀이/그래프 2017. 8. 15. 00:24
이번 글은 백준 알고리즘 문제 2026번 "소풍" 을 다뤄본다.종만북이라 불리는 책에서도 나오는 문제이긴 하나, 응용된 문제이다.문제 풀이는 DFS를 통한 백트래킹을 이용한다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 원장선생님께서는 K(1≤K≤62)명에게 소풍을 보내려 한다. 원장선생님께서는 1부터 N까지 번호가 붙은 N(K≤N≤900)명의 학생들 중에서 K명의 학생들을 소풍에 보내려고 한다. 그런데 원장선생님께서는 중간에 싸움이 일어나면 안되므로 소풍을 갈 학생들이 모두 서로 친구 사이이기를 원한다. 원장선생님께서는 이러한 일을 이번에 조교로 참가한 고은이에게 친구 관계에 대한 ..
-
백준 2573번 빙산 :: 마이구미알고리즘 풀이/그래프 2017. 8. 4. 00:23
이번 글은 백준 알고리즘 2573번 "빙산" 을 다뤄본다.정답 비율이 20%대로 어렵게 보이지만 비율 대비 쉬운 문제가 된다.본인은 DFS를 통해 문제를 풀이하겠다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 문제를 보다시피, 1년이 지날 수록, 빙산의 높이가 상하좌우에 있는 0의 횟수만큼 줄어드는 것을 볼 수 있다.그리고 그림3과 같이 2개 이상으로 분리되는 시점을 찾는 문제이다.분리된 빙산은 {3, 2}, {3}, {4} 가 된다.그래프에서 이러한 빙산의 영역을 "연결 요소"라고 표현한다.즉, 이 문제는 연결 요소의 개수를 2개 이상이 되는 시점을 찾는 문제가 된다. 코드 흐름은 ..
-
백준 6603번 로또 :: 마이구미알고리즘 풀이/그래프 2017. 8. 1. 21:24
이번 글은 백준 알고리즘 문제 6603번 "로또" 를 다뤄본다.문제를 보다시피, 모든 경우의 수를 찾아야한다.DFS에서 백트래킹을 응용하여 문제를 해결할 수 있다.이 문제의 코드를 이해한다면, 재귀 함수와 친해질 수 있을 것이다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 독일 로또는 {1, 2, ..., 49}에서 숫자 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 숫자 중 k(k>6)개의 숫자를 골라 집합 S를 만든 다음 그 숫자만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 숫자를..
-
백준 1987번 알파벳 :: 마이구미알고리즘 풀이/그래프 2017. 7. 22. 22:36
이번 글은 백준 알고리즘 문제 1987번 "알파벳" 을 다뤄본다.문제 풀이는 DFS를 응용하여 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있..
-
백준 2468번 안전 영역 [DFS] :: 마이구미알고리즘 풀이/그래프 2017. 6. 18. 22:48
이번 글은 백준 알고리즘 문제 2468번 "안전 영역" 을 다뤄본다.정올 초등부에서 출제된 문제이다.초등부이지만, 정답률은 30%인 것을 볼 수 있다.DFS, BFS - http://mygumi.tistory.com/102 문제 접근은 DFS 또는 BFS를 활용할 수 있다.기본적인으로 DFS 및 BFS 기본 지식을 가지고 있다면 충분히 풀 수 있다.여기서는 DFS를 통해 문제를 풀어보겠다. 위 그림은 높이가 4와 6의 경우를 나타내고 있다. 흰색 영역의 수를 찾는 문제가 된다.그래프에서는 이 영역을, 연결 요소의 개수라고 볼 수 있다.즉, DFS 탐색이 이루어지는 횟수 중 가장 큰 수가 정답이 된다. 높이를 1부터 100까지 경우 각각 DFS 탐색을 하면 된다. public static void dfs(..