아래 글은 오늘 강의를 들은 자료구조/알고리즘 수업의 내용과 내가 푼 방식, 강사님이 푼 방식이다. 문제의 저작권 때문에 간략하게 정리해서 올리는 점 참고해 주시기 바란다.
[그래프, DFS, BFS 응용]
수들의 조합
N개의 정수가 주어지면 그 숫자들 중 M개를 뽑는 조합의 합이 임의의 정수 K의 배수인 개수는 몇 개가 있는지 출력하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(nums, m, k) {
let answer = 0;
function DFS(L, s, sum) {
if(L === m) {
if(sum % k === 0) {
answer++;
}
} else {
for(let i = s; i<=nums.length; i++) {
DFS(L+1, i+1, sum + nums[i]);
}
}
}
DFS(0, 0, 0);
return answer;
}
console.log(solution([3, 5, 7, 8, 9, 12, 14], 4, 8));매개변수를 활용하여 sum의 값을 이용하여 레벨이 끝까지 도착하였을 때 그 값이 k의 배수인지 확인하고 맞으면 answer에 더해주면됨.
이진트리 레벨탐색(넓이우선탐색 : BFS)
큐를 이용하여 이진트리를 레벨탐색 하여라
📌 내가 푼 방법
📌 강사님 방법
function solution() {
let answer = "";
function BFS() {
let queue = [];
queue.push(1);
while(queue.length) {
let v = queue.shift();
answer+=v+" ";
for(let nv of [v*2, v*2+1]) {
if(nv > 7) continue;
queue.push(nv);
}
}
}
BFS();
return answer;
}
console.log(solution());탐색 결과 1, 2, 3, 4, 5, 6, 7의 순이며 레벨순으로 탐색을 하게됨! --> 이러한 트리가 어떠한 상태를 나타내는 트리라고 하였을 시, 최단 거리를 나타냄(1번만에 가는 레벨, 2번만에 가는레벨 ...)
시험에 DFS보다 많이 등장하지는 않는다.
송아지 찾기(BFS : 상태트리탐색)
송아지는 움직이지 않고 그대로 있고 현수의 위치가 주어진다. 최소 몇번 점프로 송아지의 위치로 갈 수 있는 지 구하여라.
📌 내가 푼 방법
📌 강사님 방법
function solution(s, e) {
let answer = 0;
function BFS() {
let ch = Array.from({length:10000}, () => 0);
let queue = [];
queue.push(s);
ch[s] = 1;
let L = 0;
while(queue.length) { // queue가 0 레벨일 땐 1바퀴 돎
let len = queue.length; // 밑의 for문을 돌고나면 다음 레벨의 개수를 가리킴
for(let i = 0; i<len; i++) {
let x = queue.shift();
for(let nx of [x-1, x+1, x+5]) {
if(nx === e) return L+1; // 여기서 확인하는 이유는 더 빨리 찾으려고 따라서 L+1로 확인해줌
if(nx > 0 && nx<=10000 && ch[nx] === 0) {
ch[nx] = 1;
queue.push(nx);
}
}
}
L++;
}
}
answer = BFS();
return answer;
}
console.log(solution(8, 3));현수의 위치가 5라고 가정했을 때, 한번만에 가는 위치를 적어두고, 그게 송아지의 위치가 아니라면 계속해서 반복!(2번.. 3번..)
미리찾으려면 For문안의 자식들을 push할때 L+1로 더해주면 된다.
ch배열을 통해 미리 갔던 곳은 체킹을 해둔다.
미로의 최단거리 통로(BFS)
7x7 격자판 미로를 탈출하는 최단경로의 길이를 출력하는 프로그램을 작성하라
📌 내가 푼 방법
📌 강사님 방법
function solution(board) {
let answer = 0;
let n = board.length;
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
let dist = Array.from(Array(7), ()=>Array(7).fill(0));
function BFS(x, y) {
let queue = [];
queue.push([x, y]);
board[x][y] = 1;
while(queue.length) {
let curr = queue.shift();
for(let j = 0; j<4; j++){
let nx = curr[0] + dx[j];
let ny = curr[1] + dy[j];
if(nx >= 0 && nx<7 && ny >=0 && ny < 7 && board[nx][ny] === 0) {
board[nx][ny] = 1;
dist[nx][ny] = dist[curr[0]][curr[1]] + 1;
queue.push([nx, ny]);
}
}
}
}
BFS(0, 0)
// console.log(dist);
if(dist[6][6] === 0) return -1;
else answer = dist[6][6];
return answer;
}
console.log(solution([
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 1, 0],
[0, 0, 0, 1, 0, 0, 0],
[1, 1, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 0, 0, 0, 0]
]));최단거리는 무조건 BFS!! DFS는 한번 길을 쭉 가기때문에 BFS로 하는게 나음
방향을 정해두고 거리 배열을 하나 더 만들어 그곳에 가는 길의 거리를 적어서 최종적으로 그 부분의 거리를 반환시켜준다.
그래프와 인접행렬
무방향 그래프, 방향그래프, 가중치 방향그래프에 대한 설명
📌 내가 푼 방법
📌 강사님 방법
무방향 그래프 --> 탐색 시 1번 정점이 탐색지점이면 1번 정점에서 한번만에 갈 수 있는 것들을 찾음(2차원배열의 1행을 탐색해보면 갈 수 있는 정점들이 나옴)
방향그래프 --> 딱 그 방향으로만 갈 수 있는거
가중치 --> 방향으로 가는데 드는 비용
경로 탐색(인접 행렬)
방향그래프가 주어지면 1번 정점에서 N번 정점으로 갈 수 있는 모든 경로의 가지 수를 출력하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(n, edges) {
let answer = 0;
let graph = Array.from(Array(n+1), () => Array(n+1).fill(0));
let ch = Array.from({length: n+1}, () => 0);
for(let [a, b] of edges) {
graph[a][b] = 1;
}
let path = []
path.push(1);
function DFS(v) {
if (v === n) {
console.log(path);
answer++;
} else {
for(let i = 1; i<=n; i++){
if(graph[v][i]===1 && ch[i] === 0) {
ch[i]=1;
path.push(i);
DFS(i);
ch[i]=0;
path.pop();
}
}
}
}
ch[1] = 1;
DFS(1);
return answer;
}
console.log(solution(5, [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]]));갈 수 있는 정점을 구하는 것은 DFS!
경로는 한번 방문한 곳을 방문하면 안됨!
graph라는 배열에 갈 수 있는 정보를 담은 배열을 만들어 두고 DFS로 탐색을 하여 그 지점까지 레벨이 왔을 때, answer 더해줌, 또한 for문을 돌면서 갈 수 있는 방향과 이미 가지 않은 방향인지 체크를 하고 DFS를 돈다.
경로 탐색(인접리스트)
방향그래프가 주어지면 1번 정점에서 N번 정점으로 갈 수 있는 모든 경로의 가지 수를 출력하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(n, edges) {
let answer = 0;
let graph = Array.from(Array(n+1), () => Array());
let ch = Array.from({length: n+1}, () => 0);
for(let [a, b] of edges) {
graph[a].push(b);
}
let path = []
path.push(1);
function DFS(v) {
if (v === n) {
answer++;
console.log(path);
} else {
for(let nv of graph[v]) {
if(ch[nv] === 0) {
ch[nv] = 1;
path.push(nv);
DFS(nv);
ch[nv] = 0;
path.pop();
}
}
}
}
ch[1] = 1;
DFS(1);
return answer;
}
console.log(solution(5, [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]]));방향일 때 graph[a].push(b)
무방향일 때 graph[a].push(b); && graph[b].push(a);
가중 방향그래프일 시 graph[a].push([b,c]);
동아리 개수
매개변수 N에 학교의 학생수와 매개변수 edges에 두 학생의 정보를 나타내는 순서쌍이 주어지면 이를 통해 학교의 동아리 개수를 구하여라.
📌 내가 푼 방법
📌 강사님 방법
function solution(n, edges) {
let answer = 0;
let graph = Array.from(Array(n+1), () => Array());
let ch = Array.from({length: n+1}, () => 0);
for(let [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
console.log(graph);
function DFS(v) {
for(let nv of graph[v]) {
if(ch[nv] === 0) {
ch[nv] = 1;
DFS(nv);
}
}
}
for(let i = 1; i<=n; i++) {
if(ch[i] === 0) {
answer++;
ch[i]=1;
DFS(i);
}
}
return answer;
}
console.log(solution(7, [[1, 2], [2, 3], [1, 4], [1, 5]]));for문을 돌면서 DFS로 돌면서 하나로 쭉 연결되어 있는 그래프를 확인하여 그 그래프의 수를 센다.
사람간의 연결관계는 무방향으로 !
섬나라 아일랜드(DFS)
섬나라 아일랜드의 지도가 격자판으로 주어지면 몇개의 섬이 있는 지 구하여라
📌 내가 푼 방법
📌 강사님 방법
function solution(board) {
let answer = 0;
let n = board.length;
let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
let dy = [0, 1, 1, 1, 0 , -1, -1, -1];
function DFS(x, y) {
for(let k = 0; k<8; k++) {
let nx = x+dx[k];
let ny = y+dy[k];
if(nx>=0 && nx < n && ny>=0 && ny<n && board[nx][ny] === 1){
board[nx][ny] = 0;
DFS(nx, ny);
}
}
}
for(let i = 0; i<n; i++) {
for(let j = 0; j<n; j++) {
if(board[i][j] === 1) {
board[i][j] = 0;
answer++;
DFS(i, j);
}
}
}
return answer;
}
console.log(solution([
[1, 1, 0, 0, 0, 1, 0],
[0, 1, 1, 0, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 1, 1],
[1, 1, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 1, 0, 0],
[1, 0, 1, 0, 1, 0, 0]
]));DFS를 통해 연결되어 있는 섬나라를 세고 answer를 증가시킴
최대 선호 음식(DFS)
재료의 번호가 D까지의 정수로 나오고, K개 이하의 재료로 요리를 하려고 하며 nums배열에 학생들이 좋아하는 음식의 정보가 주어진다. 이때 최대 몇 명의 학생에게 음식을 만들어 줄 수 있는가?
📌 내가 푼 방법
📌 강사님 방법
function solution(nums, D, K) {
let answer = Number.MIN_SAFE_INTEGER;
n = nums.length;
pow = Array.from({length: D+1}, () => 0);
st = Array.from({length: n}, () => 0);
pow[1] = 1;
for(let i = 2; i<=D; i++) {
pow[i] = pow[i-1] * 2 // 인덱스 번호에 가중치
}
for(let i = 0; i<n; i++) {
for(let j = 0; j<nums[i].length; j++) { // nums[i].length는 그 학생이 선호하는 양념의 개수
st[i] += pow[nums[i][j]];
}
}
function DFS(L, s, bit) {
if(L === K) {
let cnt = 0;
for(let j=0; j<n; j++) {
if((bit & st[j]) === st[j]) cnt++;
}
answer = Math.max(answer, cnt);
} else {
for(let i = s; i<=D; i++) { // i는 양념 번호
DFS(L+1, i+1, bit+pow[i]);
}
}
}
DFS(0, 1, 0);
return answer;
}
console.log(solution([[1], [2, 3], [3], [1, 2], [], [2, 1], [2, 3, 4], [3, 4]], 4, 3));D콤비네이션K(DCK)가 만들 수 있는 음식의 종류!
1번 양념재료에 2의 0승만큼 가중치, 2번 양념재료에 2의 1승만큼 가중치, 3번 양념재료에 2의 2승만큼 가중치, 4번 양념재료에 2의 3승만큼 가중치
자신이 만든 음식또한 2진수로 만들어 10진수로 바꾸어둠
음식과 학생의 숫자를 비트연산하였을 때 학생의 숫자가 나오면 그 학생은 그 음식을 먹을 수 있음!
토마토(BFS)
큰 창고에 토마토를 보관하는데 보관후 하루가 지나면 익은 토마토 주위의 토마토들이 익게 된다. 며칠이 지나야 다 익게 되는 지, 최소 일 수를 구하여라.
📌 내가 푼 방법
📌 강사님 방법
function solution(board) {
let answer = 0;
let n = board.length;
let m = board[0].length;
let dx = [-1, 0, 1, 0];
let dy = [0, 1, 0, -1];
let dist = Array.from(Array(n), () =>Array(m).fill(0));
let queue = [];
function BFS() {
while(queue.length) {
let cur = queue.shift();
for(let j = 0; j<4; j++) {
let nx = cur[0] + dx[j];
let ny = cur[1] + dy[j];
if(nx >= 0 && nx < n && ny >=0 && ny<m && board[nx][ny] === 0){
board[nx][ny] = 1;
dist[nx][ny] = dist[cur[0]][cur[1]]+1;
queue.push([nx, ny]);
answer = dist[nx][ny]; // 제일 마지막에 들어간 값이 최종 값
}
}
}
}
for(let i = 0; i<n; i++) {
for(let j = 0; j<m; j++) {
if(board[i][j] === 1) {
queue.push([i, j]);
}
}
}
BFS();
for(let i = 0; i<n; i++) {
for(let j = 0; j<m; j++) {
if(board[i][j] === 0) {
return -1;
}
}
}
return answer;
}
console.log(solution([
[0, 0, -1, 0, 0, 0],
[0, 0, 1, 0, -1, 0],
[0, 0, -1, 0, 0, 0],
[0, 0, 0, 0, -1, 1]
]));익은 토마토들의 좌표는 0레벨에 있어야함 (동시에 퍼져나가므로)
answer값에 계속 담아서 최종적으로 적히는 값이 토마토가 다 익는데 걸리는 최소 날짜
마지막에 이중포문을 돌면서 0이 있으면 -1을 반환!
