백준20 [백준 3055번 / Java] 탈출 ☑️ bfs() 방식은 최단 경로를 찾기 때문에 방문노드를 다시 변경해주지 않아도 된다! (이게 항상 헷갈렸는데 조금은 알 것 같다..) 📝 이 문제에서 까다로웠던 것은 매분마다 물이 찬다는 점이었다. 1분씩 증가할 수록 물이 차는 범위는 늘어난다. 그렇지만 잘 생각해보면 1분일 때 물이 차는 범위, 2분일 때의 범위, 3분.. 각각의 분마다 물의 범위는 일정하다. 즉, 고슴도치가 이동한 횟수에 따라 물이 차는 범위는 일정하므로 메모이제이션을 이용하여 구현했다. ❗️주의할 점은 배열의 복사는 참조만 복사하게 돼서 그냥 할당해서는 안 되고 새로 배열을 할당한 후에 복사해주었다. import java.io.BufferedReader;import java.io.IOException;import java... 2024. 6. 1. [백준 1987번 / Java] 알파벳 재귀 방식으로 안 풀고 싶어서 고민했지만,, 머리가 터질 것 같아서 포기했다...ㅠ항상 중복 체크와 방문이 헷갈렸는데 다시 한번 풀어볼 수 있어서 좋았다. dfs방식을 이용했고 문자열이 중복되거나 탐색이 종료되었을 때 count 값의 최대값을 업데이트 하는 식으로 구현했다. 문자열의 중복체크는 알파벳만 들어간다는 점에서 97~122의 정수로 바꿀 수 있기 때문에 정수 배열 200칸을 만들어 map 처럼 사용했다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;import static java.lang.System.out;public class Main { .. 2024. 6. 1. [백준 1389번 / Java] 케빈 베이컨의 6단계 법칙 - 양방향 매핑- bfs로 최단거리를 찾은 후 최솟값 계산 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int N; static int M; static int min = Integer.MAX_VALUE; static int res = 0; static Map> map = new HashMap(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe.. 2024. 5. 30. [백준 2644번 / Java] 촌수계산 - bfs, 카운트를 방문 배열에 기록- 양방향 매핑 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int N; static int M; static int start; static int end; static int[] visited; static Map> map; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputSt.. 2024. 5. 29. [백준 9019번 / Java] DSLR 최단거리와 비슷하게 가장 짧은 명령어를 구하는 문제이기 때문에 bfs로 구현했다.구현자체는 어렵지 않았지만 시간초과가 걸렸다 ㅠㅠ처음에는 맵을 써서 방문을 처리할까 고민했는데 map은 삽입시 정렬 시간이 걸리는 반면 N의 값이 10000을 넘지 않기 때문에 배열을 이용하여 O(1)의 복잡도로 사용하는게 빠르다고 생각했다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int N; static int[] visited; static class Node { int n; .. 2024. 5. 23. [백준 7576번 / Java] 토마토 bfs는 계단을 올라가듯이 인접한 수행을 마치면 한 계단 올라간다고 개수를 셀 수 있다.이 문제도 토마토가 익는 날짜 수를 알아야 했기 때문에 bfs를 사용했다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int M; static int N; static int count = 0; static int[][] map; static int total; static .. 2024. 5. 23. [백준 1600번 / Java] 말이 되고픈 원숭이 최단거리를 구하는 문제로 bfs를 이용하여 풀었다.내가 막혔던 부분은 visited배열의 구현이었다. 한 가지 방식으로만 간다면 한번 방문한 장소는 다시 가지 않아도 되겠지만 이 경우에는 달랐다.말처럼 가는 방식, 원숭이 자체로 가는 방식 두 가지 경우가 있었기 때문에 각 경우에 따라 방문이 달라질 수 있었다. 결국 말처럼 가는 방식인 K의 값이 0일 때, 1일 때, 2일 때... 마다 방문 수가 다르게 적용되어야 한다. 따라서 3차원 배열로 방문 노드를 주어 해결했다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { .. 2024. 5. 22. [백준 2606번 / Java] 바이러스 - 노드를 양방향으로 연결시켜야 한다.- bfs로 구현 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { static int N; static int M; static int[] visited; static Map> map; static int count = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sys.. 2024. 5. 22. [백준 23904번 / Java] A와 B # 시간 복잡도를 계산하여 미리 예측해보자# 더 쉬운 방법을 생각해보자# StringBuilder를 활용하자 처음에 모든 경우를 계산해보는 완전탐색 알고리즘을 이용해서 계산하려고 했다. 코드로 구현하기가 머리아파서 혼자 괴로워하고 있었다... 🤯 그러나 뒤에서부터 계산하면 아주 간단해진다는걸 알게됐다.경우의 수가 2개 뿐이니 역추적을 해보는 것이다ㅠㅠ 이렇게 간단할수가,, import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { static String S; static StringBuilder T; public static void main(Str.. 2024. 5. 14. 이전 1 2 3 다음