알고리즘/BFS_DFS
-
[백준-1963]-[BFS]-소수경로알고리즘/BFS_DFS 2018. 11. 23. 01:04
문제 경로 : https://www.acmicpc.net/problem/1963 이 문제는 까먹었던 소수에대해서 다시 기억하게 해준 고마운 문제다. 먼저 소수는 1 과 자신 이외에 나누어지지 않는 수를 소수라고 한다. 그럼 소수인지 아닌지 어떻게 확인할까?? N이라는 수가 있다면 2부터 N 전의 정수로 전부 나눠서 하나라도 나누어지는 값이 있다면 그것은 소수가 아니고 나누어지는 값이 없다면 그 값은 소수이다. 1은 소수가 아니다. 그래서 1은 예외처리를 해줘야 한다. 소수 판별하는 소스 12345678910111213 public static boolean isPrimeNum (int num) { boolean result = true; if(num == 1) return false; for(int i ..
-
[백준-2573]-[DFS-BFS]-빙산알고리즘/BFS_DFS 2018. 11. 21. 14:17
문제링크 : https://www.acmicpc.net/problem/2573 이 문제는 낮은 합격률에 겁을 먹고 문제를 잘못 이해해서 시간을 엄청 뺏긴 문제이다. 1년이 지나면 높이가 1이 낮아진다 하고 푸니 정말 쉽게 풀었다. 하지만 계속해서 결과가 틀렸다 나오길래 멘붕이 왔다. 다시한번 문제를 읽어보면서 문제를 제대로 읽지 않고 코딩을 한 과거의 내가 원망스러웠다. 이문제에서 중요하게 봐야할 문구가 두개 있다. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다. (i, j..
-
[백준-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 이므로..
-
[백준-2606]-[BFS]-바이러스알고리즘/BFS_DFS 2018. 11. 20. 15:14
문제 링크 : https://www.acmicpc.net/problem/2606 이문제는 시작점부터 BFS를 돌고 본인을 제외하고 접근한 노드들의 수를 세면 끝나는 문제이다. 입력받은 모든 노드들이 연결 돼 있다면 모든 노드들을 접근하겠고연결이 안된 노드들은 BFS로 접근이 안된다. 정답률이 높은데 그만큼 쉬운 문제이다. 소스 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import ja..
-
[백준-2178]-[BFS]-미로탐색알고리즘/BFS_DFS 2018. 11. 20. 14:19
문제 링크 : https://www.acmicpc.net/problem/2178 이문제는 BFS DFS 모두 풀 수 있다.하지만 본인은 BFS로 풀었다. 굳이 DFS로 풀지 않은 이유는 BFS가 더 땡기고 아직은 재귀적 생각이 짧아서 효율적인 재귀 함수를 구현을 잘 못하겠어서도 있다.좀 더 공부를 하면서 시간을 단축하는 DFS를 작성할 수 있었으면 좋겠다. 이문제는 앞서 있는 다른 BFS 문제에 비해 매우 쉬운 난이도이다. 각 칸을 BFS로 접근하면서 칸 수만 세면 끝나기 때문이다. 벽에 도달하면 패스하고 방문한 이력이 있으면 패스하면 된다. 한번이라도 방문을 했으면 무조건 적으로 먼저 방문했을때의 값이 작다. BFS는 Queue에 쌓아 하나씩 선입선출로 꺼내 사용하기 때문에 level 단위로 처리된다...
-
[백준-7569]-[BFS]-토마토알고리즘/BFS_DFS 2018. 11. 20. 13:06
문제링크 : https://www.acmicpc.net/problem/7569 이 문제는 7576 문제의 확장형이다.문제를 접근 하는 방법은 단 1의 차이점도 없고 다만 2차원 배열에서 3차원 배열로 변한거 뿐이다. 7576번에서는 (row -1, col), (row + 1, col) , (row, col - 1), (row, col + 1) 4개 위치에 있는 토마토만 익히면 됐지만 이번 문제에서는 참조할 좌표가 두개가 더 추가된것 뿐이다. 참조할 좌표 height + 1, row, col height - 1, row, col height, row - 1, col height, row + 1, col height, row, col -1height, row, col +1 문제를 접근하는 방법은 7576번 ..
-
[백준-7576]-[BFS]-토마토알고리즘/BFS_DFS 2018. 11. 20. 12:09
문제 링크 : https://www.acmicpc.net/problem/7576 이 문제는 당연히 BFS 로 풀어야 하는 문제다. 하지만 생각을 제대로 하지 못하면 어리석은 소스로 시간 초과에 걸리는 상황을 만들 수 있다. 먼저 어리석은 생각으로 한 코딩을 올리면서 한번의 반성을 하고 시간 초과를 해결한 소스를 올리면서 다시 반성해야겠다. 일단 아주 쉽게 아 BFS로 안익은 토마토 카운트가 0일 될때까지 BFS를 돌리면서 한칸씩 익히면 되겠구나! 이 생각을 아주 엇나가게 했다. 내가 한 잘못된 생각은 이렇다. 시간초과 소스1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556..