반응형 알고리즘 PS/백준 알고리즘31 [백준] 1697번 - 숨바꼭질 (Java) https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 1차원 그래프이다. 2. N의 위치에서 할 수 있는 액션은 3개이다. 2-1. nx = 2 * x 2-2. nx = x+1 2-3. nx = x - 1 3. BFS로 위 3개 액션을 for(1 to 3)문으로 돌려서 탐색한다. 4. 방문거리는 visited 배열에다가 이전거리+1을 해서 기록하고, 방문한 노드는 스킵한다. 5. N과 K가 같을 때 BFS 수행 전에 .. 2022. 9. 8. [백준] 1520번 - 내리막 길 (Java) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. map에는 높이 정보가 주어지고, 탐색은 상하좌우로만 가능하다. 2. 경로를 찾는데 높이가 지금보다 낮은 쪽으로만 이동 가능한 경로를 찾는다. 3. 가능한 경로의 개수를 찾는다. 4. dfs 파라메터로 좌표 정보를 넘겨준다. import java.util.*; /* [백준] 1520번 - 내리막 길 (Java) */ public class Main { int N, M; int A[][]; bool.. 2022. 9. 7. [백준] 7576번 - 토마토 (Java) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 익은 토마토는 1, 안익은 토마토는 0, 빈칸은 -1로 주어진다. 2. 익은 토마토의 상하좌우로 영향을 줘서 안익은 토마토가 하루가 지나면 익게 된다. 3. bfs 탐색으로 상하좌우로 탐색할 때 0이면 1로 바꾸고 탐색을 계속한다. 3-1. 상하좌우 검색 후에 누적거리+1 을 하자. 4. 출발점이 없으니 메인함수에서 for문을 돌려서 1이 나오면 bfs를 호출하자. 5. 0이.. 2022. 9. 7. [백준] 2644번 - 촌수계산 (Java) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 1. 부모-자식 관계지만 거슬러 올라갈 수 있으므로 방향이 없는 트리와 같다. 2. DFS 파라미터로 정점 번호와 count를 넘겨준다. 3. Y를 찾지 못하면 flag를 둬서 -1을 출력한다. import java.util.*; /* [백준] 2644번 - 촌수계산 (Java) */ public class Main { static int N, M, X, Y; ArrayList.. 2022. 9. 5. 이전 1 2 3 4 다음 반응형
