Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처화살표 미로 (Easy) 골드 3 📖 문제 BFS 탐색 문제나는 끝지점에서 상하좌우의 방을 탐색후 현재 방을 가리키는지 체크하고현재 방을 가리키지 않았다면 주문서를 써서 방향을 바꾸고 바꾼 방향으로 현재 방을 가리킬 수 있는지 확인후 이동하는 식으로 구현하였다. 🔅 문제 풀이import java.io.*;import java.sql.SQLOutput;import java.util.*;public class Main { static int R, C, K; static char[][] map; static boolean[][][] visited; static int[] dr = {-1, 0, 1, 0}; static int[] dc = {0, 1..

🧫 문제 분석 ✔️ 출처열쇠 골드 1 📖 문제 BFS 탐색 + 구현 상근이가 빈 공간을 다니면서 문서를 훔친다.열쇠는 줍고 열쇠가 있는 문이라면 연다. 처음풀이시도에서는열쇠를 얻자마자 해당하는 문에 이동하고그 문의 상하좌우를 탐색해서 한번이라도 방문한 빈 공간이 있다면 이 문은 이동 가능한 문으로 판단하여 탐색했는데 이 풀이의 문제점은 문의 상하좌우의 빈 공간이 방문이 가능함에도 열쇠를 얻은 시점이 더 빨라서 해당 열쇠가 있음에도 이동 할 수 없는 문이라 판단하여 열지 않는다. 따라서 우선 빈 공간을 먼저 다 탐색하면서갖고 있는 열쇠가 있다면 문을 열고 열 수 없는 문은 따로 저장해두고새로운 열쇠는 추가한다. 기존에 갖고 있는 열쇠로 다 탐색을 끝냈다면추가된 키로 열 수 있는 문이 있는지 확..

🧫 문제 분석 ✔️ 출처행성 터널 플래티넘 5 📖 문제 최소 비용 MST 문제크루스칼로 풀면된다. 문제에서 x길이, y길이, z길이중 가장 작은 값을 비용으로 사용하고터널 N-1개를 생성한다. 이때 연결에 필요한 최소 비용 구하기 어떤 수열에서 오름차순 정렬시 자신의 인접 수가 가장 자신과 가까운 값이 된다. x, y, z 각각 기준으로 정렬하고인접 노드와의 거리를 구한후 우선순위 큐에 저장한다. 우선순위 큐에서 가장 작은 비용의 터널 건설 정보를 꺼내서 union-find set 을 사용하여 터널의 건설 여부를 체크하고 union으로 터널을 건설한 두 행성을 합치고 최종 비용을 더한다. 🔅 문제 풀이import java.io.*;import java.util.*;import java.u..

🧫 문제 분석 ✔️ 출처벽 부수고 이동하기 4 골드 2 📖 문제 그래프 탐색 문제기존 벽 부수기와 달리 벽을 부쉈을때 이동가능한 칸의 개수를 부순 자리에 출력하고 벽이 아닌 곳 즉, 0인곳은 그대로 0 을 출력한다. 벽을 부쉈을때 마다 0을 탐색하는것보다 미리 0의 영역을 나눠서 탐색하여 해당 영역의 0의 개수를 구해놓고 각 벽의 위치에서 상하좌우 인접한 칸이 0인지 확인후 해당 칸의 영역에 구해놓은 0의 개수를 더하는 식으로 하면된다. 중요한 점은 영역 중복 연산 처리이다. boolean 이중 배열로 했다가 메모리초과를 계속당했다. Set을 사용하여 해결하였다.✔️ Set.claer()에 대해서set이 가능한 이유는 상하좌우 4가지에 대해서만 영역을 체크하기 때문이다.clear()메서드는 모든 s..

🧫 문제 분석 ✔️ 출처음악프로그램 골드 3 📖 문제 위상정렬 문제로 간단하게 위상정렬 풀이를 하면된다.진입차수가 0인 것만 BFS 탐색을 해주고 중복 탐색을 하지 않게 처리만 잘 해주면 간단한 문제다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static StringBuilder sb = new StringBuilder(); static int[] indegree; static List[] graph; static boolean[] visited; static int orderCount = 0; public static void main(String[] args) throws IOExcepti..

🧫 문제 분석 ✔️ 출처치즈 골드 3 📖 문제 외부 공기를 기준으로 BFS 탐색하여 치즈와 맞닿으면 카운팅해준다.  그런데 다른 풀이를 보고 했는데 치즈가 가장자리 (0,0)에서 시작할 수도 있지 않나 싶은데0,0 부터 외부 공기 찾는 로직이 있어도 다 통과해서 치즈가 가장자리에는 위치하지 않나보다. 나는 치즈의 처음 만나는 지점과 마지막 지점을 구하고, 안쪽 방향을 제외한 3방향을 탐색해서 공기외부 좌표를 구한다음BFS 탐색을 하여 공기 접촉 탐색을 했다. 공기를 2번 이상 접촉하면그 지점을 공기로 만들면 된다.   7 71 1 1 0 0 0 01 0 1 1 0 0 01 0 1 0 1 0 00 1 0 1 0 1 00 0 1 0 1 0 00 0 0 1 0 0 00 0 0 0 0 0 0//answer ..

🧫 문제 분석 ✔️ 출처파티 골드 3 📖 문제 O(N^3) 인 플로이드 워샬은 사용불가능하고,다익스트라로 풀어야하는 문제다. 그런데 X→모든 정점은 구하겠는데 모든 정점→X를 편하게 구하는 법을 몰라서 각 정점에서 다익스트라 알고리즘을 돌려서 X까지의 값을 구하는 식으로 했다.  이 후 다른 사람의 풀이를 봤는데 정말 놀랍다.  단방향이지만 역방향으로 그래프를 만들어서// 기존 X -> AllAll -> X// 다른사람들의 풀이X -> All X 로 X에서 모든정점으로 가는 그래프를 만들고X로 오는 모든 정점으로 가는 역방향 그래프를 만드는 것이다. 좋은 것을 배웠다..  🔅 문제 풀이 [x→ all → x]import java.io.*;import java.util.*;public class Ma..

🧫 문제 분석 ✔️ 출처특정한 최단 경로 골드 4 📖 문제  최단경로 + 정해진 정점을 지나기 많이 고민해보고 처음 설계는 1 -> v1 -> v2 -> N 으로 가면 되지 않나? 싶어서 저 한 가지 경우만 만들어서 했으나 당연히 실패했다. 반례를 보니 v2 -> v1- >N 경로가 더 짧은 경우가 있다. 따라서1 -> v1 -> v2 -> N1 -> v2 -> v1 -> N 두가지에 대해서 풀었다. 근데 바보같이 입력받을때 정점 e만큼 받아야하는데 n만큼 받도록 해서 계속 틀렸다이런 사소한 실수.. 제발 그만좀 하고싶다.   🔅 문제 풀이 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader..

🧫 문제 분석 ✔️ 출처케빈 베이컨 6단계 법칙 실버 1 📖 문제 어디서 많이 봤던 문제촌수 따지는 문제랑도 비슷한 것 같다. 다른점은 모든 사람들의 케빈 베이컨 지수 중 가장 작은 지수를 가진 사람을 찾는 것즉, 모든 사람에 대한 모든 사람의 최단거리, 플로이드 와샬 알고리즘을 쓸 수 있다. BFS로 그냥 풀어도 된다.  🔅 문제 풀이 (플로이드 와샬)import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in..

🧫 문제 분석 ✔️ 출처불! 골드 3 📖 문제  BFS로 풀 수 있는 문제로문제에서 탈출구는 끝부분 즉, 행이 0이거나 열이 0 인 곳에 가기만 하면 탈출한다. ....J. //여기서는 8곳이 탈출구이다.....##.J# //여기서는 0,0, 1,0 이 탈출구이다.### 또한 매 분마다 불이 퍼지고, 지훈이도 이동하는데불을 먼저 이동시키고 지훈이를 이동시키면 된다.  불이 퍼졌을 때 불에 대한 방문 체크와 벽 체크지훈이는 방문체크, 불과 벽 체크를 하면서 이동하면 된다.  분마다 퍼진 불들을 큐에 넣고 그 시간에 퍼진 불들만 퍼뜨려야한다. 아니면 시간과 상관없이 전부 퍼진다.  ....F. // 0분 초기상태....F. // 1분 전 1,1에 있는 불 하나가 퍼졌으므로 이 1개에 대한 불을 퍼..