프론트엔드 개발자의 기록 공간

🚩 7576번_토마토 골드5 📖 문제 설명 : N x M 상자 크기에 토마토가 있을 경우, 하루가 지날 때마다 인접 토마토들을 익게 한다. 모든 토마토가 익는 데까지 걸리는 최소 일수 구하기 💡 시간 초과를 벗어나기 위해서는 queue 알고리즘을 구현해서 사용 or index가 증가하는 cursor를 두고, queue.length < queueCursor를 사용 queue 알고리즘을 구현 예시 const fs = require('fs') const [mn, ...input] = fs .readFileSync('/dev/stdin') .toString() .trim() .split('\n') const [m, n] = mn.split(' ').map(Number) const graph = input.map..

백준 BFS 알고리즘 2644번_촌수계산 난이도 : 실버II 문제설명 입출력 문제 풀이 : 주어진 사람의 번호가 서로 몇 촌인지 계산하면 된다. 촌수는 부모가 같으면 형제, 즉 같은 촌수이다. 이를 좀더 생각하면 형제는 촌수를 계산할 필요없고 부모일때만 계산해주면 된다. 즉 최단경로 문제처럼 거리가 같으면 계산을 안하고 거리가 다를때 계산을 해주는 BFS 유형인것을 알 수 있다. BFS를 이용하여 촌수를 계산하면된다. 연결된 노드만 파악하면 되기 때문에 인접그래프 형식으로 풀었다. //실버2 촌수계산 const solution = (p, q) => { //시작 촌수 p삽입 let start = [p]; let cnt = 0; while (start.length !== 0) { cnt += 1; //촌수 ..

백준 BFS 알고리즘 7562번_나이트의 이동 난이도 : 실버II 문제 설명 문제 풀이 : 출발위치에서 출발하여 이동할 수 있는 범위를 움직이면서 도착위치까지 최소 횟수를 구하면 된다. 여기서 중요한 포인트는 한 지점에서 갈 수 있는 경로를 전부 탐색한 후, 경로 횟수를 카운트를 어떻게 해줘야하는 것이 관건이다. 여러 방법이 있지만 저는 한 지점에서 갈 수 있는 위치를 스택에 넣고 그 스택의 길이만큼 반복문을 해준 후 반복이 끝났을때 카운트 해줬다. 이렇게 하면 한 단계마다 모든 위치를 탐색 할 수 있게 된다. 그리고 위치를 옮겨가면서 옮겨진 위치가 도착(종료)위치인지 비교하여 맞으면 이동횟수 출력후 종료하고 아니면 방문하지 않은 곳이면 방문처리후 스택에 이동위치를 넣어준다. const BFS = (s_..

백준 DFS 알고리즘 11725번_트리의 부모 찾기 난이도 : 실버II 해결못한 문제 : 시간초과 문제 설명 입출력 문제 풀이 : 이 문제는 인접 그래프 형식의 문제이다. 배열의 인덱스 자체가 노드번호를 의미하고 배열의 값이 그 노드와 인접한 다른 노드들의 인덱스번호가 들어있는 셈이다. 예를들어 [1, 6], [6, 3] 의 연결 정보가 주어졌을때 양방향 이므로 graph배열 1번의 인덱스에 6번의 값이 있고 반대로 인덱스6번에는 1과 3의 값이 있고 인덱스3에는 6번의 값이 있는 셈이다. 이해가 안된다면 인접그래프를 검색해서 원리를 찾아보면 이해가 갈 것이다. 다시 문제로 돌아가서 인접그래프로 값을 지정해준 후, 방문처리를 위한 배열, 부모노드를 담는 배열을 선언해준 후, graph의 1번 인덱스부터 ..

백준 DFS 알고리즘 2469번_안전 영역 난이도 : 실버I 문제 설명 입출력 문제 풀이 : 문제 설명을 보면 비의 높이가 주어질때 비의 높이보다 낮은 칸들은 빗금으로 그려져있고. 그 후 영역의 요소를 카운트하면 비의 높이에 따른 안전 영역의 요소가 구해진다. 하지만 비의 높이보다 낮은 칸들을 방문처리하고 그 후 다른 영역의 요소를 구하면 두번의 그래프 탐색을 해야해서 로직이 복잡해진다. 반대로 생각하여 비의 높이가 주어질때 비의 높이를 초과(문제 예시에서 4이하니깐 반대는 4초과)하는 영역을 방문처리하고 DFS의 실행횟수를 카운트하면 똑같이 안전영역의 요소를 구할 수 있다. 비의 높이는 1이상 100이하의 정수이므로 0~101의 반복문을 돌면서 DFS를 실행하면된다. 단 한번의 DFS를 실행하고 나면 ..

백준 DFS 알고리즘 2583번_영역 구하기 난이도 : 실버I 문제 설명 입출력 입출력 추가 예제 입력2 : 00 100 1 0 0 1 1 예제 출력2 : 1 9999 문제 풀이 : 이 문제는 조금 까다로워서 고려해야할 사항이 많다. 1. 문제 예시에서는 그래프의 0.0을 제일 왼쪽밑에서 부터시작한다. 수학시간에서 배운 x축 y축 좌표로 표현한다. 2. 눈금 크기가 100이하라서 재귀 DFS를 사용하면 정해진 재귀횟수를 넘어가서 런타임 에러가 발생한다. 3. 직사각형이 그려진 이외의 곳을 탐색해야한다. 크게 이 두가지 조건을 해결해야한다. 방법은 다음과 같다. 1. 기존의 0.0처럼(제일 왼쪽 위) 사용하기 위해선 입력으로 받은 x,y값을 바꿔주면된다. 이렇게 되면 상하 반전이 된다. 상하 반전이되면 원..