백준 1743 JS 풀이

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

구하는 값

가장 큰 연결요소 구하기

핵심 아이디어

1. 입력받은값으로 이차원 배열을 만들기
2. 이중for문으로 각 위치 탐색하며 방문하지 않은 위치에서 DFS
3. DFS에서는 상하좌우로 DFS하며 DFS들 탈때마다 cnt++, return cnt
4. max값과 비교 cnt해서 가장큰값 출력

코드

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

const [n, m, k] = input[0].split(" ").map(Number);

const graph = Array.from({ length: n }, () => new Array(m).fill(false));
for (let i = 1; i <= k; i++) {
    const [r, c] = input[i].split(" ").map(Number);
    // console.log(r, c);
    graph[r - 1][c - 1] = true;
}

// console.log(graph);

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

function dfs(y, x, cnt) {
    graph[y][x] = false;

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

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

        if (graph[ny][nx]) {
            cnt = dfs(ny, nx, cnt + 1);
        }
    }
    return cnt;
}

let max = 0;
for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
        if (graph[i][j]) {
            max = Math.max(max, dfs(i, j, 1));
        }
    }
}

console.log(max);