백준 - DFS/BFS

hj·2021년 8월 21일
0

백준 유형풀이

목록 보기
1/2
post-thumbnail

브론즈/실버 난이도

아기 상어

코드를 입력하세요

바이러스

인접 리스트/ 인접 행렬을 이용해 그래프 연결 상태를 저장한다.
DFS를 이용해 해당 노드(컴퓨터)와 연결된 노드(컴퓨터)들을 찾는다.

  • 방문한 노드인 경우 pass
  • 방문하지 않은 노드인 경우
    - 방문하지 않은 노드와 인접한 노드들을 스택에 쌓는다.
  • 이 과정을 반복한다.

인접 리스트

객체 안에 키 값으로 배열 넣기

let obj = {};

for (let key = 1; key < 5; key++) {
    obj[key] = [];
}

obj[key].push(value);

풀이

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

const n = Number(input[0]);
const m = Number(input[1]);

let adjList = {};
for (let i = 1; i <= n; i++) {
    adjList[i] = [];
}

for (let i = 2; i <= m + 1; i++) {
    let [v, w] = input[i].split(' ').map(Number);

    adjList[v].push(w);
    adjList[w].push(v);
}

function DFS(start) {
    let stack = [start];
    let dis = new Array(n + 1).fill(0);
    let cnt = 0;

    while (stack.length > 0) {
        let v = stack.pop();
        
        if (dis[v] === 0) {
            dis[v] = 1;
            cnt++;

            for (let i = 0; i < adjList[v].length; i++) {
                stack.push(adjList[v][i]);
            }
        }
    }
    console.log(cnt - 1);
}

DFS(1);

인접 행렬

풀이

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

const n = Number(input[0]);
const m = Number(input[1]);

let adjList = {};
let adjArr = [];
for (let i = 1; i <= n; i++) {
    adjArr.push(new Array(n).fill(0));
}

for (let i = 2; i <= m + 1; i++) {
    let [v, w] = input[i].split(' ').map(Number);

    adjArr[v - 1][w - 1] = 1;
    adjArr[w - 1][v - 1] = 1;
}

function DFS(start) {
    let stack = [start - 1]; // index
    let dis = new Array(n).fill(0);
    let cnt = 0;

    while (stack.length > 0) {
        let v = stack.pop();

        if (dis[v] === 0) { // 방문하지 않은 노드라면
            dis[v] = 1;
            cnt++;

            for (let i = 0; i < n; i++) {
                if (adjArr[v][i] === 1) {
                    stack.push(i);
                }
            }
        }
    }

    console.log(cnt - 1);
}

DFS(1);

경로 찾기

특정 노드와 연결된 노드들을 찾는 문제이다.

DFS를 이용해서 각 노드와 연결된 노드들을 찾았다.

플로이드 워샬?로 짜야하는 문제임.

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

const n = Number(input[0]);
const adjArr = [];
let res = [];
for (let i = 1; i <= n; i++) {
    res.push(new Array(n).fill(0));
    adjArr.push(input[i].split(' ').map(Number));
}

function BFS(start) {
    let stack = [start];
    let dis = new Array(n).fill(0);

    while (stack.length > 0) {
        let v = stack.pop();

        if (dis[v] === 0) {
            dis[v] = 1;

            for (let i = 0; i < n; i++) {
                if (adjArr[v][i] === 1) {
                    stack.push(i);
                    res[start][i] = 1;
                }
            }
        }
    }
}


for (let i = 0; i < n; i++) {
    BFS(i);
    console.log(res[i].join(' '));
}

효율적인 해킹 - 메모리 초과

메모리 초과남.
인접 리스트, DFS를 이용해서 품.

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

let [n, m] = input[0].split(' ').map(Number);
let adjList = {};
for (let i = 0; i < n; i++) {
    adjList[i] = [];
}

for (let i = 1; i <= m; i++) {
    const [v, w] = input[i].split(' ').map(Number);
    adjList[w - 1].push(v - 1);
}

function DFS(start) {
    let stack = [start];
    let dis = new Array(n).fill(0);
    let cnt = 0;

    while (stack.length > 0) {
        let v = stack.pop();

        if (dis[v] === 0) {
            dis[v] = 1;
            cnt++;

            for (let i = 0; i < adjList[v].length; i++) {
                if (dis[adjList[v][i]] === 0) stack.push(adjList[v][i]);
            }
        }
    }
    return cnt - 1;
}

let arr = [];
for (let i = 0; i < n; i++) {
    arr.push(DFS(i));
}
const max = Math.max.apply(null, arr);
let answer = [];
arr.map((item, i) => {
    if (item === max) answer.push(i + 1);
});
console.log(answer.sort((a, b) => a - b).join(' '));

토마토

shift 연산을 하면 시간초과가 나서 인덱싱으로 처리해줌.

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

const [m, n] = input[0].split(' ').map(Number);
const tomatos = [];
for (let i = 1; i <= n; i++) {
    tomatos.push(input[i].split(' ').map(Number));
}

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function findNoTom(arr) {
    for (let i = 0; i < n; i++) {
        for (let k = 0; k < m; k++) {
            if (arr[i][k] === 0) return true;
        }
    }

    return false;
}

function BFS(queue) {
    let day = 0;

    let idx = 0;
    while (queue.length > idx) {
        let [a, b, cnt] = queue[idx];
        day = cnt;

        for (let i = 0; i < 4; i++) {
            const nx = a + dx[i];
            const ny = b + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            if (tomatos[nx][ny] === 0) {
                tomatos[nx][ny] = 1;
                queue.push([nx, ny, cnt + 1]);
            }
        }
        idx++;
    }
    // 0이 있는 경우를 찾아야 함.
    if (findNoTom(tomatos)) console.log(-1);
    else console.log(day);
}

let q = [];
for (let i = 0; i < n; i++) { // row
    for (let k = 0; k < m; k++) { // col
        if (tomatos[i][k] === 1) q.push([i, k, 0]);
    }
}

if (q.length === 0) {
    if (tomatos[0][0] === 1) console.log(0);
    else console.log(-1);
}
else BFS(q);

미로 탐색

처음에 방문 여부를 체크 안해줘서 시간초과남.

  • 미로 정보가 담겨있는 기존 배열을 변경해서 방문 여부 체크를 해줌.
const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const miro = input.slice(1).map(row => row.split('').map(Number));

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];

function BFS() {
    let q = [[0, 0, 0]];

    let idx = 0;
    while (q.length > idx) {
        let [a, b, cnt] = q[idx];

        if ((a === n - 1) && (b === m - 1)) return console.log(cnt + 1);

        for (let i = 0; i < 4; i++) {
            const nx = a + dx[i];
            const ny = b + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            else if (miro[nx][ny] === 1) {
                q.push([nx, ny, cnt + 1]);
                miro[nx][ny] = miro[a][b] + 1;
            }
        }
        idx++;
    }
}

BFS();

안전영역

현재 비교하려는 빗물의 높이보다 높은 경우 배열에 저장.
저장한 배열로 BFS

const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
let n = Number(input[0]);
let heights = input.splice(1).map(row => row.split(' ').map(Number));

let max = -Infinity;
heights.map(arr => arr.map(item => {
    if (item > max) max = item;
}));

function findHigh(h) {
    let tmp = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (heights[i][j] > h) tmp.push([i, j]);
        }
    }
    return tmp;
}

const dx = [-1, 1, 0, 0];
const dy = [0, 0, -1, 1];
function BFS(a, b, height, visited) {
    let q = [[a, b]];
    visited[a][b] = 1;

    let idx = 0;
    while (q.length > idx) {
        let [x, y] = q[idx];

        for (let i = 0; i < 4; i++) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

            if (heights[nx][ny] > height && visited[nx][ny] === 0) {
                q.push([nx, ny]);
                visited[nx][ny] = 1;
            }
        }
        idx++;
    }
    return visited;
}

let maxAreaCnt = 0;
for (let i = 0; i < max; i++) {
    let arr = findHigh(i);
    let visited = [];
    for (let i = 0; i < n; i++) {
        visited.push(new Array(n).fill(0));
    }
    let cnt = 0;

    arr.map(item => {
        const [a, b] = item;
        if (visited[a][b] === 0) {
            visited = BFS(a, b, i, visited);
            cnt++;
        }
    });
    if (maxAreaCnt < cnt) maxAreaCnt = cnt;
}

console.log(maxAreaCnt);
  • 빠른 풀이(다른 사람)
const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const n = +input[0];
const originMap = input.slice(1).map((e) => e.split(" ").map((i) => +i));
let rain = 0;
let maxRain = 0;
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (maxRain < originMap[i][j]) maxRain = originMap[i][j];
  }
}
let map = [];
let ans = -1;

while (rain < maxRain) {
  map = originMap.slice().map((e) => e.slice());
  sink();
  let cnt = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(i, j)) cnt++;
    }
  }
  if (cnt > ans) ans = cnt;
  rain++;
}

console.log(ans);

function sink() {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (map[i][j] <= rain) map[i][j] = -1;
    }
  }
}

function dfs(x, y) {
  if (x < 0 || y < 0 || x >= n || y >= n) return false;
  if (map[x][y] !== -1) {
    map[x][y] = -1;
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
    return true;
  }
  return false;
}

촌수계산

인접 리스트로 노드 간의 연결 상태를 나타냈고, BFS를 이용해서 촌수를 계산했다.

const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
let n = Number(input[0]);
let [p1, p2] = input[1].split(' ').map(Number);
let m = Number(input[2]);
let arr = [];

let adjList = {};
for (let key = 1; key <= n; key++) {
    adjList[key] = [];
}

for (let i = 3; i <= m + 2; i++) {
    const [x, y] = input[i].split(' ').map(Number);
    adjList[y].push(x);
    adjList[x].push(y);
}

function BFS(p1, p2) {
    let q = [[p1, 0]];
    let dis = [];
    for (let i = 0; i < n; i++) dis.push(0);

    while (q.length > 0) {
        let [cur, cnt] = q.shift();
        if (cur === p2) return console.log(cnt);

        if (dis[cur] === 0) {
            dis[cur] = 1;

            for (let i = 0; i < adjList[cur].length; i++)
                q.push([adjList[cur][i], cnt + 1]);
        }
    }
    return console.log(-1);
}

BFS(p1, p2);

맥주 마시면서 걸어가기

처음에는 왜 BFS/DFS 문제인지 감이 잡히지 않았다.

BFS로 풀었다. 우선 서로 1000m 이내에 있는 노드끼리 연결시켜주었다. (연결 상태는 인접 리스트로 나타냄.)

시작 노드에서 마지막 노드까지 갈 수 있다면 happy 갈 수 없다면 sad를 출력

const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const t = Number(input.splice(0, 1));
for (let i = 0; i < t; i++) {
    const n = Number(input[0]);
    const queue = [];

    for (let k = 1; k <= n + 2; k++)
        queue.push(input[k].split(' ').map(Number));

    BFS(makeGraph(queue), n);

    input.splice(0, n + 3);
}

function makeGraph(q) {
    let graph = {};
    for (let i = 0; i < q.length; i++) graph[i] = [];

    for (let i = 0; i < q.length - 1; i++) {
        for (let j = i + 1; j < q.length; j++) {
            const dist =
                Math.abs(q[i][0] - q[j][0]) + Math.abs(q[i][1] - q[j][1]);

            if (dist <= 1000) {
                graph[i].push(j);
                graph[j].push(i);
            }
        }
    }

    return graph;
}

function BFS(adjList, n) {
    let q = [0];
    let visited = [];
    for (let i = 0; i < n + 2; i++) visited.push(0);

    while (q.length > 0) {
        let cur = q.shift();

        if (cur === n + 1) return console.log('happy');

        if (visited[cur] === 0) {
            visited[cur] = 1;

            for (let i = 0; i < adjList[cur].length; i++)
                q.push(adjList[cur][i]);
        }
    }
    return console.log('sad');
}
  • 다른 사람 풀이
    1000m 이내에 드는 노드들을 따로 그래프로 나타내지 않고, 매 순간 계산.
const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const MAX_DIST = 50 * 20;

function calcDist(p1, p2) {
    return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}

function dfs(from, to, ps, visited) {
    if (from === to) return true;

    return ps.some((next, i) => {
        // 조건을 만족하는 값이 발견되면 그 즉시 순회 중단.
        if (!visited[i] && calcDist(ps[from], next) <= MAX_DIST) {
            visited[i] = true;
            const res = dfs(i, to, ps, visited);
            if (res) return true;
        }

        return false;
    });
}

function solution(n, ps) {
    const visited = Array(n + 2).fill(false);
    const res = dfs(0, n + 1, ps, visited);

    return res ? 'happy' : 'sad';
}

const t = +input[0];
const ans = Array(t);

for (let i = 0, j = 1; i < t; i += 1) {
    const n = +input[j];
    const ps = input
        .slice(j + 1, j + 3 + n)
        .map((line) => line.split(' ').map(Number));

    ans[i] = solution(n, ps);
    j += 3 + n;
}

console.log(ans.join('\n'));

결혼식

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

let adjList = {};
let dis = [0];
for (let i = 1; i <= n; i++) {
    adjList[i] = [];
    dis.push(0);
}

for (let i = 2; i < m + 2; i++) {
    const [a, b] = input[i].split(' ').map(Number);

    adjList[a].push(b);
    adjList[b].push(a);
}

BFS(1, 2, dis);

function BFS(start, depth, dis) {
    let q = [[start, 0]];

    while (q.length > 0) {
        const [cur, cnt] = q.shift();
        if (cnt > depth) continue;

        if (dis[cur] === 0) {
            dis[cur] = 1;
            for (let i = 0; i < adjList[cur].length; i++) {
                q.push([adjList[cur][i], cnt + 1]);
            }
        }
    }

    return console.log(dis.filter((item) => item === 1).length - 1);
}

단지번호붙이기

  • BFS
    단지의 크기가 1인 경우 cnt가 증가하지 않고 0으로 끝나기 때문에 cnt를 1로 바꿔줘야한다.
const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const n = Number(input.shift());
for (let i = 0; i < n; i++) input[i] = input[i].split('').map(Number);

let res = [];
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        if (input[i][j] === 1) {
            res.push(BFS(i, j));
        }
    }
}

console.log(`${res.length}\n${res.sort((a, b) => a - b).join('\n')}`);

function BFS(i, j) {
    let q = [[i, j]];

    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    let cnt = 0;
    while (q.length > 0) {
        const [a, b] = q.shift();

        for (let i = 0; i < 4; i++) {
            const nx = a + dx[i];
            const ny = b + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

            if (input[nx][ny] === 1) {
                cnt++;
                input[nx][ny] = 0;
                q.push([nx, ny]);
            }
        }
    }
    return cnt === 0 ? 1 : cnt;
}
  • DFS
const input = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const n = Number(input.shift());
for (let i = 0; i < n; i++) input[i] = input[i].split('').map(Number);

let res = [];
let aptCnt = 0;
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        aptCnt = 0;
        if (DFS(i, j)) {
            res.push(aptCnt);
        }
    }
}

console.log(`${res.length}\n${res.sort((a, b) => a - b).join('\n')}`);

function DFS(x, y) {
    if (x < 0 || x >= n || y < 0 || y >= n) return false;
    if (input[x][y] === 0) return false;
    if (input[x][y] === 1) {
        input[x][y] = 0;
        aptCnt++;
        DFS(x - 1, y);
        DFS(x + 1, y);
        DFS(x, y - 1);
        DFS(x, y + 1);
        return true;
    }
    return false;
}

https://www.acmicpc.net/problem/1260
https://www.acmicpc.net/problem/10451
https://www.acmicpc.net/problem/7569

골드 난이도

reference

https://mangkyu.tistory.com/181

profile
hj

0개의 댓글