BOJ/C++/DFS/BFS 문제풀이1/#2331(반복수열)/#9466(텀프로젝트)/

C++언어로 모두 작성하였으니 참고하길 바란다. 

1. #2331/반복수열 https://www.acmicpc.net/problem/2331

DFS/Directed Non-Weight Graph/Adjacency list, 

수열을 Directed non-weight Graph 자료구조로 옮겨서 먼저 생각하자. 방향의 근거로는 수열은 1차원 상에서 한 방향으로 수가 계속해서 나열되는 구조이기 때문이다. 각 수열의 원소는 정점, 그것들을 간선으로 수열의 진행 순서대로 이어준다.그래프를 담을 자료구조로는 딱히 Adj list나 Matrix를 사용하지 않고 Hash map을 사용했다.

DFS, BFS중에선 DFS를 사용한다. 그래프 자료구조로 담아서 DFS로 계속 수열을 증가시키면서(다음 노드, 그리고 그 다음노드를 기준으로 탐색할 다다음 노드가 있을때까지 그대로 탐색한다.) 중복되는 원소가 나오는 순간, 종료시키고, 그 중복되는 원소가 처음 발생한 시점 이하의 길이를 구현한다. 

메모리공간을 아끼기 위해서 체크를 하기 위한 자료구조로는 해쉬맵을 사용했고, key에 정점, value 값은 pair로 저장했고, pair에는 순서대로 1. 해당 key 와 간선으로 연결된 다음 정점, 2. 해당 정점이 수열상에 있는 idx(위치)를 기록해뒀다. 그래서 중복되는 정점이 나온다면, 그 정점이 처음 등장했을때 있었던 위치를 고려하여 그 이하의 길이를 출력해주면 된다. 

Source Code: https://github.com/brwnsugr/algorithm/blob/master/boj/2331_repeating_sequence_dfs.cpp 

2. #9466/텀프로젝트 https://www.acmicpc.net/problem/9466

DFS로 푼다.. 구현이 어렵다.

• step: 탐색을 시작한 첫걸음
• nsteps[i]: i지점이 해당 스텝 안에서 몇번째로 방문했는지(즉, 방문 순서)
• steps[i]: i지점을 방문했을 때 어떤 step(첫걸음)으로 방문했는지 값에 저장(ex. steps[2] = 3 : 2번지점은 3번 스텝(첫걸음이 3번)으로 시작해서 방문하였음
• 종료 조건은 방문 순서가 있을 때( 즉, 방문을 했고, nsteps[i]가 0이 아니고 ,순서가 적혀있을 때)

Source code: https://github.com/brwnsugr/algorithm/blob/master/boj/9466_term_project.cpp

3. #4963/섬의개수 https://www.acmicpc.net/problem/4963 

4963번: 섬의 개수

기준 점에서부터 이동할수있는 좌표 케이스가 8가지라는 점에 유의하며 풀면 쉽다.

Source Code: https://github.com/brwnsugr/algorithm/blob/master/boj/4963_number_of_islands.cpp

d 

4. #2178 미로 탐색 

https://www.acmicpc.net/problems/2178

기준 정점으로부터 목표 정점까지 가장 최단 간선으로 이어진 거리는 BFS로 풀도록 하자. 

Source Code: https://github.com/brwnsugr/algorithm/blob/master/boj/2178_maze_search.cpp

5. #2146 다리 만들기 

휴... 복잡한 문제임.. 각 섬의 섬 번호를 마킹해두는 2차원 배열을 하나 더 두고 풀어야 한다. 

Source Code:  https://github.com/brwnsugr/algorithm/blob/master/boj/2146_making_bridge.cpp

우선 여기까지.