Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처부대 복귀 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. 레버로 이동 ..

🧫 문제 분석✔️ 출처배달 level 2📖 문제  거리 값이 존재하는 그래프 문제이 문제를 통해 다익스트라, 플로이드 워샬 등거리 값이 존재하는 그래프의 탐색이 얼마나 부족한지 깨달았다. 해당 문제를 BFS, 플로이드 워샬, 다익스트라로 풀어보았다. 그리고 거리가 있는 그래프에 대한 간단한 정리를 할 예정이다.  🔅 문제 풀이 - BFSimport java.util.*;class Solution { // N개의 마을, K : 갈 수 있는 거리 // BFS 탐색으로 K - 각 마을까지의 비용 >= 0 인 곳을 방문 int[] visited; public int solution(int N, int[][] road, int K) { int[][] graph = n..

🧫 문제 분석✔️ 출처숫자 변환하기 level 2📖 문제 간단하지만 생각해볼게 좀 있는 문제최단경로 BFS로 풀어보자고 생각했다. 핵심x == y 일때,x로 y를 만들 수 없을때 bfs 탐색을 멈추는 조건중복 탐색 방지 (시간 초과 가능성)🔅 문제 풀이import java.util.Queue;import java.util.LinkedList;class Solution { // x -> y // x + n || x * 2 || x * 3 //bfs 최단 경로 boolean[] visited = new boolean[1000001]; public int solution(int x, int y, int n) { int answer = bfs(x,y,..

🧫 문제 분석✔️ 출처리코쳇 로봇 level 2📖 문제 BFS 문제로 다른점은 한방향으로 쭉 가야한다는 것과D라는 장애물이나 가장자리 즉, 배열의 범위를 넘어서는 곳을 만나면 멈춘다는 것이다.  장애물을 만나거나, 가장자리 (배열 범위)를 넘어선 곳을 만날때 멈춘 자리가 G(목표지점) 인지 확인하면 되는 단순한 문제이다. 🔅 문제 풀이import java.util.Queue;import java.util.LinkedList;class Solution { boolean[][][] visited; int[] dx = {0, 0, 1, -1}; int[] dy = {1, -1, 0, 0}; int answer = 0; class Token { int y; ..

🧫 문제 분석  ✔️ 출처연구소 골드 4 📖 문제 완전탐색  + BFS 문제이다. ( + 백트래킹...?) 단순하게 0인 곳에서 1을 세우되 3개까지만 세우고 BFS로 탐색해보고 퍼진 바이러스 개수의 최솟값을 구한다. 1을 세우는 것은 모든 구역에 대해서 진행하면 된다.  1로 된 벽 개수를 세고바이러스 위치를 list에 담고안전한 구역을 zeroList에 담는다.  list는 bfs에서 빠르게 사용하기 위함이고,zeroList는 완전탐색을 빠르게 하기 위함이다. 전체 크기 - (벽의 개수 + 새롭게 세운 벽 3개 + 바이러스 개수의 최솟값) 이 안전구역의 최댓값이다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static..

🧫 문제 분석 ✔️ 출처말이 되고픈 원숭이 골드 3 📖 문제 상하좌우, 체스의 나이트 이동방식을 BFS 방식으로 푸는 문제이다. 이 문제에서 핵심은 말 움직임은 k번만 가능하다이때 중요한 것은 0~k번 말 움직임의 경우를 각각 따져서 가장 빠르게 오른쪽 끝으로 도달한 경우를 찾는 것이다. 말 움직임을 0번도 안쓰고 상하좌우로만 목표점에 도달한 경우말 움직임을 1번 쓰고 상하좌우로만 목표점에 도달한 경우 ...말 움직임을 k번 쓰고 상하좌우로만 목표점에 도달한 경우  이때 각 말 움직임 횟수마다 방문 체크를 해줘야한다.  말 움직임 구현상하좌우로 먼저 탐색을 하고그 방향으로 1번 더 간 다음 상하일 경우 좌우를 탐색좌우일 경우 상하를 탐색한다.  코드와 그림을 보면 이해하기 쉽다.    이와 비슷한 ..

🧫 문제 분석 ✔️ 출처적록색약 골드 5 📖 문제 BFS 혹은 DFS 그래프 탐색 문제이다.나는 BFS를 좋아해서 BFS로 풀었다.  적록색약은 적록색(R) 과 초록색(G)의 차이를 거의 못느낀다.따라서 둘중 하나로 통일하면 된다.   나는 문제를 잘못 이해해서적록색과 초록색의 상화좌우로 인접해 있는 부분만 차이를 못느끼는 줄 알고 문제의 난이도를 더 높여서 풀다가 자꾸 틀리고 이상해서 문제를 다시봤더니 초록색과 적록색 차이가 없다고 보는게 맞았다...(이때문에 시간을 많이 소요함) 이 풀이법도 밑에 올리겠다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static boolean[][] visited; static i..

🧫 문제 분석 ✔️ 출처촌수계 실버 2 📖 문제 bfs는 가중치가 같으면 항상 최단거리이다.그래프는 연결되어있기에 어디에서 시작하든지 가중치가 같다면 거리는 같다. (양방향 한정)BFS는 재귀로 구현하지 못한다. 처음에는 진입 경로가 0인 최상위 부모를 찾아서 위에서부터 DFS 탐색으로 깊이를 측정하며 x와 y를 구했다.부모와의 관계를 문자열로 저장하고 각 각 비교하면서 촌수를 따졌는데 이렇게하면 너무 오래걸리고, 이상하게 중복이 생겼다. 푸는 방향이 잘못되었던 것이다. 이 문제에서 원하는건 그래프와 넓이 탐색에 대한 개념을 잘 이해하는지를 물어보는 문제였고 나는 제대로 이해하지 못했어서 이상하게 풀이를 시작한 것이다.  잘 기억하자.   🔅 문제 풀이import java.io.*;import ja..