문제 출처 https://www.acmicpc.net/problem/14500 정답 풀이 테트로미노 다섯가지 모양을 보면, dfs 탐색으로 커버 가능하다는 것을 알 수 있다. 단, ㅗ 모양 빼고 !  - 따라서 dfs 를 통해 cnt가 4가 될 때까지 탐색하고, - 최대 합을 구한다. - 따로, 'ㅗ','ㅏ',ㅜ'','ㅓ' 모양일 때 전체 합을 구한다. 정답 코드 let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n, m] = input.shift().split(' ').map(v => +v); const graph = input.map(el => el.split(' ').map(v => +v..

문제 출처 https://www.acmicpc.net/problem/16724 정답 풀이 아래 그림과 같이 화살표를 무작위로 그려봤을 때, dfs로 탐색을 해서 해당 연결이 끝나는 곳에 safe zone을 두면 되겠다는 아이디어가 떠오른다. 그런데, visited 방문 처리로만 safe zone 을 다루면 안된다.  왜냐하면 파란색 애들은 이미 방문 처리로 끝나고, 주황색 애들이 남아버린다. 원래 같은 한 묶음이 될 수 있는데 ! 어떻게 위와 같은 경우에도 한 묶음으로 만들 수 있을까?  - dfs 반복문을 통해 사이클을 다 돈다.=> visited[x][y] = 2 로 처리해둔다. - 또 아직 방문하지 않은 곳 dfs 반복문으로 돈다. => 현재 돌고 있는 곳은 1로 처리, => 1로 처리하다가 만약 ..

문제 출처 https://www.acmicpc.net/problem/10159 정답 풀이 cnt1 = 해당 물건 보다 큰 물건의 개수를 센다. cnt2 = 해당 물건 보다 작은 물건의 개수를 센다. 답 = 전체 물건 개수 - cnt1 - cnt2 - 1(자기 자신) 개수를 세는 것은 dfs 탐색을 활용한다. 정답 코드  //무게 다른 물건 //1부터 N 번호 //각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건 개수 출력 //각 관계들을 2차 배열로 생성 및 정리 //dfs로 탐색 //각 숫자로 접근해서 cnt 하기 let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')const n = Number(i..

문제 출처 https://www.acmicpc.net/problem/2458 정답 풀이순위를 확신할 수 있는 학생은자기보다 작은 학생 수 + 자기보다 큰 학생 수에서  -1 한 값이 n과 같은 학생이다.  +총 학생 수가 6명일 때 나보다 작은 학생이 3명이고, 나보다 큰 학생이 2명이면 나는 4번째 순서라는 것을 알 수 있음  dfs 탐색을 통해서 나보다 몇명이 큰지 계산하고, 나보다 작은 학생이 몇명인지 계산한다.  그 후, 그 합에서 -1 한 값이 n과 같으면 answer+= 1 을 한다. ! 정답 코드  let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n,m] = input[0].sp..

문제 출처 https://www.acmicpc.net/problem/16987 정답 풀이 완전 탐색을 이용한다. 정답 코드 //계란으로 계란 치기 //-각 계란 내구도, 무게 //-상대 계란의 무게만큼 계란의 내구도가 깍임 //-계란 0이하 깨짐 //일렬 계란, 차례로 들어, 한번씩 다른 계란 쳐 => 최대한 많은 계란 깨기 let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')const n = Number(input.shift()); let egg = input.map(el => el.split(' ').map(v => +v)); function solution(n,egg){ let max = 0 f..

문제 출처 https://www.acmicpc.net/problem/1941 정답 풀이 dfs로 상하좌우 이동하면서 조건에 맞는 (Y가 3이하) 학생으로 채우는 7명을 탐색한다면, 틀린다. 왜냐하면 아래와 같이 T자 모양은 DFS로 만들지 못한다.   따라서 , 2 부분으로 나눠서 구현해야 한다. 1. DFS를 통한 7명의 학생 선택 2. 선택된 7명의 학생이 인접한지 확인하는 BFS 정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');const graph = input.map(el => el.split(''));function solution(graph) { let answer = 0; ..

문제 출처 https://www.acmicpc.net/problem/2239 정답 풀이 다른 분의 풀이를 참고했는데, 오 어떻게 이런 생각을? ..? 기가 막히다  1. 먼저 주어진 스도쿠, 즉, board에서 0인 좌표를 zero 배열에 넣자. 2. 해당 zero 를 dfs 로 탐색을 한다. 3. 모든 zero 좌표를 다 돌았을 때의 board를 출력한다. 4. dfs 함수는 zero idx를 하나씩 올린다. 5. - 조건은 check 함수에 해당 좌표와 숫자를 넣었을 때 true 값이 출력되야 한다. 6. check 함수는 해당 좌표의 행과 열을 확인해서 같은 숫자가 있으면 false, 해당 작은 3*3 좌표에서 같은 숫자가 있으면 false 정답 코드 const board = require('fs'..

문제 출처 https://www.acmicpc.net/problem/15649 정답 풀이  흠, 사실 백트래킹을 연습하고 싶어서 풀었는데 흔히 알고 있는 재귀를 활용한 순열 구하기 문제였다.  정답 코드const [n,m] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(v => +v); function solution(n,m){ let checked = new Array(n+1).fill(false); function backTracking(L, total){ if(L === m){ console.log(total.slice(1)) return; ..

문제 출처 https://www.acmicpc.net/problem/1167 정답 힌트 1. 임의의 노드에서 가장 먼 노드를 찾는다. 2. 해당 노드에서 또 먼 노드를 찾고 그때의 거리가 트리의 지름이 된다. 정답 코드 const sol = (input) => { const N = +input[0]; input = input.slice(1) const tree = Array.from({length: N+1}, () => new Array()); input.map((str) => { const [node, ...nextInfo] = str.split(" ").map(Number); for(let i=0; i 0); let max ={node..

문제 출처 https://www.acmicpc.net/problem/2638 정답 풀이 정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');const [n, m] = input.shift().split(' ').map(v => +v);const arr = [];for (let i = 0; i +v));}function solution(n, m, graph) { let answer = 0; bfs(n, m, graph); // 초기 외부 공기(-1)로 표시 while (true) { let hasCheese = false; // 치즈가 남아있는지 확인 l..