Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처엘리베이터 플래티넘 5 📖 문제 최단경로 + BFS + 역추적 문제 이문제를 풀면서 메모리초과가 진짜 자꾸 나서 정말 힘들었다. 여러번의 테스트 끝에 알아낸 것은컬렉션에서for (int i : list)향상된 for문(for-each)는 내부적으로 Iterator 객체를 생성해서 순회한다.때문에 수많은 엘리베이터를 갖는 리스트를 foreach로 접근했으니메모리초과될 수밖에 없었다. 많은 양의 요소를 담는 컬렉션 객체는 되도록이면 for-each문을 사용하지 말아야겠다. 그리고 거리는 dist배열로 따로 빼자.괜히 큐에 같이넣어서 메모리초과뜬다. 🔅 문제 풀이 [다익스트라]import java.io.*;import java.util.*;public class Main { ..

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

🧫 문제 분석 ✔️ 출처치즈 골드 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 ..

🧫 문제 분석 ✔️ 출처특정한 최단 경로 골드 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개에 대한 불을 퍼..

🧫 문제 분석 ✔️ 출처여행 가자 골드 4 📖 문제 서로소 집합 또는 BFS-DFS 알고리즘 둘중 하나로 풀 수 있는 문제다. 주어진 섬들을 여행 시작점을 출발로 탐색해서여행 계획 섬들을 전부 방문했는지만 따지면된다.  서로소 집합의 경우 여행 계획 섬들의 부모가 모두 같으면 여행 가능하다. 🔅 문제 풀이 [BFS]import java.io.*;import java.util.*;public class Main { static boolean[] visited; static boolean[][] graph; // 방문한 곳을 여행 계획에서 체크하면 된다. // 여행계획 섬을 방문하지 않았다면 이는 불가능한 것 public static void main(String[] args..

🧫 문제 분석 ✔️ 출처뱀과 사다리 게임 골드 5 📖 문제 주사위를 굴려서 1~6까지 숫자를 현재 위치에 더하면서 BFS 탐색을 하면 된다. (최단 경로) 1차원 배열을 게임 판이라 생각하고 100칸을 만든다. x번 도착하면 y번 칸 이동 , u번 도착하면 v번 칸 이동 이므로왼쪽 입력을 인덱스로 사용, 오른쪽 입력을 값으로 사용한다.  BFS 탐색을 하면서 주사위를 굴려 이동할때 이동한 위치가map에서 값이 있다면 그 값으로 이동한다.  물론 방문 체크를 해줘야한다. 이 경우 특별한 이동방법이 없으므로 1차원 배열로 체크해주면 된다.  특별한 이동 방법을 쓰는 문제 포스팅 보러가기 백준 1600번 : 말이 되고픈 원숭이 자바 백준 2206번 : 벽 부수고 이동하기 자바  🔅 문제 풀이import ..

🧫 문제 분석 ✔️ 출처중량제한 골드 3 📖 문제 최단 경로 + 최대신장(최소 신장의 반대라서 이렇게 붙였다) + 이분탐색 문제다.근데 본인은 최대 신장 트리로 안풀고, 현재 이분탐색 문제를 공부중이므로 이분탐색 + BFS 최단경로로 풀었다.  이분탐색으로 찾고자 하는 것은 두 섬 사이의 경로 이동 비용 최댓값이다. 가장 비용이 큰 값을 max로 잡고 1 ~ max 사이를 이분탐색하면서 mid값으로 BFS 탐색을 한다. BFS 탐색에서는 공장이 있는 섬A에서부터 탐색을 하되 mid 값 (중량)을 다리의 중량제한이 버틸 수 있다면 다음 다리로 탐색한다. 공장이 있는 섬 B에 도착하면 현재 mid 값의 중량은 버틴다는 의미이므로 true를 반환해 알린다.이분탐색에서는 BFS 결과가 true이면 mid 값..