본문 바로가기

Algorithm/DFS

BaekJoon 5567 결혼식 2019. 1. 21. Link https://www.acmicpc.net/problem/5567 소스결과 2112 KB / 4 ms 출처 baekjoon, JOI 2010 언어 C++ 17 분류 그래프 이론 설명 상근이가 결혼식에 학교 동기 중 자신의 친구와, 친구의 친구를 초대할 때 상근이가 초대할 친구의 수를 구하는 문제이다. 동기의 수가 최대 500명이기 때문에 인접리스트를 써도 무방하다. 또한 a - b가 친구이면 b - a도 친구라는 점에서 양방향 그래프로 추가 하면 된다. 상근이를 기준으로 깊이가 2 이하인 친구들의 수를 출력하면 된다. 동기의 수만큼 배열을 만들어 깊이를 저장하는 방법도 있고 깊이가 2까지 진행 하게 DFS를 진행하는 방법도 있다. 아래 소스코드는 두 방법이 아닌 큐를 이용해서 친구를 구한 후 친..
Baekjoon 1405 미친 로봇 2019. 1. 21. Link https://www.acmicpc.net/problem/1405 소스 결과 1988 KB / 40 ms 출처 Baekjoon 언어 C++ 17 분류 DFS, 브루트 포스, 탐색 설명 통제할 수 없는 미친 로봇이 n번의 행동 중 로봇의 이동 경로가 단순한 경우의 확률을 구해 내는 문제 앞선 문제의 경우와 다른 점은 확률을 구해야 한다는 점이 가장 눈에 띈다. 이동 경로를 구해야 되는 문제이기 때문에 BFS/DFS를 사용 해야 한다. 하지만 이번 문제는 최단 경로를 구하는 문제가 아니기에 BFS를 사용하는것은 적절하지 않아보인다. 또한 로봇이 이동 할 수 있는 모든 경로에 대해서 탐색 해야한다. DFS를 진행 하면서 브루트 포스가 자동으로 진행 되기 때문에 크게 유의하지는 않아도 된다. 맵의 크기..
BaekJoon 1389 케빈베이컨의 6단계 법칙 2019. 1. 6. Link : https://www.acmicpc.net/problem/1389 소스결과 : 1996 KB / 0 ms 출처 : Backjoon 언어 : C++17 설명 케빈 베이컨의 여섯다리 : 위키백과_케빈 베이컨의 여섯다리 를 구현하는 문제 한 사람을 기준으로 친구 관계에 있는 사람들을 이어나가 몇 다리만에 그 사람과 연관이 있어지는지 확인 하는 문제 문제에서는 6단계의 법칙이라 했지만 검색을 하면 여섯다리로 나온다 자세한 내용은 위 링크를 참조, 또는 위 링크의 출처를 참조 DFS를 사용하면 손쉽게 결과가 구해진다. 몇가지 주의 할 점이라면 방문한 사람을 다시 방문해야 하는 경우가 존재 한다 예를들어 1 -> 2 -> 4 -> 5 의 경우 거리는 3이 되지만 동시에 1 -> 5 라면 거리를 1로 수..
BaekJoon 6603 로또 2019. 1. 5. Link : https://www.acmicpc.net/problem/6603 소스 결과 : 1988 KB / 68 ms 출처 : BackJoon / University of Ulm Local Contest 1996 F번 설명 DFS를 이용하여 조합을 생성해 출력하는 문제 이와 비슷한 문제도 여럿 존재 하지만 문제 제목이 끌렸다. 최대 숫자가 13개 이기에 DFS로 해도 시간이 100ms 이내로 나온다. 알고리즘 1. 숫자 k 를 입력받은후 k길이의 vector 생성 2. k개의 숫자를 입력 받은 후 DFS에 사용할 checker 배열 초기화 3. dfs 실행 3.1 현재 true의 개수가 6개인지 확인, 일치하면 checker에서 true인 값을 출력후 return 3.2 현재 탐색하는 pos의 che..
BaekJoon 11724 연결 요소의 개수 (DFS) 2019. 1. 1. Link : https://www.acmicpc.net/problem/11724 소스 결과 : 2964 KB / 248 ms 출처 : BackJoon 설명 자료구조 책에서 DFS / BFS를 설명할 때 예시로 자주 들어지는 문제 방향이 없는 그래프 이기에 간선을 행렬로 저장시 간선을 양방향으로 저장 x y 가 주어진다면 xy와 yx를 둘다 등록해야 한다. 정점의 개수가 최대 1000개 인접 행렬 사용시 1,000 * 1,000 = 1,000,000개 = 400 만 Bytes ( int ) 간선 행렬 사용시 m * 2 = n * (n - 1) / 2 * 2 = 1,000 * 999 = 999,000 = 399.6 만 Byte ( int ) 둘다 3 MB 정도 밖에 사용하지 않고 차이도 별로 없기에 인접행렬..
BaekJoon 1987 알파벳 2019. 1. 1. Link : https://www.acmicpc.net/problem/1987 소스 결과 : 1984KB 488ms 출처 : BackJoon, Croatian Highschool Competitions in Infomatics 2002 Regional Competition Jonior 설명 DFS 문제 조건 1. 시작하는 칸도 포함 : 즉 최대값은 1부터 시작 2. 칸을 기준으로 중복 체크를 하는 것이 아닌 현재 칸의 알파벳을 밟은 적이 있는지를 검사 사용 입력 케이스 2 20 ABCDEFGHIJKLMNOPQRST BCDEFGHIJKLMNOPQRSTU 21 3 3 ABC DEF GHI 9 4 4 AAAA BAAA CAAA DEFG 7 2 2 AA AA 1 20 2 AB BC CD DE EF FG GH H..

티스토리툴바