BFS
-
[백준 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...
-
[백준-2667]-[BFS]-단지번호 붙이기알고리즘/BFS_DFS 2018. 11. 20. 15:56
문제 링크 : https://www.acmicpc.net/problem/2667 이 문제는 처음에는 접근법이 감이 안올 수 있다. 입력받은 이차원 배열을 하나씩 접근해 나가면서 0 이면 무시하고 1이고 BFS로 접근 이력이 없으면 그 좌표를 기준으로 BFS를 돌리면 된다. 예제를 기준으로 그림으로 보면 이해가 빨리 된다.7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 위의 예제 입력으로 표를 만들면 아래 처럼 나온다. 01 1 0 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 0 0 좌표 (0, 0) 부터 조회를 한다. (0,0) 은 0 이므로..