깊이 우선 탐색19 [프로그래머스] 양과 늑대 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이늑대의 수가 양의 수 이상이 되면 양들이 다 잡아먹혀서 안된다. 트리의 0번부터 시작해서 양을 늑대보다 많게 하면서 돌아다닌다. 이때 양의 최댓값을 찾아야한다. 이동이 가능한 노드들을 담는 리스트를 만들었다. 특정 노드를 방문 할 때 그 노드의 자식 노드를 리스트에 담고, 해당 노드는 제거해주었다. 이동가능한 리스트를 들고 dfs탐색을 통해 최댓값을 갱신했다. 리스트에서 노드를 제거할 때 Conc.. 2024. 5. 18. [백준] 1189: 컴백홈 - JAVA https://www.acmicpc.net/problem/1189 풀이(R-1, 0)에서 (0, C-1)로 이동한다. T는 가지 못하는 부분이고, 한번 지나친 곳은 다시 방문하지 않는다. 이동거리가 K인 경우의 수를 구하는 문제이다. 따라서 방문처리를 하며 dfs탐색을 했다. 각각의 경우에 따른 방문처리가 서로 영향을 주어서는 안되기 때문이다. 이동 거리를 1씩 늘려가면서 다음 칸으로 이동했고, 이동 거리가 K가 됐을 때, 도착점에 도달하였을 때 사이클을 종료시켰다. 메모리: 14584KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[][] vector = { { 1, 0 }, { 0, 1.. 2024. 5. 17. [백준] 2668: 숫자고르기 - JAVA https://www.acmicpc.net/problem/2668 풀이사이클을 찾는 문제이다. `arr[i] -> arr[arr[i]]`이런식으로 뽑힌 정수를 인덱스로 하는 숫자를 다시 봐야한다. 처음 시작한 숫자와 같은 숫자가 나오면 사이클이 완성된다. dfs탐색을 통해 뽑힌 정수를 인덱스로 하여 탐색했고 처음 숫자가 나왔을 때 list에 넣었다. 메모리: 14216KB시간: 128ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[] arr; static ArrayList list; static boolean[] visit; public static void main(String[] ar.. 2024. 5. 17. [백준] 2250: 트리의 높이와 너비 - JAVA https://www.acmicpc.net/problem/2250 풀이트리를 격자모양의 틀에 넣을 때 트리의 깊이별로 너비를 구했을 때 최댓값을 찾는 문제. 입력받으면서 트리를 저장하는데, 부모, 왼쪽 자식, 오른쪽 자식을 저장한다. 입력받아서 저장한 후 부모가 -1로 되있는 것이 루트 노드이다. 루트노드부터 중위순회(왼쪽 - 루트 - 오른쪽)하여 탐색하면 열 번호를 1부터 순서대로 부여할 수 있다. 중위순회할 때 트리의 깊이(level)도 함께 넘겨 각 깊이별로 열 번호의 최대와 최소를 저장한다. 중위순회를 마친 후 깊이별로 너비의 최댓값을 구한다. 메모리: 21176KB시간: 256ms언어: Java 11import java.io.*;import java.util.*;public class Main.. 2024. 5. 14. [백준] 15681: 트리와 쿼리 - JAVA https://www.acmicpc.net/problem/15681 풀이트리에 속한 간선의 정보가 주어지고, 루트의 번호가 주어진다. 트리의 정점을 포함해 자신보다 하위에 있는 정점들의 개수를 구하는 문제이다. 먼저 간선의 정보를 인접리스트에 담았다. 루트의 번호부터 dfs탐색을 통해 진행하는데 정점의 개수의 최대값이 크다보니 매번 구하면 시간 초과가 발생할 것 같았다. dp배열을 만들어 dfs탐색을 하며 dp에 저장하고 반환하는 식으로 구현했다. 메모리: 77800KB시간: 812ms 언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> tree; static int[] dp; stati.. 2024. 5. 13. [백준] 24230: 트리 색칠하기 - JAVA https://www.acmicpc.net/problem/24230 풀이트리가 주어지고 트리를 주어진 색으로 칠해야 한다. 한 정점에 색을 칠하면 그 정점의 하위 정점들 모두에게 같은 색을 칠한다. 따라서 루트인 1번 정점부터 시작하여 아래로 내려가면서 색이 다르면 색을 칠해줬다. dfs탐색을 통해 먼저 자식의 부모의 색을 따라서 칠하고 원하는 색과 비교하여 색을 다시 칠했다. 메모리: 111952KB시간: 1684ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, ans; static int[] arr, color; static ArrayList> list; static boolean.. 2024. 5. 13. [백준] 16947: 서울 지하철 2호선 - JAVA https://www.acmicpc.net/problem/16947 풀이서로 연결된 정점들의 번호가 주어진다. 루프를 이루고 있는것을 먼저 찾고 그 루프로부터의 거리를 출력해야한다. dfs탐색을 통해 루프를 탐색했다. 저장된 루프의 정점으로부터 bfs탐색을 통해 루프에 포함되지 않은 정점들이 루프로부터 얼마나 떨어져 있는지 저장하고 출력한다. 메모리: 25788KB시간: 388ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N; static ArrayList> list; static boolean[] loop; static int[] dist; public static void ma.. 2024. 5. 13. [백준] 1937: 욕심쟁이 판다 - JAVA https://www.acmicpc.net/problem/1937 풀이특정 위치에서 시작하여 상하좌우로 움직일 수 있다. 현재 칸보다 숫자가 더 큰 칸으로만 갈 수 있는데 갈 수 있는 최대 칸 수를 구하는 문제. 처음에 dfs로 풀었는데 시간초과가 났다. 모든 칸을 봐야하는데 이미 기록된 칸은 더이상 볼 필요가 없었다. 메모이제이션을 하여 dp배열에 저장된 값이 있다면 그 값을 반환해주고 바로 끝내도록 했다. 메모리: 37148KB시간: 516ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n; static int[][] forest, dp; static int[][] vector = { { .. 2024. 5. 12. [백준] 2251: 물통 - JAVA https://www.acmicpc.net/problem/2251 풀이물통 세 개의 부피가 정해져 있고 초기에는 C물통만 가득 차 있다. A물통이 비어있을 때마다 C물통의 양을 체크하여 저장하면 되는 문제이다. A, B, C물통의 양을 방문처리하기 위해 boolean[][][] 배열을 이용했고, C물통의 양을 오름차순으로 저장하기 위해 TreeSet을 이용했다. dfs탐색을 통해 진행하며 물통의 양을 체크했고, A물통에 물이 있다면 "A물통의 양 + B물통의양"과 "B물통의 용량"을 비교하여 A물통에서 B물통으로 옮기는 경우를 처리했다. 메모리: 23284KB시간: 140ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12. 이전 1 2 다음