그래프
-
[그래프] 백준 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..