알고리즘/BFS_DFS
-
[백준 2468] - [DFS BFS] - 안전영역 (JAVA)알고리즘/BFS_DFS 2018. 12. 27. 18:17
문제 링크 : https://www.acmicpc.net/problem/2468 이 문제는 정말 분노를 유발하는 문제였다. 일단 문제를 풀기에 앞서 이문제를 풀기전에 꼭 명심해야할 사항을 먼저 적고 시작하겠다. 각 영역의 높이를 기준으로 문제를 풀면 틀린다. 비가 안왔을 경우에 대해서도 처리를 해야한다. 위의 말이 무엇인지는 문제를 풀다보면 이해가 저절로 갈것이라 생각한다. 계속 문제가 틀렸다 나오길래 멘탈이 무너진 상태에서 질문 검색을 통해 확인해보니 비가 온 높이로 잠기는 안전영역을 확인하는것이었다. 안전 영역 자체의 높이로만 DFS 혹은 BFS 탐색을 돌리면 비가 안왔을 경우인 비의 높이 0 에대해서 대응을 하지 못하기 때문에 계속 틀리다는 결과를 받았다. 문제가 매우 모호한 문제이기에 이 문제를 ..
-
[백준 5427] - [BFS 최단거리] - 불 (JAVA)알고리즘/BFS_DFS 2018. 12. 20. 13:57
문제링크 : https://www.acmicpc.net/problem/5427 이 문제는 BFS를 가지고 풀면 되는데 좌표정보를 갖는 queue를 2개를 사용해야 한다. queue1은 불의 좌표를 저장하는 queue로 사용하고queue2는 사람의 좌표를 저장하는 queue로 사용한다. 입력 값이 숫자가 아닌 # * . @ 형식의 char 타입 데이터 이기 떄문에 나는 이 char를 custom 해서 int 형의 값으로 변경했다. # --> -1* --> -2. --> 0@ --> 1 방문 정보를 저장할 visited 배열을 사용하기 싫어서 빈 공간은 0으로 두고 사람이 움직일때 좌표의 값이 0인 위치만 이동하게 소스를 작성했다. 복잡하다면 char형의 이차원 배열과 visited 배열을 두개 생성하고 문..
-
[백준 1697] - [bfs] - 숨바꼭질알고리즘/BFS_DFS 2018. 12. 19. 21:06
문제 링크 : https://www.acmicpc.net/problem/1697 이 문제 힌트에 백트래킹으로 돼 있어서 백트래킹으로 풀었다가 후회하고 제일 간단한 단순 bfs로 풀었다. 분명 백트래킹으로 풀 수 있는 문제긴 하다. 하지만 쉽게 풀 수 있는 방식이 있었기에 이번에는 쉬운 방식으로 풀려고 한다. 간단하게 생각해서 1회전에 방문하는 위치 는 n-1, n+1, n*2가 되고 i번 만큼 반복하면서 목표 위치에도달했을때의 반복 횟수를 리턴해주면 된다. 소스123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051import java.util.LinkedList;import java.util...
-
[백준 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 탐색을 시도하면 문제는 아주 쉽게 풀린다. 모든 좌표에 방문여부와 배추가 심어진 좌표인지..
-
[백준 1260] - [DFS BFS] DFS와 BFS (JAVA)알고리즘/BFS_DFS 2018. 12. 2. 15:02
문제 링크 : https://www.acmicpc.net/problem/1260 이 문제는 DFS와 BFS를 제대로 이해하고 있는지 파악하는 문제로 보면 된다. 이미 여러개의 DFS BFS 문제를 포스팅을 했지만 이번에 푼 문제가 이 문제여서 DFS와 BFS의 개념을 한번 복습을 해보자. DFS는 깊이 우선 탐색(Depth First Search)의 약자이고 BFS는 너비 우선 탐색(Breadth First Search)의 약자이다.노드들을 탐색할때 먼저 탐색된 노드의 자식노드를 우선적으로 탐색하는것을 말한다. 만약 위의 노드들을 1을 기준으로 DFS로 조회한다고 하면 어떻게 될까? 먼저 기준점 1의 자식노드들을 확인한다. 1의 자식노드들은 {2, 3} 이 있고 2부터 탐색을 시작한다. 2의 자식노드들은..
-
[백준-9466]-[DFS]-텀 프로젝트(JAVA)알고리즘/BFS_DFS 2018. 11. 26. 17:14
문제링크 : https://www.acmicpc.net/problem/9466 이 문제는 백준_2668번 문제 와 비슷한 문제지만 절대 비슷하게 풀면 큰일 난다. 본인의 2668 번 문제대로 풀었더니 시간 초과가 발생했다. 이전글 보기 --> 2018/11/23 - [알고리즘/BFS_DFS] - [백준-2668]-[DFS]-숫자고르기 어떤 부분이 문제가 될까 확인을 해보니 사이클 조회를 한번 한 이후 초기화 하는 과정에서 시간을 오래 잡아 먹는것으로 파악 됐다. 먼저 시간 초과가 발생한 소스를 보면서 왜 문제가 있었는지 확인해보고 이 글을 읽는 다른 사람들은 시간초과의 늪에 빠지지 않았으면 좋겠다. 시간초과 소스 123456789101112131415161718192021222324252627282930..
-
[백준-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는 초기화 해주..
-
[백준-1726]-[BFS]-로봇알고리즘/BFS_DFS 2018. 11. 23. 01:30
문제 링크 : https://www.acmicpc.net/problem/1726 이 문제를 풀려고 하는데 계속 틀렸다고 하는 분들에게 드리고 싶은 말은 문제 제대로 보셨나요?? 이다..수없이 문제를 수정하고 아.. 왜 안되지.. 잘되는데.. 했지만 문제를 제대로 읽지 않고 문제를 풀었기에 문제에서 큰 부분을 뺴놓고 문제를 풀었다. 명령 1. Go k - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다.명령 2. Turn dir - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 명령 1 Go K 는 본인의 현재 방향으로 1 ~ 3을 움직인다. 나는 이 부분을 그냥 무조건 직진! 으로만 이해를 했다. 한번의 명령으로 최대 3칸만 움직일..