SK_MOUSE 개발일기

DFS를 활용한 문제이다. 하지만 DFS를 숨겨놓아서 알아내기 어려운 문제였다. 블로그출처 더보기 https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-14500-%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8#dfs%EB%A5%BC-%EC%82%AC%EC%9A%A9%ED%95%B4%EC%84%9C-%ED%95%A9%EC%9D%98-%EC%B5%9C%EB%8C%93%EA%B0%92%EC%9D%84-%EA%B5%AC%ED%95%98%EB%8A%94-%EB%AC%B8%EC%A0%9C-%E3%85%9C-%EB%AA%A8%EC%96%91%EC%9D%80-%EC%98%88%EC%99%B8%EC%B2%98%EB%A6%AC-%ED%95%A9%EB%8B..

DFS + BFS를 이용한 문제의 대표유형이다. DFS는 depth를 인수로 재귀를 돌고, BFS는 Queue를 이용하여 queue.isEmpty()를 이용하여 재귀를 돌린다. 각각의 주석을 통해 dfs와 bfs의 대표적인 풀이법을 살펴보면 도움이 될 듯하다. import java.util.*; import java.io.*; class Main { static int[][] grid; static int N, M; static int max = 0; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s ..

현재상어->음식 길찾기 : 탐색 길찾으면서 거리 측정 비교 : 객체로 dist값을 넣어놓는다. 맨위,맨왼쪽부터는 for문을 돌려서 왼쪽부터 돌려나가면 된다. =>(1,1)에서 시작해서 Fish 탐색 전체코드를 우선 보겠다. import java.io.*; import java.util.*; class Main { public static int N, time, sx, sy, size, count, map[][]; public static ArrayList fishes; public static int dx[] = {-1, 1, 0, 0}; public static int dy[] = {0, 0, -1, 1}; // 상어 또는 물고기의 위치와 거리를 담을 클래스 static class Info { int ..

위의 문제풀이에 대하여 알아보겠다. 1. 좌표값에 대하여 치킨집, 집에 대한 ArrayList를 각각 생성한다. 2. 위의 생성한 ArrayList에 Input받는 동시에 각각의 Dot(x,y)객체를 집어넣는다. 3. 백트래킹을 이용할것이다. =>Combination(DFS)을 이용하여, 각각의 집에 대하여 치킨집까지 거리를 계산해서 그중에서 최소값을 택하여 min값에 넣어준다. 해당 min값은 sum에 추가한다. ex) Calc부분과 min값 구하는 방법 설명 output currentM = Calc(person.get(i), chicken.get(output[j] - 1)); 0,1 Calc(각 사람, 치킨집(0번째&1번째 선택)) 0,2 Calc(각 사람, 치킨집(0번째&2번째 선택)) 0,3 Ca..

N과M(1)은 중복 O N과M(2)는 중복 X 둘다 DFS를 활용한 코드이다. 오히려 중복없이 출력하는 코드인 (2)가 더 짧다. 단, 매개변수를 하나 더 필요로한다. 이 값(at)은 현재 index값보다 더 큰 index에 대하여 for문을 돌리기위해 사용한다. import java.util.Scanner; class Main { public static int[] arr; public static int N, M; public static void main(String[] args) { Scanner in = new Scanner(System.in); N = in.nextInt(); M = in.nextInt(); arr = new int[M]; dfs(1, 0); } public static voi..

필자의 코드는 계속해서 오답이라고 뜨는데, 모든 반례가 다 알맞게 출력된다. import java.io.*; import java.util.*; class Main { static int[][] grid; static boolean[][] visited; static int[][] vector = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; static int count; public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); grid = new int[n+1][n+1]; visited = new boolean[n+1][n+1];..

간단히 BFS나 DFS를 통해서 시작노드1로부터 연결되어있는 지점을 방문처리하면 되는 문제다. 백준 테스트가 아직 적응이 안돼서, System.out.println으로 채점되는 것을 유의하지 못해서 시간을 질질 끌었다. 필자는 dfs로 방문하고 checked 가 true인 것의 개수를 세는 방식으로 체크하였다. 단, 1에서 전염시키는 컴퓨터의 수이므로 -1을 마지막에 해주어야한다. import java.io.*; import java.util.*; public class Main { //함수에서 사용할 변수들 static int[][] check; //간선 연결상태 static boolean[] checked; //확인 여부 static int n; //정점개수 static int m; //간선개수 st..

ArrayList에 하나씩 값을 넣어야한다는 편견을 깨주었다. 한가지의 순서를 각각의 list[i]에 value + " " + value2 를 하여 일련의 String을 이어붙이고 이를 sort하여 가장 낮은차순의 배열을 추출할때 사용한다. import java.util.ArrayList; import java.util.Collections; public class TravelRoute { boolean[] visited; //방문한지 안한지를 체크하는 visited배열 ArrayList answers; public String[] solution(String[][] tickets) { visited = new boolean[tickets.length]; answers = new ArrayList(); ..

단어는 charAt메소드를 이용해서 String에서 글자를 각각 비교할 수 있다. public class WordConversion { int answer; //최소 단계 boolean[] used; //단어를 사용 중인지를 판단하는 visited와 같은 역할을 하는 배열 public int solution(String begin, String target, String[] words) { answer = 51; //단어 최대값이 50이므로 used = new boolean[words.length]; dfs(begin, target, 0, words); return answer == 51 ? 0 : answer; //answer이 51이면 target과 같은 단어가 없는 것으로 판단. } public v..

DFS/BFS 문제를 처음 접해서 다른 이들의 코드를 참고했다. 다음은 DFS 코드이다..예술이다.. class Solution { public int solution(int[] numbers, int target) { int answer = 0; answer = dfs(numbers, 0, 0, target); return answer; } int dfs(int[] numbers, int n, int sum, int target) { if(n == numbers.length) {//노드를 모두 탐색했을때만 타겟과 합이 같은지 검사한다 if(sum == target) { return 1; } return 0; } return dfs(numbers, n + 1, sum + numbers[n], target..