온라인 코드 테스트 사이트
https://www.jdoodle.com/execute-nodejs-online/
Ch 07. DFS (깊이 우선 탐색) 알고리즘
문제 1-1) 바이러스 (실버3)
- 양방향 그래프로 생각하고 인접 리스트 표현하기
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const v = Number(input[1]);
const matrix = [];
for(let i = 0; i <= n; i++) matrix.push([]);
for(let i = 2; i < v + 2; i++) {
const [from, to] = input[i].split(' ').map(Number);
matrix[from].push(to);
matrix[to].push(from);
}
const visited = new Array(n + 1).fill(false);
let result = 0;
function dfs(node) {
visited[node] = true;
result += 1;
for(let n of matrix[node]) {
if(visited[n]) continue;
dfs(n);
}
}
dfs(1);
console.log(result - 1);
문제 1-2) 유기농 배추(실버2)
- 테스트별 필요한 변수 선언에서 실수 발생 가능
- dfs 함수에 매개변수 항목이 많아 그래프 자체로 재귀 호출하여 처리(강의 해설 참고*)
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
function dfs(matrix, row, col, x, y) {
if(x < 0 || y < 0 || x >= row || y >= col) return false;
if(matrix[x][y] === 1) {
// 해당 노드 방문 처리
matrix[x][y] = -1;
// 상하좌우 재귀적으로 호출하여 방문처리
dfs(matrix, row, col, x, y + 1);
dfs(matrix, row, col, x - 1, y);
dfs(matrix, row, col, x, y -1);
dfs(matrix, row, col, x +1, y);
return true;
}
return false;
}
let testCase = Number(input[0]);
let line = 1;
while(testCase-- > 0) {
const [m, n, k] = input[line].split(' ').map(Number);
/*
m행 n열의 인접행렬 초기화
5행 3열의 경우 [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]
*/
const matrix = [];
for(let i = 0; i < m; i++) {
const data = [];
for(let j = 0; j < n; j++) data.push(0);
matrix.push(data);
}
// 배추 심기
for(let l = 1; l <= k; l++) {
const [x, y] = input[line + l].split(' ').map(Number); //테스트별 라인 처리*
matrix[x][y] = 1;
}
// m행 n열을 돌면서 1인 경우 재귀 호출하여 방문 처리하고, 그룹 수(결과) 증가
let result = 0;
for(let i = 0; i < m; i++) {
for(let j = 0; j < n; j++) {
if(dfs(matrix, m, n, i, j)) result += 1;
}
}
console.log(result);
line += k + 1; // 다음 테스트 입력 라인*
}
문제 2-1) 노드 사이의 거리 (골드5)
입력 형식
4 2 // n 노드 수 , m : 결과를 알고 싶은 노드 쌍의 수
2 1 2 // n-1 개의 두 노드와 비용
4 3 2
1 4 3
1 2 // m에 해당
3 2
- 방문 처리 배열과 비용 배열을 생각하지 못했다
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input[0].split(' ').map(Number); // n : 노드 수, m : 결과 찾아야 하는 노드 쌍
let line = 1;
const graph = Array.from({length : n + 1}, () => []);
for(let i = line; i < n; i++) {
const [from, to, cost] = input[i].split(' ').map(Number);
graph[from].push([to, cost]);
graph[to].push([from, cost]);
}
/*
graph
[
[],
[ [ 2, 2 ], [ 4, 3 ] ],
[ [ 1, 2 ] ],
[ [ 4, 2 ] ],
[ [ 3, 2 ], [ 1, 3 ] ]
]
*/
function dfs(x, dist) {
if(visited[x]) return;
visited[x] = true;
distance[x] = dist;
for(let [y, cost] of graph[x]) {
dfs(y, cost + dist);
}
}
line += (n - 1);
let visited;
let distance;
for(let i = line; i < line + m; i++) {
const [from, to] = input[i].split(' ').map(Number);
visited = new Array(n + 1).fill(false);
distance = new Array(n + 1).fill(-1);
dfs(from, 0);
console.log(distance[to]);
}
문제 2-2) 트리 (골드4)
- 그래프내 사이클 판별(중요*) 요하는 문제
- 그래프는 사이클 존재, 트리는 사이클 존재 x
입력
6 3 -- n : 정점 개수, m : 간선 수
1 2 -- m개의 간선 정보
2 3
3 4
6 5 -- n : 정점 개수, m : 간선 수
1 2 -- m개의 간선 정보
2 3
3 4
4 5
5 6
6 6 -- n : 정점 개수, m : 간선 수
1 2 -- m개의 간선 정보
2 3
1 3
4 5
5 6
6 4
0 0 -- 종료
사이클 판별(isCycle) 재귀함수 이해 잘 하기
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
function isCycle(x, prev) {
visited[x] = true;
for(let y of graph[x]) {
if(!visited[y]) {
if(isCycle(y, x)) return true;
} else if(y !== prev) {
return true;
}
}
return false;
}
let line = 0;
let graph;
let visited;
let testCase = 1;
while(true) {
const [n, m] = input[line++].split(' ').map(Number);
if(n === 0 && m === 0) break;
graph = Array.from({length : n + 1}, () => []);
for(let i = line; i < line + m; i++) { // 무방향 그래프 간주
const [from, to] = input[i].split(' ').map(Number);
graph[from].push(to);
graph[to].push(from);
}
visited = new Array(n +1).fill(false);
let treeCnt = 0;
for(let i = 1; i <= n; i++) {
if(!visited[i] && !isCycle(i, 0)) treeCnt++; // 방문한 적 없고, 사이클 없는 경우 트리
}
if(treeCnt == 0) console.log(`Case ${testCase}: No trees.`);
else if(treeCnt === 1) console.log(`Case ${testCase}: There is one tree.`);
else console.log(`Case ${testCase}: A forest of ${treeCnt} trees.`);
testCase += 1;
line += m;
}
참고. "간선의 개수 = 정점 - 1" 공식과 DFS로 품
백준 4803 트리 Java
https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한
dhbang.tistory.com
문제 3-1) 치킨배달 (골드5)
해당 문제 또한 아이디어가 생각나지 않아 헤매었다. 2차원 인접 행렬로 풀어야 하는가 싶었지만, 각각의 집과 치킨집 좌표만 따로 배열에 담고 치킨집 조합을 고른 후 주어진 수식에 따라 최소값을 구하면 되는 문제였다.(백트래킹 문제)
5 2 // N(2 ≤ N ≤ 50) : N개 줄의 도시정보, M(1 ≤ M ≤ 13) : 치킨집 조합 최대 개수 ( 5개중 2개 조합)
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
0: 빈칸, 1 : 집, 2: 치킨 집
집 (r1, c1) , 치킨집 (r2, c2) 있을 때 치킨 거리 = |r1 - r2| + |c1 - c2| 공식으로 구함
각 집별로 가장 가까운 치킨집 거리 구해서 합산했을 때 최소값을 구하면 되는 문제
*시간복잡도
1. 전체 치킨 집 x개 중 m 개를 고른 조합 : xCm
2. 치킨집과 집 간의 거리 계산 : 2n * m
결과 13Cm * 2n * m 이고 최대값으로 계산할 경우
= 13C6 * 2 * 50 * 6 = 1716 * 600 = 1,029,600 연산 소요됨
치킨집 조합의 경우 배열 인덱스로 하여 구하도록 함 (중복x, 순서x)
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input[0].split(' ').map(Number); // n * n 크기, n 줄 입력, m : 폐업하지 않을 치킨 집 개수(뽑을 조합 수)
const house = [];
const chicken = [];
for(let i = 1; i <= n; i++) {
const line = input[i].split(' ').map(Number);
for(let j = 0; j < n; j++) {
if(line[j] == 1) house.push([i, j]); // 집 (1)
if(line[j] == 2) chicken.push([i, j]); // 치킨집(2)
}
}
function dfs(depth, start) { // start 추가하여 시간초과 해결
if(depth === m) {
let totalChickenDistance = 0;
for(let [r1, c1] of house) {
let chickenDistance = 1e9;
for(let i of selected) { // m개의 치킨집 조합 중에 각각 집별로 가장 가까운 치킨집 거리 구함
const [r2, c2] = chicken[i];
chickenDistance = Math.min(Math.abs(r1 - r2) + Math.abs(c1 - c2), chickenDistance);
}
totalChickenDistance += chickenDistance; // 각 집 별로 최소 치킨 거리 합산
}
minChickenDistance = Math.min(totalChickenDistance, minChickenDistance);
return;
}
for(let i = start; i < chicken.length; i++) { // start 추가하여 시간초과 해결
if(visited[i]) continue;
visited[i] = true;
selected.push(i);
dfs(depth + 1, i + 1);
selected.pop(i);
visited[i] = false;
}
}
let minChickenDistance = 1e9; // 1* 10^9
const selected = [];
const visited = new Array(chicken.length).fill(false); // 각 치킨집 방문 여부
dfs(0, 0);
console.log(minChickenDistance);
문제 3-2) 단지번호붙이기 (실버1)
- 인접 행렬을 사용하여 1인 경우 dfs로 방문처리하면서 그룹별로 카운트하는 문제
- 2중 반복문에서 groupCnt 변수가 dfs 함수에서 갱신되지 않는 것을 확인 (삽질) -> dfs 함수 내부 scope로 변수가 적용된 듯..
- 그래서 강의 해설과 같이 dfs에서 카운트를 리턴하도록 처리
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
// 초기 입력
const n = Number(input[0]);
const matrix = [];
for(let i = 1; i <= n; i++) {
matrix.push(input[i].split('').map(Number));
}
// 함수 정의
function dfs(x, y) {
if(x < 0 || y < 0 || x >= n || y >= n) return 0;
if(matrix[x][y] === 1) {
matrix[x][y] = -1; // 방문 처리
let result = 1;
result += dfs(x, y + 1);
result += dfs(x -1, y);
result += dfs(x, y - 1);
result += dfs(x + 1, y);
return result;
}
return 0;
}
// 실행
let result = [];
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
if(matrix[i][j] === 1) {
const groupCnt = dfs(i, j);
if(groupCnt > 0) result.push(groupCnt);
}
}
}
result.sort((a, b) => a - b);
console.log(`${result.length}\n${result.join('\n')}`);
문제 4-1) 텀 프로젝트 (골드3)
- 그래프내 사이클 판별(중요*) 요하는 문제
- 단순히 사이클 발생하는 그룹 카운트를 세는 경우 답은 구해져도 실패로 뜸
- 방문(visited) 했는데 완료(finished) 되지 않은 경우 사이클 발생했다고 판별하는 개념이 이해가 어려웠음
- 학생의 수가 최대 10만이기 때문에 시간초과 발생가능 => 그래서 finished 배열 사용함
// SUCCESS
function dfs(x, graph, visited, finished, result) {
visited[x] = true;
let y = graph[x];
if(!visited[y]) {
dfs(y, graph, visited, finished, result );
} else if(!finished[y]) { // y대신 x넣는 실수하여 메모리 초과 발생
while(y !== x) {
result.push(y);
y = graph[y];
}
result.push(x);
}
finished[x] = true;
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let testCase = Number(input[0]);
let line = 1;
while(testCase > 0) {
const n = Number(input[line]);
const graph = [0, ...input[line + 1].split(' ').map(Number)];
const visited = new Array(n + 1).fill(false);
const finished = new Array(n + 1).fill(false);
const result = [];
for(let i = 1; i <= n; i++) {
if(!visited[i]) dfs(i, graph, visited, finished, result);
}
console.log(n - result.length);
line += 2;
testCase -= 1;
}
문제 4-2) 숫자 고르기 (골드5)
위에 문제 4-1과 동일한 사이클 판별 문제 (문제 설명 꼼꼼히 읽어보기.. 내가 원하는 내용이 출력 설명에 있었음)
예제 출력
3 -- 사이클을 이루는 최대 노드 수
1 -- 사이클 이루는 노드 번호 오름차순 출력
3
5
// SUCCESS
function dfs(x) {
visited[x] = true;
let y = graph[x];
if(!visited[y]) {
dfs(y);
} else if(!finished[y]) {
while(y !== x) {
result.push(y);
y = graph[y];
}
result.push(x);
}
finished[x] = true;
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const graph = [0];
for(let i = 1; i <= n; i++) graph.push(Number(input[i]));
let result = [];
const visited = new Array(n + 1).fill(false);
const finished = new Array(n + 1).fill(false);
for(let i = 1; i <= n; i++) if(!visited[i]) dfs(i);
result.sort((a, b) => a - b);
console.log(result.length)
for(let n of result) console.log(`${n}`);
문제 5-1) 적록색약 (골드5)
- 적록색약이 아닌 경우와 적록색약인 경우의 그룹 수 확인하는 문제 (적록색약인 경우 R === G 동일하게 봄)
// SUCCESS (내 답안)
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const matrix = [];
let visited = [];
for(let i = 1; i <= n; i++) {
matrix.push(input[i].split(''));
}
const dx = [0, -1, 0, 1];
const dy = [1, 0, -1, 0];
function dfs(x, y) {
visited[x][y] = true;
for(let i = 0; i < 4; i++) {
const _x = x + dx[i];
const _y = y + dy[i];
if(_x < 0 || _y < 0 || _x >= n || _y >= n) continue;
if(visited[_x][_y]) continue;
if(matrix[x][y] !== matrix[_x][_y]) continue; // 같은 색상이 아닌 경우
dfs(_x, _y);
}
}
function process() {
let result = 0;
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
if(!visited[i][j]) {
dfs(i, j, visited);
result += 1;
}
}
}
return result;
}
// 적록 색약이 아닌 경우
const result = [];
visited = Array.from({length : n}, () => new Array(n).fill(false));
result.push(process(n));
// 적록색약인 경우
visited = Array.from({length : n}, () => new Array(n).fill(false));
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
if(matrix[i][j] === 'G') matrix[i][j] = 'R';
}
}
result.push(process());
console.log(result.join(' '));- (참고) 강의 해설에서는 dfs 함수가 boolean 형으로 처리함
// 강의 해설
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const graph = [];
for(let i = 1; i <= n; i++) graph.push(input[i].split(''));
const dx = [0, -1, 0, 1];
const dy = [1, 0, -1, 0];
function dfs(x, y) {
if(visited[x][y]) return false;
visited[x][y] = true;
for(let i = 0; i < 4; i++) {
const _x = x + dx[i];
const _y = y + dy[i];
if(_x < 0 || _y < 0 || _x >= n || _y >= n) continue;
if(graph[x][y] === graph[_x][_y]) dfs(_x, _y); // 같은 색상인 경우
}
return true;
}
// 적록 색약이 아닌 경우
let result1 = 0;
let visited = [];
for(let i = 0; i < n; i++) visited.push(new Array(n).fill(false));
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
if(dfs(i, j)) result1 += 1;
}
}
// 적록색약인 경우 ( R -> G 로 변환 후 카운트)
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
if(graph[i][j] === 'R') graph[i][j] = 'G';
}
}
let result2 = 0;
visited = [];
for(let i = 0; i < n; i++) visited.push(new Array(n).fill(false));
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
if(dfs(i, j)) result2 += 1;
}
}
console.log(`${result1} ${result2}`);
문제 5-2) 연구소 (골드4)
- 절차 : 벽을 3개 세운다 -> 바이러스 전파 -> 안전 영역 카운팅하여 최대값 구함
- 해당 문제를 풀면서 2차원 인접 행렬에 대해 벽을 세울 조합을 어떻게 구하고, 처리할 지가 생각이 안나 어려웠다. (DFS)
n, m 이 최대 8일 때
1. 벽을 세우는 조합의 수 64C3 = 41,664
2. 매번 직접 "탐색"을 통해서 바이러스부터 안전한 구역을 확인 => 8 * 8 = 64
이에 따라 이중 반복문으로 실행할 경우
41,664 * 64 = 최대 2,666,496 연산 수행
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const graph = []; // 입력받은 그래프 원본
const grapWithWall = []; // 벽을 세운 그래프
for(let i = 1; i <= n; i++) {
graph.push(input[i].split(' ').map(Number));
grapWithWall.push(new Array(m).fill(0));
}
const dx = [0, -1, 0, 1];
const dy = [1, 0, -1, 0];
function spreadVirus(x, y) { // 4방향으로 바이러스 전파
for(let i = 0; i < 4; i++) {
const _x = x + dx[i];
const _y = y + dy[i];
if(_x < 0 || _y < 0 || _x >= n || _y >= m) continue;
if(grapWithWall[_x][_y] === 0) { // 0인 경우 바이러스 전파
grapWithWall[_x][_y] = 2;
spreadVirus(_x, _y);
}
}
}
function getSafityArea() {
let cnt = 0;
for(let i = 0; i < n; i++) {
for(let j = 0; j < m; j++) {
if(grapWithWall[i][j] === 0) cnt += 1;
}
}
return cnt;
}
let result = 0;
function dfs(count) {
if(count === 3) {
// 1. 벽을 3개 세운 조합을 임시 배열에 저장
for(let i = 0; i < n; i++) {
for(let j = 0; j < m; j++) {
grapWithWall[i][j] = graph[i][j];
}
}
// 2. 바이러스 전파
for(let i = 0; i < n; i++) {
for(let j = 0; j < m; j++) {
if(grapWithWall[i][j] === 2) spreadVirus(i, j);
}
}
// 3. 안전 지역(0) 카운팅
result = Math.max(result, getSafityArea());
return;
}
// 아래와 같이 DFS로 벽(1)을 3개 세우는 조합을 찾을 수 있도록 재귀 함수 처리
for(let i = 0; i < n; i++) {
for(let j = 0; j < m; j++) {
if(graph[i][j] === 0) {
graph[i][j] = 1;
dfs(count + 1);
graph[i][j] = 0;
}
}
}
}
dfs(0);
console.log(result);
나중에 BFS로도 해당 문제를 풀어보자 !
문제 6-1) 차이를 최대로 (실버2)
- 중복 없는 순열 (6! = 720 경우의 수 존재)
- 각 입력 값에 해당 하는 배열 인덱스로 순열 구함
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const data = input[1].split(' ').map(Number);
let result = 0;
let visited = new Array(n).fill(false);
function dfs(selected, depth, start) {
if(depth === n) {
let value = 0;
for(let i = 0; i < n-1; i++) {
value += Math.abs(data[selected[i]] - data[selected[i+1]]);
}
result = Math.max(result, value);
return;
}
for(let i = 0; i < n; i++) {
if(visited[i]) continue;
visited[i] = true;
selected.push(i);
dfs(selected, depth + 1, i);
visited[i] = false;
selected.pop();
}
}
dfs([], 0, 0);
console.log(result);- 배열 인덱스에 대한 순열을 구하지 않고, 해설처럼 값을 바로 순열로 구해서 처리하는게 좀 더 간결해 보임
// 강의 해설
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]);
const data = input[1].split(' ').map(Number);
const visited = new Array(n).fill(false);
const result = [];
let maxValue = -1e9;
function dfs(depth) {
if(depth === n) {
let value = 0;
for(let i = 0; i < n - 1; i++) value += Math.abs(result[i] - result[i + 1]);
maxValue = Math.max(maxValue, value);
}
for(let i = 0; i < n; i++) {
if(visited[i]) continue;
visited[i] = true;
result.push(data[i]);
dfs(depth + 1);
result.pop();
visited[i] = false;
}
}
dfs(0);
console.log(maxValue);
문제 6-2) 연산자 끼워넣기(실버1)
- 연산 부분에서 답이 나오지 않아 시간 소비한 문제
- JS에서 Math.floor() 와 ~~(double tilde) 가 음수일 때 값이 차이난다는 걸 알게 됨
Math.floor(-2.4) = -3
~~(-2.4) = -2
Math.floor(3/-2) = -2
~~(3/-2) = -1
// SUCCESS (강의 해설)
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]); // 수의 개수
const numbers = input[1].split(' ').map(Number);
let [add, sub, mul, div] = input[2].split(' ').map(Number);
let minValue = 1e9;
let maxValue = -1e9;
function dfs(index, value) {
if(index === n) {
minValue = Math.min(minValue, value);
maxValue = Math.max(maxValue, value);
return;
}
if(add > 0) {
add -= 1;
dfs(index + 1, value + numbers[index]);
add += 1;
}
if(sub > 0) {
sub -= 1;
dfs(index + 1, value - numbers[index]);
sub += 1;
}
if(mul > 0) {
mul -= 1;
dfs(index + 1, value * numbers[index]);
mul += 1;
}
if(div > 0) {
div -= 1;
dfs(index + 1, ~~(value / numbers[index]));
div += 1;
}
}
dfs(1, numbers[0]);
console.log(maxValue);
console.log(minValue);http://rocha.la/JavaScript-bitwise-operators-in-practice
Tilde or the Floor? Practical use for JavaScript bitwise operators. (#1) | rocha.la | JavaScript and my other hobbies
Tilde or the Floor? Practical use for JavaScript bitwise operators. (#1) Submitted by Piotr Rochala on Sat, 11/26/2011 - 12:10 JavaScript bitwise operators are one of these features of JavaScript that we always forget about. It seems like we assume there i
rocha.la
Ch 08. BFS (너비 우선 탐색) 알고리즘
- 탐색(Search)란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미함
- BFS는 기본적으로 Queue 자료 구조를 활용함
BFS 절차
- 시작 노드를 Queue에 넣고(enqueue) "방문 처리"함
- Queue에서 원소를 꺼내고 방문하지 않은 인접노드를 확인 => 있을 경우 Queue에 삽입 후 방문처리함
- 2번과정을 더 이상 반복할 수 없을 때 까지 반복 수행
다음과 같이 class Queue 정의하여 사용함
class Queue {
constructor() {
this.items = {};
this.headIndex = 0;
this.tailIndex = 0;
}
enqueue(item) {
this.items[this.tailIndex] = item;
this.tailIndex += 1;
}
dequeue() {
const item = this.items[this.headIndex];
delete this.items[this.headIndex];
this.headIndex += 1;
return item;
}
peek() {
return this.items[this.headIndex];
}
length() {
return this.tailIndex - this.headIndex;
}
}
문제 1-1) 숨바꼭질 (실버1)
- 1초당 현재 위치에서 + 1, -1, *2 에 해당 하는 위치로 이동하게 된다
- 1초 후에 이동한 상태값을 정점으로 보고, +1, -1, *2 를 방향선 간선으로 봄
- 고로 가장 빨리 동생을 찾는 방법 => 최소 개수로 간선 이동하는 방법
- 정점이 최대 10만개일 때 간선은 10만개 * 3 (개당 3개의 방향 간선 가짐) 가지므로 약 O(10^5) 시간과 공간복잡도 가짐
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, k] = input[0].split(' ').map(Number);
const MAX_VALUE = 100001;
const visited = new Array(MAX_VALUE).fill(0);
function bfs() {
const queue = new Queue();
queue.enqueue(n);
while(queue.length() > 0) {
let current = queue.dequeue();
if(current === k) {
return visited[k];
}
for(let next of [current - 1, current + 1, current *2]) {
if(next < 0 || next >= MAX_VALUE) continue;
if(visited[next] === 0) { // 방문하지 않은 경우
queue.enqueue(next);
visited[next] = visited[current] + 1; // 이전 이동 횟수 + 1
}
}
}
}
console.log(bfs());
문제 1-2) 나이트 이동 (실버1)
두 가지 부분에서 문제가 되서 정답 판정을 받지 못했다. (30분 소요)
- 테스트 케이스별로 line += 3 을 해줘야 하는데 line += testCase 로 하는 바람에 TypeError 발생 (
3으로 고정인 줄 착각함) - 나이트가 움직이는 방향 좌표 정의 순서에 따라 값에 차이가 발생함
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
// 실수1 : 왼쪽 - 아래 - 오른쪽 - 위 순서로 탐색해야 정답 나옴
const dx = [-2, -2, -1, 1, 2, 2, 1, -1];
const dy = [-1, 1, -2, -2, -1, 1, 2, 2];
function bfs(n, startX, startY, targetX, targetY) {
const queue = new Queue();
queue.enqueue([startX, startY]);
const visited = Array.from({length : n}, () => new Array(n).fill(0));
while(queue.length() > 0) {
let [x, y] = queue.dequeue();
if(targetX === x && targetY === y) {
return visited[targetX][targetY];
}
for(let i = 0; i < 8; i++) {
const _x = x + dx[i];
const _y = y + dy[i];
if(_x < 0 || _y < 0 || _x >= n || _y >= n ) continue;
if(visited[_x][_y] !== 0) continue;
visited[_x][_y] = visited[x][y] + 1;
queue.enqueue([_x, _y]);
}
}
}
let testCase = Number(input[0]);
let line = 1;
for(let i = 0; i < testCase; i++) {
const n = Number(input[line]);
const [startX, startY] = input[line + 1].split(' ').map(Number);
const [targetX, targetY] = input[line + 2].split(' ').map(Number);
console.log(bfs(n, startX, startY, targetX, targetY));
line += 3; // 실수2 : testCase가 무조건 3인줄 착각
}
문제 2-1) 이분 그래프 (골드4)
참고.
https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html
[알고리즘] 이분 그래프(Bipartite Graph)란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
Point.
인접한 정점끼리 번갈아가면 색칠했을 때 두 가지 색만으로 정점 표시 가능한 경우 이분 그래프로 판별
(*만약에 인접한 노드의 색깔이 서로 같다면 이분그래프가 아님)
입력 예시
2 -- 테스트 케이스
3 2 -- V : 정점의 개수, E : 간선의 개수 (case1)
1 3 -- E 개 만큼의 정보가 주어짐
2 3
4 4 -- E 개 만큼의 정보가 주어짐(case2)
1 2
2 3
3 4
4 2
풀이
- 방문시 0, 1(Red, Blue)를 교차하여 갱신하는 방식으로 bfs 탐색 후 서로 인접한 노드가 같은 색인지 판별 (강의 해설 참고)
틀린 부분
- bfs 실행하는 반복문 부분과 시작 노드 0으로 초기화 누락
// SUCCESS
function bfs(n, graph, visited) {
const queue = new Queue();
queue.enqueue(n);
visited[n] = 0; // 처음 노드는 Red 처리 (틀린 부분*)
while(queue.length() > 0) {
const current = queue.dequeue();
for(let next of graph[current]) {
if(visited[next] === -1) {
visited[next] = (visited[current] + 1) % 2; // -1 : 방문하지 않는 경우 , 0 : Red , 1 : Blue
queue.enqueue(next);
}
}
}
}
function isBipartite(graph, visited) {
for(let i = 1; i < visited.length; i++) { // 같은 색상인 경우 이분 트리가 아니다
for(let j of graph[i]) if(visited[i] === visited[j]) return false;
}
return true;
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let testCase = Number(input[0]);
let line = 1;
while(testCase > 0) {
const [v, e] = input[line].split(' ').map(Number);
const visited = new Array(v + 1).fill(-1);
const graph = Array.from({length : v + 1}, () => []);
for(let i=1; i <= e; i++) {
const [from, to] = input[line + i].split(' ').map(Number);
graph[from].push(to);
graph[to].push(from);
}
// 틀린 부분*
for(let i = 1; i <= v; i++) {
if(visited[i] === -1) bfs(i, graph, visited);
}
console.log(isBipartite(graph, visited) ? "YES" : "NO");
line += e + 1;
testCase -= 1;
}
문제 2-2) 4연산 (골드5)
['*', '+', '-', '/'] 간선 이동했을 때 각 값이 정점이라고 생각 (문제 1-1 숨바꼭질과 유사)
틀린 부분
- 방문 여부 확인 하는 visited 를 Set 자료구조 처리하는 것을 생각 못 함
- 최대값이 10^9 까지 인데 while 문 안에서 부등호를 >= 해서 오답 판정 받음
// SUCCESS
function bfs(s, t) {
const queue = new Queue();
queue.enqueue([s, '']);
// 방문 여부 확인
const visited = new Set([s]); // 생성자 초기화시 new Set([s]); 형태*
let found = false;
while(queue.length() > 0) {
const [current, operations] = queue.dequeue();
if(current > 1e9) continue; // 값의 범위를 벗어나는 경우*
if(current === t) {
console.log(operations);
found = true;
break;
}
for(let op of ['*', '+', '-', '/']) {
let next = current;
if(op === '*') next *= current;
else if(op === '+') next += current;
else if(op === '-') next -= current;
else if(op === '/' && s !== 0) next = 1; // 자기자신을 나누니 1
if(!visited.has(next)) {
queue.enqueue([next, operations + op]);
visited.add(next);
}
}
}
if(!found) console.log(-1);
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [s, t] = input[0].split(' ').map(Number);
if(s === t) console.log(0);
else bfs(s, t);
참고. new Set(iterable) , new Set()
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/Set
Set() constructor - JavaScript | MDN
The Set() constructor creates Set objects.
developer.mozilla.org
문제 3-1) 경쟁적 전염(골드5)
초기 K 개의 바이러스 정보를 어떻게 알 수 있을까? 초기화때 임시 배열*에 정보 저장 후 오름차순 정렬하여 사용
입력 예시
3 3 -- N : 행렬크기, K : 바이러스 번호 정보 (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000)
1 0 2 -- N개 줄에 걸쳐 각 행은 N개의 원소로 구성 ( N * N )
0 0 0
3 0 0
2 3 2 -- S, X, Y : S초 뒤에 (X,Y)에 존재하는 바이러스를 구하는 문제(없으면 0을 출력)
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, k] = input[0].split(' ').map(Number);
const graph = []; // 전체 보드 정보를 담는 리스트
const data = []; // 바이러스에 대한 정보를 담는 리스트
for(let i = 0; i < n; i++) {
graph.push(input[i + 1].split(' ').map(Number));
for(let j = 0; j < n; j++) { // 강의 참고
if(graph[i][j] !== 0) {
// ( 바이러스 종류, x위치, y위치 )
data.push([graph[i][j], i, j]);
}
}
}
data.sort((a, b) => a[0] - b[0]); // 바이러스 번호 순으로 오름차순 정렬
let [s, x, y] = input[n + 1].split(' ').map(Number);
// Queue 초기화 : 초기 바이러스 위치 입력
const queue = new Queue();
for(let x of data) {
queue.enqueue(x);
}
const dx = [0, -1, 0, 1];
const dy = [1, 0, -1, 0];
while(s > 0) { // 초 단위
// 바이러스 전파 수행
for(let i = 0; i < queue.length(); i++) {
const [virus, x, y] = queue.dequeue();
for(let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if(graph[nx][ny] === 0) {
graph[nx][ny] = virus;
queue.enqueue([virus, nx, ny]);
}
}
}
s -= 1;
}
// 결과 출력
console.log(graph[x-1][y-1]);
큐 반복시 시간(초)을 갱신하며 처리하도록 함
// 강의 해설
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, k] = input[0].split(' ').map(Number);
const graph = []; // 전체 보드 정보를 담는 리스트
const data = []; // 바이러스에 대한 정보를 담는 리스트
for(let i = 0; i < n; i++) {
graph.push(input[i + 1].split(' ').map(Number));
for(let j = 0; j < n; j++) {
if(graph[i][j] !== 0) {
// ( 바이러스 종류, 시간, x위치, y위치 )
data.push([graph[i][j], 0, i, j]);
}
}
}
data.sort((a, b) => a[0] - b[0]); // 오름차순 정렬
let [targetS, targetX, targetY] = input[n + 1].split(' ').map(Number);
// Queue 초기화
const queue = new Queue();
for(let x of data) {
queue.enqueue(x);
}
const dx = [0, -1, 0, 1];
const dy = [1, 0, -1, 0];
while(queue.length() > 0) {
let [virus, s, x, y] = queue.dequeue();
// 정확히 s 초 지나거나, 큐가 빌때까지 반복
if(s === targetS) break;
for(let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if(graph[nx][ny] === 0) {
graph[nx][ny] = virus;
queue.enqueue([virus, s + 1, nx, ny]);
}
}
}
// 결과 출력
console.log(graph[targetX-1][targetY-1]);
문제 3-2) 특정 거리의 도시 찾기 (실버2)
- 방향 그래프로 보고 인접 리스트로 이동 수를 더해서 구해주면 되는 전형적인 BFS 문제
- 문제) distance를 0으로 초기화 하고 for문에서 0인 경우 처리하도록 했었는데 실패함
=> 결과적으로 초기 distance 를 -1로 초기화 후 distance[start] = 0 하도록 수정하여 통과
// SUCCESS
function bfs(n, start, k) {
const queue = new Queue();
queue.enqueue(start);
const distance = new Array(n + 1).fill(-1); // -1로 초기화, 강의 해설 참고
distance[start] = 0; // 시작 노드*
while(queue.length() > 0) {
const current = queue.dequeue();
for(let next of graph[current]) {
if(distance[next] === -1) {
distance[next] = distance[current] + 1;
queue.enqueue(next);
}
}
}
let check = false;
for(let i = 1; i <=n ; i++) {
if(distance[i] === k) {
console.log(i);
check = true;
}
}
if(!check) console.log(-1);
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [n, m, k, x] = input[0].split(' ').map(Number);
const graph = Array.from({length : n + 1}, () => []);
for(let i = 1; i <= m; i++) {
const [from, to] = input[i].split(' ').map(Number);
graph[from].push(to);
}
bfs(n, x, k);
문제 4-1) 환승 (골드2)
- 하이퍼 튜브(K)에 또한 노드라는 것을 생각하지 못하였고, 이로인해 그래프 표현 방식이 잘못되었음
- 결과적으로 1 ~ N 까지 최소 이동거리는 (distance / 2) + 1 로 구하게 된다 ( 절반은 하이퍼 튜브 이므로, +1은 출발역 )
9 3 5 -- N : 역의 수, K : 하이퍼 튜브가 서로 연결하는 역의 수(*), M : 하이퍼 튜브의 개수
1 2 3 -- M개 라인 만큼 입력, 하이퍼 튜브 n + 1번은 1,2,3 연결
1 4 5 -- 하이퍼 튜브 n + 2번은 1,4,5 연결
3 6 7 -- 하이퍼 튜브 n + 3번은 3,6,7 연결
5 6 7
6 8 9
// SUCCESS
function bfs(n, m) {
const queue = new Queue();
queue.enqueue([1, 1]); // start, dist
const visited = new Array(n + m + 1).fill(false); // Set 으로도 처리 가능
visited[1] = true;
let find = false;
while(queue.length() > 0) {
const [now, dist] = queue.dequeue();
if(now === n) {
console.log(parseInt(dist / 2) + 1);
find = true;
break;
}
for(let next of graph[now]) {
if(!visited[next]) {
queue.enqueue([next, dist + 1]);
visited[next] = true;
}
}
}
if(!find) console.log(-1);
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
// n : 역의 개수, k : 하이퍼 튜브별 연결 역의 개수, m : 하이퍼 튜브 개수(라인)
let [n, k, m] = input[0].split(' ').map(Number);
const graph = Array.from({length : n + m + 1}, () => []);
for(let i = 1; i <= m; i++) {
const line = input[i].split(' ').map(Number);
const hyperTube = n + i;
for(let l of line) {
graph[hyperTube].push(l);
graph[l].push(hyperTube);
}
}
bfs(n, m);
문제 4-2) 결혼식 (실버2)
- 1번 노드 기준으로 distance 가 1(친구), 2(친구의 친구) 인 경우를 구하면 되는 문제였음(문제 3-2와 유사)
// SUCCESS
function bfs(n, start) {
const queue = new Queue();
queue.enqueue(start);
const distance = new Array(n + 1).fill(-1);
distance[start] = 0;
while(queue.length() > 0) {
const current = queue.dequeue();
for(let next of graph[current]) {
if(distance[next] !== -1) continue;
distance[next] = distance[current] + 1;
queue.enqueue(next);
}
}
let result = 0;
for(let d of distance) {
if(d === 1 || d === 2) result++;
}
console.log(result);
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const n = Number(input[0]); // n : 상근이의 동기의 수 (=노드 수)
const m = Number(input[1]); // m : 리스트 길이
const graph = Array.from({length : n + 1}, () => []);
for(let i = 2; i < m + 2; i++) {
const [from, to] = input[i].split(' ').map(Number);
graph[from].push(to);
graph[to].push(from);
}
bfs(n, 1);
문제 5-1) 치즈 (골드3)
방법
- 치즈 내부의 공간은 치즈 외부 공기와 접촉하지 않은 것으로 간주 => 단순히 주변이 0인지를 확인하는 방식으로는 해결할 수 없다
- 즉, 외부 공기를 정확히 파악하기 위해 (0,0) 위치에서 출발하여 BFS를 진행한다. (가장자리는 항상 치즈가 없기 때문)
- 인접한 위치에 치즈가 있다면, 치즈가 있는 위치에 대해 카운트 수행
- 카운트가 2이상인 치즈를 녹인다.
외부 공기인 경우 Queue 에 담아 탐색하고, 공기에 맞닿은 치즈의 경우 카운트를 증가 시켜준다 (bfs 대상이 치즈가 아닌 공기*)
기본적으로 치즈는 1이기 때문에 3이상인 치즈가 해당 턴에 삭제 대상에 해당 => 녹일 때 치즈 2는 1로 초기화 (다음 턴 위해)
// SUCCESS
const dx = [0, -1, 0, 1];
const dy = [1, 0, -1, 0];
function bfs(_row, _col) {
const visited = [];
for(let i = 0; i < row; i++) visited.push(new Array(_col).fill(false));
visited[0][0] = true;
const queue = new Queue();
queue.enqueue([0, 0]);
while(queue.length() > 0) {
const [x, y] = queue.dequeue();
for(let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= _row || ny >= _col) continue;
if(visited[nx][ny]) continue;
if(graph[nx][ny] >= 1) { // 치즈인 경우
graph[nx][ny] += 1;
} else { // 외부 공기인 경우
visited[nx][ny] = true;
queue.enqueue([nx, ny]);
}
}
}
}
function melt() {
let finish = true;
for(let i = 0; i < row; i++) {
for(let j = 0; j < col; j++) {
if(graph[i][j] >= 3) { // 외부 공기와 2면이상 접촉한 치즈의 경우 녹인다.
graph[i][j] = 0;
finish = false;
} else if(graph[i][j] === 2) {
graph[i][j] = 1;
}
}
}
return finish;
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [row, col] = input[0].split(' ').map(Number);
const graph = [];
for(let i = 1; i <= row; i++) {
graph.push(input[i].split(' ').map(Number));
}
//녹일 때 3이상인 경우 0으로 초기화, 2인 경우 1로 초기화
let result = 0;
while(true) {
bfs(row, col);
if(melt()) {
console.log(result);
break;
}
result += 1;
}
문제 5-2) A -> B (실버2)
- 탐욕(그리드) 알고리즘으로 풀었던 문제를 'BFS-최단거리' 으로 풀도록 한다.
- 방문여부를 Set() 자료구조로 확인
2 → 4 → 8 → 81 → 162
오름차순으로 볼 때
- 2를 곱하기
- 10을 곱한다음 1을 더하기
내림차순으로 볼 때
- 2배 => 2로 나눌 때 나머지 0인 경우
- 1을 수의 가장 오른쪽에 붙이기 => 10으로 나눴을 때 나머지 1인 경우
// SUCCESS
function bfs(from, to) {
const queue = new Queue();
queue.enqueue([from, 0]);
const visited = new Set();
let find = false;
while(queue.length() > 0) {
const [value, dist] = queue.dequeue();
if(value > 1e9) continue;
if(value === to) {
console.log(dist + 1);
find = true;
break;
}
for(let op of ["/", "*"]) {
let next = value;
if(op === "/") {
next *= 10;
next += 1;
} else if(op === "*") {
next *= 2;
}
if(!visited.has(next)) { // 방문 여부*
queue.enqueue([next, dist + 1]);
visited.add(next);
}
}
}
if(!find) console.log(-1);
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let [a, b] = input[0].split(' ').map(Number);
bfs(a, b);
문제 6-1) 인구 이동 (골드5)
조건에 맞는 연합인 경우를 처리할 아이디어가 생각나지 않아 어려운 문제 (다시 풀어보기)
필요한 변수
(1) union[][] : 연합 번호 할당
(2) summary : 연합의 인구 수 총 합
(3) cnt : 연합의 수
(4) united[][] : 연합 좌표 저장
// SUCCESS
const dx = [0, -1, 0, 1];
const dy = [1, 0, -1, 0];
function bfs(x, y, index, union) {
const queue = new Queue();
queue.enqueue([x, y]);
union[x][y] = index; // 현재 연합의 번호 할당
let summary = graph[x][y]; // 현재 연합의 전체 인구 수
let cnt = 1;
const united = [[x, y]]; // (x, y)의 위치와 연결된 나라(연합) 정보를 담는 리스트
while(queue.length() > 0) {
const [x, y] = queue.dequeue();
for(let i = 0; i < 4; i++) {
const nx = x + dx[i];
const ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
if(union[nx][ny] !== -1) continue;
const diff = Math.abs(graph[nx][ny] - graph[x][y]); // 옆 나라와 인구 수 차이
if(L <= diff && diff <= R) {
queue.enqueue([nx, ny]);
union[nx][ny] = index; // 연합 번호 추가
united.push([nx, ny]);
summary += graph[nx][ny];
cnt += 1;
}
}
}
for(let u of united) { // 연합 국가 끼리 인구 분배
const [i, j] = u;
graph[i][j] = parseInt(summary / cnt);
}
}
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
// N * N, 조건 L <= x <= R 인 경우 하루동안 국경선을 연다
let [N, L, R] = input[0].split(' ').map(Number);
const graph = [];
let line = 1;
for(let i = 0; i < N; i++) {
const row = input[line + i].split(' ').map(Number);
graph.push(row);
}
let result = 0;
while(true) {
const union = Array.from({length : N}, () => new Array(N).fill(-1));
let index = 0; // ?
for(let i = 0; i < N; i++) {
for(let j = 0; j < N; j++) {
if(union[i][j] === -1) {
bfs(i, j, index, union);
index++;
}
}
}
if(index === N * N) break; // 모든 인구 이동이 끝난 경우 (조건을 만족안하면 )
result += 1;
}
console.log(result);
참고용
1회차
united : [
[ 0, 0 ], [ 0, 1 ],
[ 1, 0 ], [ 0, 2 ],
[ 1, 1 ], [ 1, 2 ],
[ 2, 1 ]
]
union :[ [ 0, 0, 0 ], [ 0, 0, 0 ], [ -1, 0, -1 ] ]
summary : 142
united : [ [ 2, 0 ] ]
union :[ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 1, 0, -1 ] ]
summary : 40
united : [ [ 2, 2 ] ]
union :[ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 1, 0, 2 ] ]
summary : 10
2회차 시작
united : [ [ 0, 0 ] ]
union :[ [ 0, -1, -1 ], [ -1, -1, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 0, 1 ] ]
union :[ [ 0, 1, -1 ], [ -1, -1, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 0, 2 ] ]
union :[ [ 0, 1, 2 ], [ -1, -1, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 1, 0 ] ]
union : [ [ 0, 1, 2 ], [ 3, -1, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 1, 1 ] ]
union : [ [ 0, 1, 2 ], [ 3, 4, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 1, 2 ], [ 2, 2 ], [ 2, 1 ] ]
union :[ [ 0, 1, 2 ], [ 3, 4, 5 ], [ -1, 5, 5 ] ]
summary : 50
united : [ [ 2, 0 ] ]
union :[ [ 0, 1, 2 ], [ 3, 4, 5 ], [ 6, 5, 5 ] ]
summary : 40
3회차 시작 - 조건을 만족하는 경우가 없으므로 index 만 증가하게 됨
united : [ [ 0, 0 ] ]
union :[ [ 0, -1, -1 ], [ -1, -1, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 0, 1 ] ]
union :[ [ 0, 1, -1 ], [ -1, -1, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 0, 2 ] ]
union :[ [ 0, 1, 2 ], [ -1, -1, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 1, 0 ] ]
union :[ [ 0, 1, 2 ], [ 3, -1, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 1, 1 ] ]
union :[ [ 0, 1, 2 ], [ 3, 4, -1 ], [ -1, -1, -1 ] ]
summary : 20
united : [ [ 1, 2 ] ]
union :[ [ 0, 1, 2 ], [ 3, 4, 5 ], [ -1, -1, -1 ] ]
summary : 16
united : [ [ 2, 0 ] ]
union :[ [ 0, 1, 2 ], [ 3, 4, 5 ], [ 6, -1, -1 ] ]
summary : 40
united :[ [ 2, 1 ] ]
union :[ [ 0, 1, 2 ], [ 3, 4, 5 ], [ 6, 7, -1 ] ]
summary : 16
united :[ [ 2, 2 ] ]
union :[ [ 0, 1, 2 ], [ 3, 4, 5 ], [ 6, 7, 8 ] ]
summary : 16
결과.
2
문제 6-2) 뱀 (골드4)
- 지금까지 푼 문제 중에 변수가 가장 많이 필요하고 한번에 파악이 안되었음
입력 예시
6 -- N : 보드의 크기
3 -- K : 사과의 위치 (라인 수)
3 4 -- row, col
2 5
5 3
3 -- L : 뱀의 방향 변환 횟수
3 D
15 L
17 D
입력 예시.
// SUCCESS
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let n = Number(input[0]); // 맵의 크기
let k = Number(input[1]); // 사과의 개수
// 맵 초기화
let graph = [];
for(let i = 0; i < n + 1; i++) {
graph.push(new Array(n + 1).fill(0));
}
for(let i = 2; i <= (k + 1); i++) {
const [a, b] = input[i].split(' ').map(Number);
graph[a][b] = 1; // 1: 사과
}
let L = Number(input[k + 2]); // 방향 전환 입력 횟수
let cmds = [];
for(let i = k + 3; i < (k + 3 + L); i++) {
let [x, c] = input[i].split(' ');
cmds.push([Number(x), c]);
}
// 방향 주의 [동, 남, 서, 북]
const dx = [0, 1, 0, -1];
const dy = [1, 0, -1, 0];
function move(dir, cmd) {
let result;
if(cmd === 'L') {
result = dir - 1;
if(result < 0) result = 3; // 해당 조건식이 틀린 걸 못찾아서 2시간 넘게 소요*
} else {
result = (dir + 1) % 4;
}
return result;
}
const queue = new Queue();
queue.enqueue([1, 1]);
graph[1][1] = 2;
let headX = 1;
let headY = 1;
let t = 0;
let direction = 0;
let cmdIndex = 0;
while(true) {
let nx = headX + dx[direction];
let ny = headY + dy[direction];
if(1 <= nx && 1 <= ny && nx <= n && ny <= n && graph[nx][ny] !== 2) {
if(graph[nx][ny] === 0) {
let [bx, by] = queue.dequeue();
graph[bx][by] = 0;
graph[nx][ny] = 2;
queue.enqueue([nx, ny]);
}
if(graph[nx][ny] === 1) {
graph[nx][ny] = 2;
queue.enqueue([nx, ny]);
}
} else {
t += 1;
break;
}
headX = nx;
headY = ny;
t += 1;
//방향 전환
if(cmdIndex < L && (t === cmds[cmdIndex][0])) {
direction = move(direction, cmds[cmdIndex][1]);
cmdIndex += 1;
}
}
console.log(t);
Ch 09. 다이나믹 프로그래밍
추후 예정
학습 후기 (+ 인증사진)
3주차에서는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)에 대해 학습할 수 있었다.
DFS에서는 재귀 함수를 사용하여 조합(Combination, 순서 의미 없음), 순열(Permutation, 순서 의미 있음), 그리고 사이클 판별 같은 기법과 DFS 기본 구조와 함께 문제 풀이 방법에 대해 알 수 있었다. -- 백트래킹(완전 탐색)과도 연관됨
BFS의 특징으로 노드와 간선 사이의 가중치가 1인 경우에 해당 알고리즘을 사용 가능하다는 점이 눈에 띄었다. (가중치가 상이한 경우 다익스트라 알고리즘 등을 사용해야 함). 그리고 "문제1-1)숨바꼭질", "문제2-2) 4연산" 문제를 풀어보면서 시작 노드에서부터 변화되는 상태값들을 각각의 노드로 바라보고 그래프 문제 풀이하는 방식에 대해 알 수 있었다.
전반적으로 기본 틀을 다루는 문제의 경우 쉽게 풀 수 있었으나, 구현 문제에 대해서는 아이디어가 생각나지 않아 문제 풀이를 보고 손으로 그려본 다음에 이해 가능했다는 점에서 연습이 많이 요할 것으로 판단이 된다. 제한된 시간내에 문제를 풀기 위해 공간(변수)를 좀 더 사용한다는 말이 생각나는 시간이었다.
DFS 다시 풀어보기
문제 2-1) 노드 사이의 거리 (골드5)
문제 2-2) 트리 (골드4)
문제 3-2) 단지번호붙이기 (실버1)
문제 4-1) 텀 프로젝트 (골드3)
문제 5-2) 연구소 (골드4)
문제 6-2) 연산자 끼워넣기(실버1)
BFS 다시 풀어보기
문제 2-1) 이분 그래프 (골드4)
문제 2-2) 4연산 (골드5)
문제 3-1) 경쟁적 전염(골드5)
문제 4-1) 환승 (골드2)
문제 6-1) 인구 이동 (골드5)
문제 6-2) 뱀 (골드4)
https://fastcampus.co.kr/dev_online_upjscodingtest
UPSKILL : Javascript 코딩테스트 131개 예제 & CS지식으로 끝내기 | 패스트캠퍼스
25시간 대비 과정 / '코테 레전드' 유튜버 강사님께 핵심만 배우고 빠르게 합격하세요.
fastcampus.co.kr
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
'공부 > Javascript' 카테고리의 다른 글
| 패스트캠퍼스 JavaScript 코딩테스트 강의 한 달 후기 (3) | 2023.05.12 |
|---|---|
| 패스트캠퍼스 JavaScript 코딩테스트 강의 4주차 (0) | 2023.05.08 |
| 패스트캠퍼스 JavaScript 코딩테스트 강의 2주차 (0) | 2023.04.24 |
| 패스트캠퍼스 JavaScript 코딩테스트 강의 1주차 (0) | 2023.04.17 |
| 정규 표현식 문법 정리 (1) | 2023.01.24 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!
