https://www.acmicpc.net/problem/2178

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map( i => Number(i));
const maps = [];
const vector = [[0,1], [1,0], [0,-1], [-1,0]];

input.forEach((i) => {
   i = i.split("").map(d => Number(d));
   maps.push(i);
});

const bfs = () => {
    const queue = [[0,0]];

    while(queue.length) {
        const cur = queue.shift();

        if(maps[cur[0]][cur[1]] !== 0) {
            const vectors = [];

            vector.forEach((v) => {
                const x = cur[0]+v[0];
                const y = cur[1]+v[1];

                if(x >= 0 && y >= 0 && x < N && y < M && maps[x][y] === 1) {
                    vectors.push([x,y]);
                }
            });

            let prev = maps[cur[0]][cur[1]];

            vectors.forEach((v) => {
                maps[v[0]][v[1]] = prev+1;
            })

            queue.push(...vectors);
        }
    }

    return maps[N-1][M-1];
}


console.log(bfs());
728x90

'Algorithm&CodingTest > Baekjoon' 카테고리의 다른 글

[Baekjoon][1495] 실버1 - 기타리스트  (0) 2023.04.22
[Beakjoon] [1271] 브론즈 5 - 엄청난 부자2  (0) 2023.03.17
[Baekjoon] [1766] 위상정렬 골드2 - 문제집  (0) 2023.03.15
[Baekjoon] [2667] DFS/BFS 실버 1 - 단지번호붙이기  (0) 2023.03.14
[ Baekjoon ] [11724] DFS/BFS 실버 2 - 연결 요소의 개수  (0) 2023.03.14

https://www.acmicpc.net/problem/1766

 

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주

www.acmicpc.net

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map(n => Number(n));
const graph = new Array(N+1).fill(0).map(i => []);
const indegree = new Array(N+1).fill(0);

for(let i = 0 ; i < M ; i++) {
    const [to, from] = input[i].split(' ').map(n => Number(n));
    graph[to].push(from);
    indegree[from]++;
}

const tOrder = [];
const queue = [];

for(let i = 1; i < graph.length ; i ++) {
    if(indegree[i] === 0) {
        queue.push(i);
        break;
    }
}

while(queue.length) {
    const node = queue.shift();
    indegree[node] = -1;

    const targetNode = graph[node];
    targetNode.forEach((i) => {
       indegree[i]--;
    });
    tOrder.push(node);

    for(let i = 1; i < graph.length ; i ++) {
        if(indegree[i] === 0) {
            queue.push(i);
            break;
        }
    }
}

console.log(tOrder.join(" "))
728x90

'Algorithm&CodingTest > Baekjoon' 카테고리의 다른 글

[Beakjoon] [1271] 브론즈 5 - 엄청난 부자2  (0) 2023.03.17
[Baekjoon] [2178] DFS/BFS 실버1 - 미로 탐색  (0) 2023.03.17
[Baekjoon] [2667] DFS/BFS 실버 1 - 단지번호붙이기  (0) 2023.03.14
[ Baekjoon ] [11724] DFS/BFS 실버 2 - 연결 요소의 개수  (0) 2023.03.14
[ Baekjoon ] [1260] DFS/BFS 실버 2 - DFS와 BFS  (0) 2023.03.13

https://www.acmicpc.net/problem/2667

 

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
const vector = [[1,0], [-1,0], [0,1], [0,-1]];

let cnt = 0;

const N = Number(input.shift());
const maps = input.map((i) => {
   i = i.split("").map(d => Number(d));
   return i;
});

const dfs = (start) => {
    const stack = [start];

    let cnt = 0;
    while(stack.length) {
        const cur = stack.pop();
        if(maps[cur[0]][cur[1]]) {
            maps[cur[0]][cur[1]] = 0;
            cnt++;
            const vectors = [];
            vector.forEach((v) => {
                if(v[0]+cur[0] >= 0 && v[0]+cur[0] < maps.length && v[1]+cur[1] >= 0 && v[1]+cur[1] < maps[0].length) {
                    vectors.push([v[0]+cur[0], v[1]+cur[1]]);
                }
            });
            stack.push(...vectors);
        }
    }
    return cnt;
}

let answer = 0;
let answerArr = [];

for(let i = 0; i < maps.length ; i++) {
    for(let j = 0 ; j < maps[0].length ; j++) {
        const result = dfs([i,j]);
        if(result) {
            answer++;
            answerArr.push(result);
        }
    }
}

answerArr = answerArr.sort(function(a,b) {
    return a - b;
});
console.log(answer);
for(let i = 0 ; i < answer ;i ++) {
    console.log(answerArr[i]);
}
728x90

'Algorithm&CodingTest > Baekjoon' 카테고리의 다른 글

[Baekjoon] [2178] DFS/BFS 실버1 - 미로 탐색  (0) 2023.03.17
[Baekjoon] [1766] 위상정렬 골드2 - 문제집  (0) 2023.03.15
[ Baekjoon ] [11724] DFS/BFS 실버 2 - 연결 요소의 개수  (0) 2023.03.14
[ Baekjoon ] [1260] DFS/BFS 실버 2 - DFS와 BFS  (0) 2023.03.13
[ Baekjoon ] [1049] 그리디 실버3 - 기타줄  (0) 2023.03.13

https://www.acmicpc.net/problem/11724

 

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주

www.acmicpc.net

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, M] = input.shift().split(" ").map( i => Number(i));
const graph = new Array(N+1).fill(0).map(i => []);
let V = new Array(N+1).fill(false);

input.forEach((i) => {
    const [to, from] = i.split(" ").map(n => Number(n));
    graph[to].push(from);
    graph[from].push(to);
});

const dfs = (start) => {
    const visited = [];
    let stack = [start];

    while(stack.length) {
        const cur = stack.pop();
        if(!visited.includes(cur)) {
            visited.push(cur);
            V[cur] = true;
            stack.push(...graph[cur]);
            graph[cur].length = 0;
        }
    }
    return visited;
}

let start = 1;
let cnt = 0;

while(start !== graph.length) {
    if(graph[start].length) {
        dfs(start);
        cnt++;
    }
    start++;
}

V = V.filter(v => !v);
console.log(V.length > 1 ? cnt+V.length-1 : cnt);
728x90

'Algorithm&CodingTest > Baekjoon' 카테고리의 다른 글

[Baekjoon] [1766] 위상정렬 골드2 - 문제집  (0) 2023.03.15
[Baekjoon] [2667] DFS/BFS 실버 1 - 단지번호붙이기  (0) 2023.03.14
[ Baekjoon ] [1260] DFS/BFS 실버 2 - DFS와 BFS  (0) 2023.03.13
[ Baekjoon ] [1049] 그리디 실버3 - 기타줄  (0) 2023.03.13
[ Baekjoon ] [2607] 실버 3 - 비슷한 단어  (1) 2023.03.12

+ Recent posts

티스토리툴바