유미의 기록들

📌 문제 📝 풀이과정완전탐색 문제이고 나는 DFS로 풀었다 1. map[0][0] 인 C를 int형 인덱스 2로 바꿔서 방문처리를 한다.2. dfs(y, x, cnt) 탐색을 한다    2-1. cnt 중에 가장 큰 값 ret을 정의한다    2-2. 인접한 노드를 탐색하면서 방문하지 않은 알파벳이 있다면 방문처리를 하고 dfs(ny, nx, cnt+1) 탐색한다    2-3. 방문처리를 원복한다 (다른 루트로 탐색하기 위해 방문하지 않은 상태로 초기화한다)  💻 코드import java.util.Scanner;import java.io.*;import java.util.*;public class Main{ static int r,c,ret=0; static char [][]map; static i..

📌 문제   💻 코드import java.util.Scanner;import java.io.*;import java.util.*;public class Main{ static final int MAX=1501; static int r,c; static char [][]map; static boolean [][] visited; static boolean [][]visitedSwan; static int swanY,swanX,day,y,x; static Queue waterQ=new LinkedList(); static Queue waterTempQ=new LinkedList(); static Queue swanQ=new LinkedList(); static Queue swanTempQ=new Link..

📌 문제  📝 풀이과정위 문제를 푸는 데 2가지 핵심로직이 있다 1) 수빈이와 동생이 같이 이동하면서 만났을 경우 2) 수빈이가 먼저 도착했지만, 동생과 홀수, 짝수가 맞았을 경우ex) 수빈이는 2초에 20에 도착, 동생은 4초에 20에 도착해도 성립된다수빈이는 +1, -1으로 이동할 수 있기 때문에 20(2초) → 21(3초) → 20(4초) 로 동생과 만날 수 있다  ⚠️ 처음에 1)번째 상황만 생각해서 문제를 풀었기 때문에 틀렸다.....  💻 코드import java.util.Scanner;import java.io.*;import java.util.*;public class Main{ static final int MAX=500000; static int[][] visited=new int..

📌 문제 📝 풀이과정1. 가장 빠른 시간이전에 숨바꼭질 2 문제에서 BFS로 가장빠른 시간을 출력해보았다 (12851번 문제풀이 참고) 2. 어떻게 이동해야 하는 지이동 경로를 추적하는 문제이므로 prev배열으로 구현할 수 있다prev[next]=now; for(int i=k;i!=n;i=prev[i]){ trace.add(i);}trace.add(n);Collections.reverse(trace); 1) k인 17부터 prev[17], prev[16], prev[8] .... i가 5가 아닐 때까지 ArrayList trace에 i를 넣는다2) 마지막으로 n인 5를 넣어준다3)  그럼 trace에는 17, 16, 8, 4, 5 순서로 들어있고, Collections.reverse로 뒤집어 주..

📌 문제  📝 풀이과정1. 가장 빠른 시간으로 동생으로 가는 시간 → 최단거리 문제이므로  BFS 로 푼다- 3개의 방향으로 갈 수 있음 (x-1, x+1, 2*x)- visited[k] - 1 가 최단거리의 시간이다 2. 가장 빠른 시간으로 동생으로 가는 경우- 경우의 수는 cnt배열이 0인 상태에서 이전 방문 노드의 cnt를 더하면서 계산한다- 이미 방문한 노드라도 최단소요시간과 같다면 한번 더 방문할 수 있다 3. 반례수빈이와 동생의 위치가 같다면 시간은 0이고 경우는 1이다 💻 코드import java.util.Scanner;import java.io.*;import java.util.*;public class Main{ static final int MAX=200000; static Que..

📌문제  📝 풀이과정처음에는 내림차순 정렬을 해서 9,3,1 차례로 빼면서 모두 0이하일 때까지 반복하면 최솟값을 구할 수 있다고 생각했다... 하지만 예외1에서도 그 방법은 맞지 않았다  너무 단순하게 생각한 것이다😓 단순하게 9,3,1 만 빼는 것이 아니라 6가지의 경우의 수가 있다  이렇게 그래프로 나타내보면 모든 경우의 수에서 (0,0,0)에 도달하는 최소의 횟수를 구할 수 있다. 즉, 레벨별로 탐색하여 최단거리를 구하는 개념으로 생각해보면 BFS로 풀 수 있는 것을 알 수 있다.   💻코드import java.util.Scanner;import java.io.*;import java.util.*;public class Main{ static int n; static int scv[]=ne..

📌문제     📝 풀이과정최단거리 문제이므로 BFS로 푸는 것이 좋다 1. 시작 좌표값인 (0,0)을 BFS로 넘긴다2. (y,x)좌표를 탐색했으므로 visited[y][x]=1으로 방문처리를 한다2. 이동 할 수 있는 좌표값을 저장할 Queue를 선언하고 (x,y)를 저장한다 3.  Queue 가 비어있지 않을때 까지 반복한다    3-1. Queue에서 처음 입력값을 꺼내 nowY와 nowX를 저장한다    3-2. (nowY,nowX)를 기준으로 상,하,좌,우로 인접한 노드를 탐색해서 이동가능하고 방문하지 않은 노드가 있다면 Queue에 저장한다    3-3. 인접한 노드(ny,nx)를 (nowY,nowX)보다 1 큰 값을 visited배열에 저장한다 (최단거리를 나타내는 배열이다)   ⚠️입력..