BFS (9) 썸네일형 리스트형 [코딩테스트] SWEA 7793 오! 나의 여신님(Java) 제가 공부한 내용을 정리하는 블로그입니다.아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁SWEA 7793 오! 나의 여신님입니다.포인트해당 문제에서는 악마의 손아귀가 먼저 진행되어야 합니다.만약 악마의 손아귀를 통해서 전파된 곳에 수연이가 이미 있는 곳이라도 사실 크게 의미가 없습니다.왜냐하면 이미 수연이가 있는 위치는 수연이가 도달한 공간이기 때문에 다음 시간에는 수연이가 이동하기에 부식된 공간과는 수연이의 위치와 무관합니다. 수연이가 고려할 것은 다음 위치에 악마의 손아귀가 있는지 없는지 입니다.따라서 BFS 탐색을 통해서 문제를 진행합니다.소스코드import java.io.BufferedReader;import java.io.IOExce.. [코딩테스트] SWEA 1249 보급로(Java) 제가 공부한 내용을 정리하는 블로그입니다.아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁SWEA 1249 보급로입니다.포인트문제가 여러 조건이 많은 것 같지만 배열의 숫자는 이동비용이라고 가정하면 결국 출발지로부터 도착지까지의 최소 비용을 구하는 문제입니다.따라서 BFS로 문제를 풀면 가능합니다. BFS는 한 위치에 도달하기에 최소 경로가 보장되기 때문에 step이라는 배열을 통해 비용을 저장합니다.소스코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.Lin.. [코딩테스트] SWEA 1226 미로1(Java) 제가 공부한 내용을 정리하는 블로그입니다.아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁SWEA 1226 미로1입니다.포인트먼저 시작점과 목표 지점을 설정합니다.시작점으로부터 상하좌우 방향으로 이동 가능한지를 순회하면서 탐색을 진행합니다.이동 중에는 벽은 갈 수 없도록 범위 체크를 합니다.또한 이미 방문한 구간은 다시 탐색하지 않도록 처리하여 중복을 방지합니다.위 조건을 기반으로, 너비 우선 탐색(BFS)를 사용해 전체 경우를 탐색합니다.소스코드package SWExpert.Implementation;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStr.. [코딩테스트] Java 여행경로 제가 공부한 내용을 정리하는 블로그입니다.아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁Programmers 알고리즘 고득점 Kit입니다.포인트모든 항공권을 사용해 가능한 여행 경로를 찾고, 사전순으로 가장 앞선 경로를 반환합니다.소스코드import java.util.*;class Solution { int n; boolean[] visited; ArrayList arr = new ArrayList(); public void dfs(int cnt, String start, String path, String[][] tickets) { if(cnt == n) { arr.add(path.. [코딩테스트] Java 아이템 줍기 제가 공부한 내용을 정리하는 블로그입니다.아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁Programmers 알고리즘 고득점 Kit입니다.포인트해당 문제는 검은색 선을 따라서만 이동할 수 있다는 것이 포인트였습니다. 예를 들어, 도형의 변이 다음과 같을 때 BFS/DFS를 할 때에 문제가 발생할 수 있습니다.(4,3) -> (4,4) -> (5,3) -> ...왜냐하면 저희가 현재까지 사용했던 dx/dy 테크닉을 사용하게 되면 (4,3)에서 (5,3)으로 바로 이동할 수 있기 때문입니다. 따라서 저는 Scale(2)을 두어 더 정교하게 이동할 수 있도록 하였습니다. 나중에 답을 구할 때에도 Scale의 값만큼 나누어줘야하는 주의사항이 있습니다.. [코딩테스트] Java 단어변환 제가 공부한 내용을 정리하는 블로그입니다.아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁Programmers 알고리즘 고득점 Kit입니다.포인트dfs를 통해 모든 케이스를 돌면서 단어 변환이 되는지 체크하는 문제였습니다.소스코드import java.util.*;class Solution { static boolean[] visited; static int answer = Integer.MAX_VALUE; // s1에서 s2로 가능한지. public boolean canChange(String s1, String s2) { int dif_cnt =0; for(int i = 0; i 코.. [코딩테스트] Java 게임 맵 최단거리 제가 공부한 내용을 정리하는 블로그입니다.아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁Programmers 알고리즘 고득점 Kit입니다.포인트BFS를 활용한 문제였습니다. BFS/DFS 문제들은 중복 방문에 대한 처리를 확인해주셔야하며 OutOfRange가 나지 않기 위해 validation 체크를 진행해주셔야 합니다.소스코드import java.util.*;class Solution { class Pair { int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } } int .. [코딩테스트] Java 네트워크 제가 공부한 내용을 정리하는 블로그입니다.아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁Programmers 알고리즘 고득점 Kit입니다.포인트연결되어 있는 노드를 DFS로 이동하면서 트리의 갯수를 찾는 문제입니다.union-find로도 문제를 풀 수 있겠지만 DFS를 통해 문제를 해결했습니다. 소스코드import java.util.ArrayList;class Solution { boolean[] visited; int answer = 0; public void dfs(int n, int start, int[][] computers) { visited[start] = true; for(int i.. 이전 1 2 다음