DFS
-
[백준 2468] - [DFS BFS] - 안전영역 (JAVA)알고리즘/BFS_DFS 2018. 12. 27. 18:17
문제 링크 : https://www.acmicpc.net/problem/2468 이 문제는 정말 분노를 유발하는 문제였다. 일단 문제를 풀기에 앞서 이문제를 풀기전에 꼭 명심해야할 사항을 먼저 적고 시작하겠다. 각 영역의 높이를 기준으로 문제를 풀면 틀린다. 비가 안왔을 경우에 대해서도 처리를 해야한다. 위의 말이 무엇인지는 문제를 풀다보면 이해가 저절로 갈것이라 생각한다. 계속 문제가 틀렸다 나오길래 멘탈이 무너진 상태에서 질문 검색을 통해 확인해보니 비가 온 높이로 잠기는 안전영역을 확인하는것이었다. 안전 영역 자체의 높이로만 DFS 혹은 BFS 탐색을 돌리면 비가 안왔을 경우인 비의 높이 0 에대해서 대응을 하지 못하기 때문에 계속 틀리다는 결과를 받았다. 문제가 매우 모호한 문제이기에 이 문제를 ..
-
[백준 1012] - [dfs] - 유기농 배추 (JAVA)알고리즘/BFS_DFS 2018. 12. 19. 17:00
문제 링크 : https://www.acmicpc.net/problem/1012 이 문제는 DFS 간단하게 풀 수 있는 문제이다. 다만 주의해야 할 부분이 있는데 제한시간은 1초인데 여러개의 테스트 케이스가 주어지니 제한시간내에 모든 테스트 게이스를 풀기 위해선 불필요한 좌표까지 dfs로 접근할 필요가 없다. 배추의 좌표를 정수형 배열 타입의 큐에 저장한다. 모든 입력이 완료되고 queue가 빌때까지 queue에서 하나씩 추출해가면서 dfs를 돌린다. queue에 있는 좌표는 부조건 배추가 심어저 있는 좌표이다. 추출된 좌표가 이전에 방문한 이력이 없는 경우만 dfs 탐색을 한다. 위에 나열한 순서와 조건으로 DFS 탐색을 시도하면 문제는 아주 쉽게 풀린다. 모든 좌표에 방문여부와 배추가 심어진 좌표인지..
-
[백준-2668]-[DFS]-숫자고르기알고리즘/BFS_DFS 2018. 11. 23. 13:06
문제링크 : https://www.acmicpc.net/problem/2668 이 문제는 사이클이 발생할 때 까지 DFS로 탐색을 진행하면 된다. 만약 사이클이 발생하지 않는다면 visited 정보를 초기화 해주고 사이클이 발생했다면 방문 정보는 초기화 하지 않아야 된다. 12 3 4 5 6 7 3 1 1 5 5 4 6 예제로 받은 데이터로 표를 만들면 위의 표와 같은데 여기서 1을 탐색하면 1의 값이 3 이고 인덱스 3의 값을 탐색한다. 인덱스 3의 값은 1이고 1과 3은 사이클을 돌게 된다. 사이클이 발생하면 visited는 초기화 하지 않는다. 12 3 4 5 6 7 3 1 1 5 5 4 6 2번 인덱스의 값은 1인데 1은 이미 방문 했으므로 사이클이 성립 안된다. 2의 visited는 초기화 해주..
-
[백준-1987]-[DFS-백트래킹]-알파벳알고리즘/백트래킹 2018. 11. 23. 02:38
문제링크 : https://www.acmicpc.net/problem/1987 이문제를 어떻게 접근할까 하다가 간단하겠지 하고 BFS로 풀었는데 절대 BFS풀면 안된다더라..그 이유는 동시에 같은 레벨의 다른 접점을 접근하기 때문에 만약 2레벨의 같은 알파벳이 있으면 방문 여부를 파악하기가 힘들다. 백트래킹으로 가능한 모든 방향을 접근하고 지나간 최대 칸수를 출력해주면 된다. 말이 쉽지 참 힘들었다. 예제는 항상 답이 나오는데 제출을 하면 항상 문제였다. 내가 푼 문제에 반례가 어떤게 있을까 하다가 스스로 예제를 만들어 보았다. 이것만 통과하면 제출해도 정답이 나올거 같다.. 내가 생각해낸 예제는 아래 표다. A B B C EC E D FG D H 만약 단순한 DFS만으로 결과를 도출해낸다면 최대 길이는..