반응형 Algorithm/DFS15 [DFS, 난이도 중상] 프로그래머즈, 여행경로 여태 백준에서 DFS/BFS 문제를 풀 때는 노드명을 정수로 두고 풀었는데.. 노드명이 문자열이라 적응이 잘 안됐다. C++ vector의 요소들은 정수로된 인덱스로 다룰 수 있는데 , 이번 문제에서는 벡터만으로 풀기에는 꽤 난이도가 있어보였다. 그래서 파이썬의 딕셔너리와 유사한 기능을 하는 C++의 map의 도움을 받았다. map은 key와 value쌍으로 되어있는 구조이다. 하나의 출발점에서 여러 경로로 이동하는 경우를 고려해야 하므로 value에는 여러 요소를 담을 수 있는 vector을 넣기로 했고, 그 vector안에서도 도착점 정보 뿐만아니라 방문 여부까지도 알 수 있게 pair로 도착점, 방문여부 쌍을 이루었다. 모든 도시를 방문 해서 티켓을 모두 소진이 되었음을 확인 할 때 까지 dfs를 .. 2020. 9. 24. [DFS, 난이도 중상] 백준 1937번 욕심쟁이 판다 알고리즘이 DP로 분류되어 있긴 하지만 DFS에 더 가깝다고 생각했고, 내 풀이법은 일반적인 DFS풀이와 전혀 다를 것이 없기 때문에 카테고리를 DFS로 했다. 이전값을 참고하여 현재 정보를 갱신한다는 점에선 동적계획법이기도한 문제이다. https://kimcoder.tistory.com/48 [동적계획법, 난이도 중상] 백준 1520번 내리막 길 이 문제는 동적계획법과 DFS를 동시에 적용해야 하는 문제이다. 백준 1890번 점프와 접근법은 비슷하다. https://kimcoder.tistory.com/47 [동적계획법, 난이도 상] 백준 1890번 점프 동적계획법과 DFS를 동시� kimcoder.tistory.com 백준 1520번이 내리막길이라면, 이 문제는 오르막길이다. 판다는 자신이 있는 좌표.. 2020. 8. 17. [DFS, 난이도 중] 백준 1389번 케빈 베이컨의 6단계 법칙 이 문제는 BFS로 푸는게 훨씬 간단하다. 왜냐하면 최단경로를 구해야 하는 문제이기 때문이다. DFS로 하면 꽤 신경써야될 것들이 있다. 깊이 매개변수를 추가해줘야하고 DFS를 다 돌면 방문처리를 해제해야한다. 본인은 DFS연습 차원으로 DFS로 풀었기 때문에 DFS이용 기준으로 난이도를 중으로 정했다. BFS로 풀었다면 중하~하 사이가 아닐까 싶다. 주어진 예제를 양방향 그래프로 도식화한 그림이다. dfs의 매개변수는 각각 (출발점,도착점,깊이) 이다. 출발점=도착점인 경우 깊이의 최솟값을 갱신하는 처리를 해준뒤 하나의 dfs함수를 종료한다. 노드n이 노드1~n까지 모두 탐색하여 구한 최단경로의 합은 kevin[n] 이다. kevin의 최솟값을 가지는 최초의 인덱스값을 출력하면 문제는 해결된다. BFS.. 2020. 8. 16. [DFS, 난이도 중하] 백준 10026번 적록색약 (BFS, DFS 모두 사용) 제출번호 21761134가 DFS로, 제출번호 21760828이 BFS로 해결해서 정답처리된 소스코드이다. 맵의 모든 구역을 탐색하면서 탐색하지 않은 좌표에서 BFS/DFS를 호출하여 , 인접 색들을 만나면 전부 방문처리를 한다. BFS/DFS를 호출할 때마다 group 카운트를 늘려나가서 몇 개의 그룹으로 이루어져 있는지 계산하면 된다. 적록색약이 아닌사람에 대해서 map배열, visited배열, group변수를, 적록색약인 사람에 대해서 map2배열, visited2배열, group2변수를 썼다. 두 가지 경우에 대해 모두 수행해주었다. 적록색약인 사람인 경우 모든 초록색을 빨강색으로 인지하는 것으로 가정했다. 즉 map2에서는 R 혹은 B만 존재한다. 애초에 모든 G를 R로 바꾼 것이다. 이렇게 접.. 2020. 8. 15. [DFS, 난이도 중하] 백준 11403번 경로 찾기 표를 직접 이용하는 방법 보다는 그래프로 도식화해서 해결하는 것이 더 편한 방법 같다. 고로 도식화를 하여 DFS로 해결 하였다. 아래 그림은 예제 입력2 의 인접행렬을 그래프로 도식화 한 것이다. 경로벡터 a에 간선 정보들을 모은 후 각 노드마다 dfs를 수행해주면 된다. dfs의 매개변수는 s, x로 설정했는데 s는 첫 출발 노드고, x는 현재 노드이다. 접근 할 수 있는 노드들을 모두 방문하며 ans[첫출발 노드][현재 노드]를 1로 갱신 해나가는 전략이다. 이 문제가 정답률이 52%로 높은 편인 이유는 예제를 2개나 주었고, 시간 및 노드 제한이 널널해서 인 것같다. 이 소스코드에서 노드별로 dfs를 수행할 때 자신보다 낮은 노드 번호를 가지는 노드의 접근 가능 노드 목록은 이미 계산이 되어 있는.. 2020. 8. 14. [DFS, 난이도 중상] 백준 1987번 알파벳 DFS 첫 문제부터 조금 욕심을 내서 정답율 30%인 문제를 골랐다. 한 번만에 성공해서 되게 좋았다. DFS는 주로 스택이나 재귀 함수를 이용하는데, 개인적으로 재귀 함수가 훨씬 편한 것 같다. 제일 먼저 node라는 이름을 가진 구조체를 선언하였다. BFS 문제들을 풀면서, 탐색 문제에는 구조체를 활용하는것이 효과적이라는 사실을 깨달아서 바로 활용해 본 것이다. 구조체 안의 변수는 깊이,좌표 정보들로 구성시켰다. 시작점은 1행 1열이므로 좌표는 (0,0), 깊이는 1인 구조체 node를 맨 처음dfs 매개변수에 넣으며 시작했다. 상하좌우를 탐색하며 현재까지 처음 마주보는 알파벳만 그 좌표를 방문처리 하고 재귀함수를 호출했다. 그리고 재귀함수에서 나왔을 때 방문처리는 취소했다. dfs문 중간에서 -65.. 2020. 8. 12. 이전 1 2 다음
