Meluu_의 코딩 공부 일지

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

🧫 문제 분석✔️ 출처부대 복귀 level 3📖 문제 최단경로인데 길이가 1이라해서 그냥 BFS로 풀었다.  몰랐던 사실인데 n이 10만이고, roads에서 모든 노드를 주지 않으므로, 메모리 낭비라고 생각해서 HashMap을 사용하는것이 좋아보인다고 생각해서 사용했다.  목적지 (destination)부터 끝노드까지 (탐색이 종료될때까지 ) 돌게 하되방문한 곳이 source[i] 면 거리값을 저장한다.   물론 다익스트라 알고리즘을 쓰는게 맞는것 같다. 내 로직보다 속도는 약 5배 정도 더 빠르다. 문제에서 최단 경로 라고 주어졌는데 비용이 1이라는 말에 BFS로 밀고 가려해서 저렇게 짠 것이다.   참고 HashMap은 해시 충돌을 대비한 내부 구조 (엔트리 배열, 체이닝 등)로 인해 메모리 오버..

🧫 문제 분석✔️ 출처단어 변환 level 3📖 문제 begin 알파벳 중 하나를 words 단어중 하나의 알파벳으로 바꿀 수 있다.순서는 상관없고, 변경을 최소한으로 해서 target을 만들면 된다.   백트래킹하면서 words를 탐색한다.  words 각 단어의 알파벳을 begin의 각 알파벳과 비교해서 2개이상 다르면 바꾸지 않고 넘어가도록 한다.  만약 알파벳이 1개만 다르다면 그 단어를 begin으로 하고백트래킹 탐색을 한다. 🔅 문제 풀이class Solution { // 완전탐색 // 백트래킹 boolean[] visited; int min = Integer.MAX_VALUE; public int solution(String begin, Str..

🧫 문제 분석✔️ 출처미로 탈출 level 2📖 문제 단순 BFS이며,레버를 당기고 난 후 출구로 나갈 수 있으며레버를 당기지 않아도 출구 지역은 지나다닐 수 있고모든 지점은 여러 번 지나갈 수 있다.  나는 출발점을 찾고 거기서 부터 BFS로 L를 탐색한다음현재 위치에서 다음 위치가 레버이면서 아직 레버를 안당겼다면여태까지 방문한 기록을 없애고, 큐를 초기화 시킨 다음 레버를 당기고(레버 위치를 큐에 담고), 레버 위치에 방문했다고 표시한다. 그리고 레버 위치에서부터 시작하게끔 현재 위치에서 탐색을 중지시킨다.(break)레버 위치에서부터 다시 BFS 탐색을 해서 E인 탈출구를 찾는다. 🔅 문제 풀이import java.util.*;class Solution { // 1. 레버로 이동 ..