BFS
-
[그래프] 백준 5214Dev/알고리즘 2020. 8. 27. 17:01
BFS를 사용해서 구현하되, 각 역간의 직선 연결로 할 시 java에서는 무조건 메모리 초과가 나게 되는 구조이다. C, C++에서는 최대한 심플하게 인접 리스트를 활용하면 가능할 것으로 보인다. 해결 방법은, 각 역간을 연결하는 정보(하이퍼튜브)를 따로 리스트를 만들어 관리하고 각 역은 해당 하이퍼튜브를 바라보는 방향으로 인접 리스트를 구현하고 Queue를 이용해 최종 역을 찾아가는 과정을 수행하면 되는데, 최종 결과 출력 시 하이퍼튜브에 방문했던 수는 제외하고 각 역 간을 방문했을 때의 숫자만을 가지고 최종 결과를 만들어야 한다. 하이퍼튜브 방문 횟수를 빼기 위해 애초에 count를 계산할 때 역->하이퍼튜브 방문이면 +를 하지 않고, 하이퍼튜브->역 방문일 경우 +하는 방향으로 계산했다. 큐에 모든..
-
[그래프] 백준 5567: 결혼식Dev/알고리즘 2020. 8. 27. 10:38
문제는 간단하게 기준이 되는 1번의 친구들, 그 친구들의 친구들까지 초대(목록에 추가)한다는 내용이다. BFS를 사용해서 구현했다. 트리 구조를 활용해 기준이 되는 1번을 level 0으로 잡고, 1번의 친구들을 level 1, 1번의 친구들의 친구들을 level 2로 잡고 level 2까지의 사람들만 count해서 결과를 출력하는 방향으로 구현했으며 level은 따로 배열을 생성해서 정해줬다. 소스 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 5..
-
[그래프, BFS&DFS] 1260, 2606 문제 풀이Dev/알고리즘 2020. 8. 26. 17:36
두 문제 다 DFS와 BFS, 그래프에 대한 개념 문제라고 생각한다. 1260 문제 풀이 그래프는 인접 리스트, 인접 행렬로 나누어짐 인접 리스트는 각 원소 별로 인접해 있는 주변 원소들을 각 원소와 연결시킨 리스트로 표현하는 것. 인접 행렬은 배열을 선언해 전체 배열 중 인접 원소들을 true 변환하는 것이라고 볼 수 있음. 인접 행렬로 문제를 푼 결과는 해당 페이지에서 확인 가능하다. github.com/saturdayAlgo/acmicpc/blob/master/sw/java/p01260/array/Main.java saturdayAlgo/acmicpc Contribute to saturdayAlgo/acmicpc development by creating an account on GitHub. gi..
-
[알고리즘] DFS와 BFS 정리Dev/알고리즘 2020. 6. 12. 01:53
DFS: Depth First Search 깊이를 우선으로 하는 검색 방법이다. 재귀 함수, 스택으로 구현한다. BFS: Breadth First Search 너비를 우선으로 하는 검색 방법이다. 큐로 구현한다. 위의 그림은 7을 찾아가는 과정을 DFS, BFS로 표현한 그림이다. DFS는 빨간색으로, BFS는 파란색으로 그려봤다. DFS는 tree의 level과 관계 없이 최상단(1)부터 각각의 leaf node까지를 찾아본 후, 다음 leaf node까지를 계속해서 검색하다 7이 나오면 종료한다. BFS는 같은 level의 node들을 모두 검색하고, 검색한 node들의 하위 node들을 검색하는 방식으로 작업이 수행된다. 그래서 DFS의 경우 5번, BFS의 경우 6번만에 7을 찾아 작업을 종료했다.