접근

1~99까지

연속된 두 개의 수의 차이는 항상 일정하다. 비교할 대상이 하나(19) 또는 둘(1099)이기 때문에 이는 모두 한수이다.

100~ 210까지는 연속된 두 개의 수의 차이가 항상 일정한 수는 111, 123, 135, 147, 159, 210 로 총 6개이다.

1~99 수만큼 count ++

100부터 N까지

수를 한자리씩 split 한 후 연속된 수의 차이가 같은지 확인하면 되겠다.

for문으로 array의 length까지 index와 index+1 로 접근하는 방식

제출답안

const fs= require('fs')
// const input =fs.readFileSync('../text.txt').toString()
const input =fs.readFileSync('dev/stdin').toString()
const N = parseInt(input)
let count = 0;
//두자리 숫자라면
if(N < 100)
{
    //주어진 값만큼 한수 존재
    count = N
}
else
{
    //count를 99부터 시작 (두자리 숫자 모두 포함)
    count = 99
    for(let i = 100; i <=N;i++)
    {
        //각 자리수 array에 추가
        let arr = i.toString().split('').map(item=>+item)
        let temp
        //세자리 수일때
        if(arr.length === 3)
        {
            if((arr[0]-arr[1]) === (arr[1] - arr[2]))
            {
                count++
            }
        }
        else if(arr.length === 4)
        {
            if(((arr[0]- arr[1]) === (arr[1] - arr[2])) && ((arr[1]-arr[2]) === (arr[2] -arr[3])))
            {
                count++
            }
        }
    }

}
console.log(count)

접근 완전 탐색 문제로,0부터 10000까지 반복문을 돌리며 각 수가 셀프넘버가 됐을때 몇인지를 계산하고 배열에 push한다. 그 후 array에 포함되지 않는것들을 출력하면 되겠다.

let array = []
function selfNumber()
{
    let dn;
    for(let i = 0 ;i<10000;i++)
    {
        if(i<10)
        {
            dn = i*2
        }
        else if(i >= 10)
        {
            dn = i + i.toString().split('').map(item=>parseInt(item)).reduce((prev,cur)=>{
                cur = parseInt(prev) + cur
                return cur;
            },0)
        }
        array.push(dn)
    }

}

selfNumber()


for(let i = 1;i<=10000;i++)
{
    if(!array.includes(i))
    {
        console.log(i)
    }

}

dn = i + i.toString().split('').map(item=>parseInt(item)).reduce((prev,cur)=>{ cur = parseInt(prev) + cur return cur; },0)

숫자가 두자리 수 이상일때 수를 한 자리 씩 split으로 나눈 후에 reduce로 더해줘 값을 계산해주는 방식을 사용했다.

정리 모든 수를 다 완전탐색하는 방식을 사용하는게 핵심 숫자를 split하여 더하는 로직

완전탐색 방식은 복잡한 로직을 요한다기 보단 문제에서 보이는 그대로 계산해주는게 좋은 방식같아보인다.

해당 문제는 시간초과로 마무리 지은 문제입니다.

처음접근

간선이 주어지고 A가 B를 신뢰한다 이면 B를 해킹하면 A도 해킹할 수 있음, 하지만 A를 해킹하면 B를 해킹할수는 없다. 인접리스트를 생성할때 양쪽을 생성하는게 아닌 주어진 간선에 대한 인접 리스트만 생성하고 BFS로 풀면 되겠다 !

const fs =require('fs')
const input = fs.readFileSync('../text.txt').toString().trim().split('\n').map(item=>item.split(' ').map(item=>+item))
// const input = fs.readFileSync('dev/stdin').toString().trim().split('\n').map(item=>item.split(' ').map(item=>+item))
const [N,M] = input.shift()
const adjList = {}

//인접리스트 객체 key : value(배열) 로 초기화
for(let i = 1; i<=N;i++)
{
    adjList[i] = []
}

for(let i = 0; i<M;i++)
{
    let edge = input[i]
    adjList[edge[1]].push(edge[0]) //A가 B를 신뢰한다 -> B를 해킹하면 A를 해킹할 수 있다 -> B에 A가 연결된 구조
    // adjList[edge[0]] = edge[1] -> 기존의 인접리스트와는 다르게 주어진 간선만을 할당해줌
}


function bfs(startVertex)
{
    //방문했는지 확인하는 visited 객체
    let visited = {}
    //방문이 필요한 노드를 확인하는 queue 선언
    let needVisit = []

    //start vertex를 방문할 노드에 추가
    needVisit.push(startVertex)
    //start vertex를 방문했다고 추가
    visited[startVertex] = true
    //방문할 노드가 없을때까지
    while(needVisit.length)
    {
        //bfs이니까 맨 앞에있는것부터 너비 탐색 shift로 빼주기
        let currentVertex = needVisit.shift()
        //탐색하는 노드에 연결되어있는 인접리스트를 탐색
            adjList[currentVertex].forEach(vertex=>{
                //연결되어있는 인접리스트가 방문하지 않았다면
                if(visited[vertex] != true) {
                    //방문했다고 변경하고
                    visited[vertex] = true
                    //탐색할 노드에 추가
                    needVisit.push(vertex)
                }
            })
    }
    //startvertex에서부터 bfs로 탐색하면 몇개의 노드를 탐색하는지에 대한 개수를 반환
    return Object.keys(visited).length
}

let max = 0;
let result = []
//startvertex를 하나씩 모두 확인
for(let i = 1;i<=M;i++)
{
    //bfs로 탐색했을때 노드의 개수가 최대인지 확인
    if(max < bfs(i))
    {
        result = []
        max = bfs(i)
        result.push(i)
    }
    else if(max === bfs(i))
    {
        result.push(i)
    }
}
console.log(result.join(' '))

이렇게 코드를 작성했는데 1%에서 시간초과가 떴다.. 시간을 많이 잡아먹는 부분은 어떤 부분일까? 아무래도 입력값이 N은 10,000 이고 M은 100,000 이니까 배열을 push한다면 꽤 시간을 잡아먹겠다는 생각이 들었다. -> 시도했지만 실패..

인접 리스트를 만드는 부분이 문제가 아니었고 dfs로 구현을 해야한다는데 이 문제를 dfs로 풀어야 하는 명확한 이유를 찾을수가 없었다. 맞기 위해 이것저것 이유도 모르고 구현하는건 시간낭비일 것 같다는 생각이 들었기에 그냥 이 문제는 생각한 아이디어로 구현한 걸로 만족하고 넘어가기로 했다

정리 인접리스트를 구현할때 주어진 간선만 단방향으로 구현하기 노드의 개수가 몇번 탐색되었는지 구현하는 로직을 작성하기 시간초과로 오류가 나왔지만 다른 방법으로 구현해야 하는 명확한 이유를 납득하지 못해서 백준이니까.. 과감하게 스킵했다

문제를 풀진 못했지만 점점 구현하는 속도도 빠르고 비슷한 결의 풀이방향이 떠올라서 실력이 늘고있는듯한 느낌을 받았다

끝!

해당 문제는 숨바꼭질 1 문제에서 추가로 이동한 경로까지 구하는 문제이다. 문제를 풀기 전에 이전에 풀었던 숨바꼭질 1 문제를 다시 살펴보자.

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

const fs = require('fs')
// const input = fs.readFileSync('../text.txt').toString().split(' ').map(item=>+item)
const input = fs.readFileSync('dev/stdin').toString().split(' ').map(item=>+item)
const [N,K] = input
console.log(bfs(N,K))
function bfs(x,y)
{
    let visited = {}
    //현재 좌표와 depth를 선언
    let needVisit = [[N,0]]

    while(needVisit.length>0)
    {
        let [currentVertex,depth] = needVisit.shift()
        //수빈이가 동생의 좌표라면
        if(currentVertex === y)
        {
            //depth를 출력 , depth가 결국 시간이 됨
            return depth
            break;
        }
        let changedVertex;
        //+1,-1,곱하기 2의 경우의 수 중 좌표 조건을 만족하고 방문을 하지 않았다면 넣고 bfs를 돌리기
        [currentVertex-1,currentVertex+1,currentVertex*2].forEach(vertex=>{
            if(vertex >=0 && vertex <= 100000 && visited[vertex] != true)
            {
                    //그 노드를 방문했다고 초기화
                    visited[vertex] = true
                    //방문할 노드에 추가
                    needVisit.push([vertex,depth+1])
                }
            })


    }


}

처음접근

해당 문제에선 needVisit에서 수빈이가 동생의 좌표로 이동을 했다면(currentVertex === y) depth를 구하고 반복문을 종료하는 방식으로 문제를 풀어나갔다. 이번 문제에선 최단 경로까지 가는 모든 경우의 수를 계산하고, 이동한 좌표를 출력해보기로 생각을 했다.

생각한 변형 방식 : 경로를 탐색하는 route를 needVisit에 추가하자 (완전탐색방식)

const fs = require('fs')
const input = fs.readFileSync('../text.txt').toString().split(' ').map(item=>+item)
// const input = fs.readFileSync('dev/stdin').toString().split(' ').map(item=>+item)
const [N,K] = input
console.log(bfs(N,K).join('\n'))
function bfs(x,y)
{
    let visited = {}
    //현재 좌표와 depth를 선언
    let needVisit = [[N,[N],0]]

    while(needVisit.length>0)
    {
        let [currentVertex,route,depth] = needVisit.shift()
        //수빈이가 동생의 좌표라면
        if(currentVertex === y)
        {
            //depth를 출력 , depth가 결국 시간이 됨
            return [depth,route.join(' ')]
            break;
        }
        let changedVertex;
        //+1,-1,곱하기 2의 경우의 수 중 좌표 조건을 만족하고 방문을 하지 않았다면 넣고 bfs를 돌리기
        [currentVertex-1,currentVertex+1,currentVertex*2].forEach(vertex=>{
            if(vertex >=0 && vertex <= 100000 && visited[vertex] != true)
            {
                //그 노드를 방문했다고 초기화
                visited[vertex] = true
                //방문할 노드에 추가
                needVisit.push([vertex,[...route,vertex],depth+1])

            }
        })


    }


}

완전탐색으로 각 좌표에 대한 모든 경로를 needVisit.push([vertex,[...route,vertex],depth+1]) 를통해 구해줬다. 그 후에 수빈이가 동생의 좌표까지 가게 되면 ( if(currentVertex === y) ) depth와 추가해준 경로를 출력하여 답을 구했다. 4 5 4 8 16 17 답은 잘 나오지만.. 이렇게하니까 메모리 초과가 난다. needVisit에 너무 많은 경로를 저장하게 되어서 발생하는 문제같았고, 탐색하는 모든 경로를 저장하는게 아닌 정답의 경로만 출력하는 방식을 생각해야했다.

수정된 방식

경로를 일일이 다 넣어주지 말고, path라는 배열을 지정해준뒤 -1,+1, x2로 좌표를 이동할때마다 path에 해당 좌표에 도착하기전 어떤 좌표에서 왔는지를 넣어준다.

path에 이전에 탐색한 좌표를 넣게되면 각 좌표가 이전에 어떤 노드를 거쳤는지 확인할 수 있다. 이런 방식으로 path를 채우면 depth가 낮은 순서대로 path의 배열이 채워지게 되고, visited[vertex]≠true를 통해서 이전에 업데이트 된 path는 다시 업데이트 되지 않게되며 최단경로를 보장할 수 있게된다.

그 뒤에 도착지 (17)에서부터 시작해서 for(let i = 0;i<depth;i++) { array.push(path[array[i]]) } 연결된 노드들을 array 배열에 push하고, 시작노드부터 출력해야하기 때문에 reverse를 통해 출력해주었다.

정답코드

const fs = require('fs')
// const input = fs.readFileSync('../text.txt').toString().split(' ').map(item=>+item)
const input = fs.readFileSync('dev/stdin').toString().split(' ').map(item=>+item)
const [N,K] = input
const path = Array.from({ length: 100000 }, () => 0);
function bfs(x,y)
{
    let visited = {}
    //현재 좌표와 depth를 선언
    let needVisit = [[N,0]]

    while(needVisit.length>0)
    {
        let [currentVertex,depth] = needVisit.shift()
        //수빈이가 동생의 좌표라면
        if(currentVertex === y)
        {
            //depth를 출력 , depth가 결국 시간이 됨
            return depth
            break;
        }
        let changedVertex;
        //+1,-1,곱하기 2의 경우의 수 중 좌표 조건을 만족하고 방문을 하지 않았다면 넣고 bfs를 돌리기
        [currentVertex-1,currentVertex+1,currentVertex*2].forEach(vertex=>{
            if(vertex >=0 && vertex <= 100000 && visited[vertex] != true)
            {
                //그 노드를 방문했다고 초기화
                visited[vertex] = true
                //방문할 노드에 추가
                needVisit.push([vertex,depth+1])
                path[vertex] = currentVertex

            }
        })


    }


}

let depth = bfs(N,K)
let array = [K]

for(let i = 0;i<depth;i++)
{
    array.push(path[array[i]])
}
console.log(depth)
console.log(array.reverse().join(' '))

정리 최단경로의 정확한 이동 경로를 구할땐 탐색한 모든 노드들의 경로를 구하는 완전탐색 방법을 사용은 피하자(메모리 초과가 발생함) 이때 이전에 탐색한 좌표를 현재 탐색노드에 대응해주는 대응해주는 방식을 사용하면 어디서 오게 된 노드인지 알 수 있어 총 이동 경로를 구할 수 있다. index(현재탐색노드)에 이전 탐색노드를 대응해주는 방식

끝 !

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제입력 :5 17 예제 출력 : 4

처음 접근

0부터 100,000까지의 일차원 좌표에서 수빈이와 동생의 좌표가 주어진다. 수빈이는 x+1, x-1, 2x로 이동할 수 있고, 이때 가장 빠르게 찾는 시간을 출력한다. 가장 빠른 최단경로를 찾는 것이기 때문에 BFS를 사용하고, 이전에 이차원 좌표로 왼쪽, 위, 오른쪽, 아래로 이동하는 경우의 수를 통해 최단경로를 찾았다면 이번 문제는 x+1,x-1,2x를 통해 visited 방문 여부를 확인 후에 경로를 찾으면 될것같다.

걸린 부분

최단경로를 계산하는 부분에서 뭐가 정답이 될지 내가 어떻게알지..? x2를 먼저 해주어야하나? 라는 잘못된 생각을 잠깐 했었던 것 같다. 최적의 답을 구하는 것을 고민하는 그리디 알고리즘 구현이 아니라 모든경우의 수를 계산하며 답을 구하는 브루트포스의 접근 방식중 bfs, dfs를 사용하는 문제라는것을 인지하자.

count를 어떻게 계산할지에 대한 로직을 해결하느라 시간을 많이 잡아먹었다. 좌표에 해당하는 depth를 어떻게 계산해줄지 생각을 하는게 이번 문제의 핵심이었다고 생각한다.

function bfs(x,y)
{
    let visited = {}
    //현재 좌표와 depth를 선언
    let needVisit = [N]
    let count = 0
    while(needVisit.length>0)
    {
        console.log(count)
        let currentVertex = needVisit.shift()
        //수빈이가 동생의 좌표라면
        if(currentVertex === y)
        {
            //depth를 출력 , depth가 결국 시간이 됨
            return count;
            break;
        }
        let changedVertex;
        //+1,-1,곱하기 2의 경우의 수 중 좌표 조건을 만족하고 방문을 하지 않았다면 넣고 bfs를 돌리기
        [currentVertex-1,currentVertex+1,currentVertex*2].forEach(vertex=>{
            if(vertex >=0 && vertex <= 100000 && visited[vertex] != true)
            {
                //그 노드를 방문했다고 초기화
                visited[vertex] = true
                //방문할 노드에 추가
                needVisit.push(vertex)
            }
        })

        count++;


    }


}

이런식으로 depth를 계산하는 로직을 짜고 count를 출력해보았다.

결과 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

처음엔 이런식으로 while문을 벗어날때마다 count를 더해주려고 했지만 while문이 돌아간 횟수를 그대로 출력해줘서 다른 방식으로 선언을 해줘야겠다고 생각을했다.

일반적인 count ++로는 depth가 계산이 안되므로 needVisit에 [좌표,depth] 자체를 선언하면 반복문을 몇번 도는 것과는 상관없이 좌표에 대한 depth를 각각 계산할 수 있다.

제출한 정답 코드

const fs = require('fs')
// const input = fs.readFileSync('../text.txt').toString().split(' ').map(item=>+item)
const input = fs.readFileSync('dev/stdin').toString().split(' ').map(item=>+item)
const [N,K] = input
console.log(bfs(N,K))
function bfs(x,y)
{
    let visited = {}
    //현재 좌표와 depth를 선언
    let needVisit = [[N,0]]

    while(needVisit.length>0)
    {
        let [currentVertex,depth] = needVisit.shift()
        //수빈이가 동생의 좌표라면
        if(currentVertex === y)
        {
            //depth를 출력 , depth가 결국 시간이 됨
            return depth
            break;
        }
        let changedVertex;
        //+1,-1,곱하기 2의 경우의 수 중 좌표 조건을 만족하고 방문을 하지 않았다면 넣고 bfs를 돌리기
        [currentVertex-1,currentVertex+1,currentVertex*2].forEach(vertex=>{
            if(vertex >=0 && vertex <= 100000 && visited[vertex] != true)
            {
                    //그 노드를 방문했다고 초기화
                    visited[vertex] = true
                    //방문할 노드에 추가
                    needVisit.push([vertex,depth+1])
                }
            })


    }


}

이렇게 되면 최단경로를 계산할때까지의 좌표를 만나기전에 depth가 커지게 되어도, 결국 최단경로에 대응하는 depth를 계산할 수 있게된다.

정리 1.최단경로를 구하는 문제는 BFS를 사용할 생각을하자. 2.depth를 구하는 문제는 일반적인 count++로 계산하기가 복잡하고 어려워보인다. needVisit = [탐색하는 vertex] 이렇게만 선언하지 말고 needVisit = [탐색하는 vertex, depth] 로 선언해서 needVisit.push([vertex,depth+1])를 통해 depth를 구하는 방식을 기억하자. 3.그 외 다른 방식들은 일반적인 bfs 구현 후 이동할 수 있는 경우의 수를 찾으며 조건에 만족하는것들을 push하는 방식으로 다른 문제들과 비슷한 결을 보인다. 4. bfs, dfs문제인것을 인지하고 풀때 저 정답을 빠르게 찾는 로직을 어떻게 짜지? 라는 그리디알고리즘 접근 방식보단 브루트포스로 경우의 수를 다 계산해보고, 그중에 답을 찾는다. 라는 생각으로 문제를 푸는게 아직까지 겪은 bfs dfs문제들의 좋은 접근방식이었다.

끝!

처음 접근

배추가 심어져 있는 좌표가 주어지고 그 외에는 배추가 심어져 있지 않다. M-1, N-1 만큼의 이차원 배열을 생성해주고 값을 전부 0으로 초기화한다. input에서 주어진 좌표들만 1로 선언해준다 인접 좌표를 확인해주는 xval,yval(왼쪽,위,오른쪽,아래) 를 통해 bfs를 구현, 조건에 맞게 문제를 풀어가면 될것같다. 이전에 푼 문제들(미로탐색2178 ,단지 번호붙이기 2667)과 매우 유사해보였다.

내가 푼 풀이

const fs= require('fs')
// const input = fs.readFileSync('../text.txt').toString().trim().split('\n')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')
const T = input.shift()
let visited ;
for(let j = 0; j<T;j++)
{
    let result = 0;
    const [M,N,K] = input.shift().split(' ').map(item=>+item)
    //row M, column N만큼의 배추밭 선언, 0으로 초기화
    const field = Array.from({length : M}, ()=> Array(N).fill(0))
    //방문한 노드를 확인하는 이차원 배열 선언
    visited = Array.from({length : M}, ()=> Array(N).fill(false))
    //주어진 배추의 좌표를 1로 초기화
    for(let i =0; i<K;i++)
    {
        let line = input.shift().split(' ').map(item=>+item)
        field[line[0]][line[1]] = 1
    }

    for(let row = 0;row<M;row++)
    {
        for(let column = 0;column<N; column++)
        {
            //방문하지 않았고 배추가 심어져 있다면
            if(visited[row][column] === false && field[row][column] === 1)
            {
                //x좌표, y좌표, 테스트케이스의 field를 넘겨주어 bfs 탐색, 방문한 노드들을 true로 만들어준다
                bfs(row,column,field,M,N)
                //인접해있는 배추들이 몇군데 퍼져있는지 (그래프 순회가 몇번 사용이 됐는지)
                result++
            }
        }
    }

    console.log(result)

}


function bfs(x,y,field,M,N)
{
    //방문할 노드를 확인하는 queue생성
    let needVisit = []
    //파라미터로 받은 최초 x,y push
    needVisit.push([x,y])
    visited[x][y] = true
    //왼쪽, 위, 오른쪽, 아래 순서로 접근할 수 있는 좌표 생성
    const [xval,yval] = [[0,-1,0,1],[-1,0,1,0]]

    while(needVisit.length)
    {
        let currentVertex = needVisit.shift()
        //인접한 좌표값을 계산
        for(let i = 0; i<4;i++)
        {
            //탐색하는 좌표에서의 왼쪽, 위 , 오른쪽, 아래의 좌표 하나씩 탐색
            let [nx,ny] = [xval[i]+currentVertex[0],yval[i]+currentVertex[1]]

            //좌표가 범위를 넘어가지 않을때
            if(nx >=0 && ny >=0 && nx<M && ny <N)
            {
                //(왼쪽,위,오른쪽,아래)탐색하는 노드가 이전에 방문한 적이 없고 배추가 심어져 있을때
                if(visited[nx][ny] === false && field[nx][ny] === 1)
                {
                    //해당 노드를 방문할 노드에 추가
                    needVisit.push([nx,ny])
                    //해당 노드를 방문했다고 추가
                    visited[nx][ny] =true
                }

            }

        }
    }
}

이것도 이전에 푼 문제와 비슷하게 xval과 yval의 반복문(왼쪽,위,오른쪽,아래)을 통해 인접한 좌표를 확인하는 로직만 신경쓰고 bfs를 구현하면 큰 어려움 없이 풀렸다. 주어지는 입력값의 스타일이 조금 달랐지만 이차원 배열을 먼저 선언한 뒤에 입력에서 주어진 좌표에 1을 대입해주면 결국엔 인접좌표 계산을 통해 bfs로 탐색하는 이전의 문제들과 같은 느낌이었다. 1.인접 좌표를 선언한뒤 2.인접 좌표들에 대한 반복문을 돌리며 3. 좌표 범위가 넘어가지 않는 if문 4. 탐색하는 노드가 이전에 방문한적이 없는지, 그 노드가 탐색 대상인지 (1인지) 확인

풀다보니 이런 비슷한 유형이 많은것같다.

끝!

문제 접한 후 처음 접근

좌표내에 연결된 단지 모임들의 개수를 구하는 문제이다.

N이 최대 25이므로 25x25의 좌표들을 반복문을 돌려도 무방해보였다.

해당 좌표를 방문하지 않았다면 bfs를 통해 연결된 단지의 노드들을 방문했다고 처리하고, 방문한 노드만큼 +1을 visited에 추가해주어 단지모임의 총 개수를 구한다.

bfs 순회가 종료되면 visited를 0으로 초기화하고 다시 반복문을 돌며 visited가 0이 아니라면 bfs, 0이라면 continue를 통해 답을 구하면 될것같다.

구현

const fs = require('fs')
// const input =fs.readFileSync('../text.txt').toString().trim().split('\n')
const input =fs.readFileSync('dev/stdin').toString().trim().split('\n')
const n = Number(input.shift())
const apart = []
//아파트 이차원 배열 선언
for(let i = 0; i<input.length;i++)
{
    apart.push(input[i].split('').map(item=>+item))
}

//방문한 노드와 단지모임의 총 개수를 계산해주는 변수,최초 0으로 초기화
let visited = Array.from({length : n}, ()=>Array(n).fill(0))

//인접한 좌표를 계산해주는 변수([xval,yval] 왼쪽, 위, 오른쪽, 아래 순서)
const [xval,yval] = [[-1,0,1,0],[0,1,0,-1]]
let groupCount = 0
let result = []
let apartNumber;
for(let i = 0; i< n;i++)
{
    for(let j=0;j<n;j++)
    {
        //방문하지 않았고 아파트가 존재한다면
        if(visited[i][j] ===0 && apart[i][j] === 1)
        {
            //좌표마다 bfs 순회
            apartNumber = bfs(i,j)
            result.push(apartNumber)
            groupCount++
        }
    }
}

bfs(0,1)

function bfs(x,y)
{
    const needVisit = []
    needVisit.push([x,y])
    visited[x][y] = 1
    let count = 1;

            //bfs 순회
    while(needVisit.length>0)
    {
        const currentApart = needVisit.shift()

        for(let i = 0; i<4;i++)
        {
            //시작 노드에서 인접 노드 (왼쪽, 위, 오른쪽, 아래)계산
            const [nx,ny] = [currentApart[0]+xval[i],currentApart[1]+yval[i]]

            //인접한 x,y의 좌표가 0보다 크거나 같고 n보다 작을때 (존재하는 좌표 범위 내에 있을때)
            if(nx >=0 && ny>=0 && nx<n && ny<n)
            {
                //아파트가 있을떄 (값이 1일때), 방문하지 않은 노드일때
                if(apart[nx][ny] === 1 && visited[nx][ny] === 0 )
                {
                    count++
                    visited[nx][ny] = visited[nx][ny]+ count
                    needVisit.push([nx,ny])
                }
            }
        }

    }
    return count
}

console.log(groupCount)
console.log(result.sort((a,b)=>{return a-b}).join('\n'))

코드 풀이

입력과 변수 받기

const fs = require('fs')
// const input =fs.readFileSync('../text.txt').toString().trim().split('\n')
const input =fs.readFileSync('dev/stdin').toString().trim().split('\n')
const n = Number(input.shift())
const apart = []
//아파트 이차원 배열 선언
for(let i = 0; i<input.length;i++)
{
    apart.push(input[i].split('').map(item=>+item))
}

input을 split 함수와 map함수를 통해 apart 일차원 배열에 일차원 배열을 push하는 방식으로 apart 이차원 배열을 만들어줬다.

//방문한 노드와 단지모임의 총 개수를 계산해주는 변수,최초 0으로 초기화
let visited = Array.from({length : n}, ()=>Array(n).fill(0))

방문할 노드를 확인하는 이차원 배열을 모두 0으로 초기화 해줬다. 알면 굉장히 유용한 이차원 배열 선언 방법!

//인접한 좌표를 계산해주는 변수([xval,yval] 왼쪽, 위, 오른쪽, 아래 순서)
const [xval,yval] = [[-1,0,1,0],[0,1,0,-1]]
let groupCount = 0
let result = []
let apartNumber;

이전에 풀었던 미로탐색 문제에서 사용한 방식이다. 인접한 좌표를 계산할 수 있는 x,y좌표를 미리 선언해주고 반복문을 사용해주면서 가독성을 키웠다.

그래프 순회 함수 (BFS)

function bfs(x,y)
{
    const needVisit = []
    needVisit.push([x,y])
    visited[x][y] = 1
    let count = 1;

            //bfs 순회
    while(needVisit.length>0)
    {
        const currentApart = needVisit.shift()

        for(let i = 0; i<4;i++)
        {
            //시작 노드에서 인접 노드 (왼쪽, 위, 오른쪽, 아래)계산
            const [nx,ny] = [currentApart[0]+xval[i],currentApart[1]+yval[i]]

            //인접한 x,y의 좌표가 0보다 크거나 같고 n보다 작을때 (존재하는 좌표 범위 내에 있을때)
            if(nx >=0 && ny>=0 && nx<n && ny<n)
            {
                //아파트가 있을떄 (값이 1일때), 방문하지 않은 노드일때
                if(apart[nx][ny] === 1 && visited[nx][ny] === 0 )
                {
                    count++
                    visited[nx][ny] = visited[nx][ny]+ count
                    needVisit.push([nx,ny])
                }
            }
        }

    }
    return count
}

일반적인 BFS 코드에 인접한 좌표를 계산하는 로직과 조건문, 그리고 결과값을 계산하는 로직을 추가한다.

xval과 yval의 반복문(왼쪽,위,오른쪽,아래)을 통해 인접한 좌표를 확인 각각의 인접한 좌표마다

1. 좌표 범위 내에 있는지 확인하는 if문
2. 그 좌표에 아파트가 있는지 확인하고, 이전에 방문하지 않은 노드인지 확인하는 if문

의 조건을 만족했을때 인접한 노드들을 통해 bfs가 얼마나 순회하는지 확인하는 count를 늘려주면서 인접한 아파트 모임내의 아파트 개수를 구해주었다. 그후 count를 반환.

결과값 출력

for(let i = 0; i< n;i++)
{
    for(let j=0;j<n;j++)
    {
        //방문하지 않았고 아파트가 존재한다면
        if(visited[i][j] ===0 && apart[i][j] === 1)
        {
            //좌표마다 bfs 순회
            apartNumber = bfs(i,j)
            result.push(apartNumber)
            groupCount++
        }
    }
}

bfs(0,1)
console.log(groupCount)
console.log(result.sort((a,b)=>{return a-b}).join('\n'))

n의 크기가 최대 25이기 때문에 모든 좌표를 확인해봐도 무방하다고 판단을 했고, 어쩌피 bfs로 순회한 좌표는 if문에 걸리지 않기 때문에 시간 복잡도가 크지 않을것이다.

반복문에 걸린 if문을 groupCount++을 해주어 아파트 모임의 개수를 구해주고

인접한 아파트 모임내의 아파트 개수를 반환한 결과를 배열에 넣어 오름차순으로 정렬하여 값을 출력하였다.

걸린부분

 if(nx >=0 && ny>=0 && nx<n && ny<n)
            {
                //아파트가 있을떄 (값이 1일때), 방문하지 않은 노드일때
                if(apart[nx][ny] === 1 && visited[nx][ny] === 0 )
                {
                    count++
                    visited[nx][ny] = visited[nx][ny]+ count
                    needVisit.push([nx,ny])
                }
            }

이 부분에서 visited[nx][ny] === 0 (이전에 방문하지 않은 노드인지 확인) 를 추가해주지 않아 시간을 많이 잡아먹었다. 이 부분을 다음부터 신경써야겠다. 추가적으로 visited 배열을 굳이 count로 하지 않고 boolean으로 나타내도 좋을듯 !

정리 1.이차원 배열 선언하는 방법 기억하기 let visited = Array.from({length : n}, ()=>Array(n).fill(0)) 2.const [xval,yval] = [[-1,0,1,0],[0,1,0,-1]] 룰 활용한 인접 좌표 확인 3.조건문을 달때 방문하지 않은 노드인지 확인하는 부분 신경쓰기

끝!

연결되어있는 컴퓨터들의 정보가 주어지고 1번 컴퓨터가 바이러스에 걸릴때 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 문제이다.

입력을 인접리스트로 바꿔준뒤에 1번에서부터 그래프 알고리즘을 사용하여 연결된 컴퓨터의 총 개수를 구하면 된다.

연결되어있는 컴퓨터의 개수만 구하면 되는것이기 때문에 DFS와 BFS중 어떤걸 사용해도 큰 지장이 없을것같았다.

일반적인 BFS 알고리즘을 구현하고 , 몇개의 노드들을 탐색했는지를 저장하는 cnt 변수를 +1 해주면 될것같다.

const fs = require('fs')
// const input = fs.readFileSync('../text.txt').toString().trim().split('\n')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')
const n = Number(input.shift()) //컴퓨터의 개수
const m = Number(input.shift()) //간선의 개수
let adjList = {}
for(let i = 1;i<=n;i++)
{
    adjList[i] = []
}

// visited를 false로 초기화 시키는 함수 구현
function setVisited(){
    let visited = {}
    for(let i = 1;i<=n;i++)
    {
        visited[i] = false
    }
    return visited
}

//인접리스트 구현
for(let i = 0;i<m;i++)
{
    //각 line에 해당하는 간선
    let edge = input[i].split(' ').map(item=>+item)
    adjList[edge[0]].push(edge[1])
    adjList[edge[1]].push(edge[0])
}

// console.log(adjList)

function bfs(startVertex)
{
    //방문한 노드를 저장하는 객체 (초기값 false)
    let visited = setVisited()
    //방문할 노드를 저장하는 변수
    let needVisit = []
    needVisit.push(startVertex)
    visited[startVertex] = true
    //몇개의 노드를 방문하는지 확인하는 변수
    let cnt = 0
    //방문할 노드가 없을때까지 반복
    while(needVisit.length)
    {
        //방문하는 노드 계산
        cnt++;
        let currentVertex = needVisit.shift()
        //연결된 노드들 각각에 대한 탐색 ex) 1일때 -> 2,5 확인
        adjList[currentVertex].forEach(item=> {
            //탐색하는 노드가 방문을 하지 않았을때
            if (visited[item] === false)
            {
                //방문했다고 변경
                visited[item] = true
                //방문할 노드에 push
                needVisit.push(item)
            }
        })
    }

    //1번 컴퓨터를 제외하고 계산
    return cnt-1
}


console.log(bfs(1))

큰 어려움없이 문제가 풀렸다. 일반적인 BFS나 DFS를 구현하고 cnt++ 해주는 로직만 추가하면 문제가 쉽게 풀린다.

정리

1. 인접 리스트 만들기
2. 기본적인 BFS를 먼저 구현을 하고 그 뒤 문제가 원하는 조건(cnt 변수)을 뒤에 추가하는 식의 방식으로 문제를 풀어 나가도 좋을듯 !

끝!

미로탐색 문제이다.

처음 접근 :

BFS와 DFS의 개념상 다음길에 연결되어있는 그 다음길을 이어서 쭉 탐색하는건 깊이 탐색이 적절하다고 생각했었기 때문에 맨 처음 DFS로 접근을 했다. 하지만 DFS는 가장 빠른 길을 구하는 적절한 탐색법이 아니다.

최단 경로를 탐색하는 문제는 BFS가 적절하다는 것을 알아두자 !

이전 코드와 정답 코드와 비교하며 공부해보자.

1. 이차원 배열 할당

let maze = new Array(row)
//미로의 각 노드를 방문했는지 확인하는 visited
let visited = new Array(row)
for(let i = 0; i< maze.length;i++)
{
    maze[i] = new Array(column)
    visited[i] = new Array(row)
    maze[i] = [...input.shift().split('').map(item=>+item)]
}


//visited 배열 false로 초기화 : 나중에 fill하는 쉬운 방법 찾아보기
for(let i = 0; i<row;i++)
{
    for(let j = 0;j<column;j++)
    {
        visited[i][j] = false
    }
}

new Array(row)로 할당한 뒤에 for문으로 한번더 new Array(column)으로 하는 방식은 좋지 않다.

const maze = []
for(let i = 0; i<input.length;i++)
{
maze.push(input.split('').map(item=>+item)
}

이렇게 maze 일차원 배열만 할당한뒤에 split을 사용해서 push 하는 방식으로 구현하자.

for(let i = 0; i<row;i++)
{
    for(let j = 0;j<column;j++)
    {
        visited[i][j] = false
    }
}

이렇게 이증 반복문을 사용해서 visitied 의 이차원 배열을 선언했는데 fill함수를 사용하는 방법을 익히자

let visited = Array.from({length : N}, () => Array(M).fill(0))

2.문제 풀이

✅ Count를 계산하는 방식

문제를 풀때 나는 처음에는 dfs를 활용해서 재귀를 통해 재귀의 횟수만큼 count+를 해줘서 총 거리를 구하려고했다. 하지만 visited를 boolean으로 놓지않고, 전부 0으로 선언뒤에 +1만큼 증가시키는 방식을 사용하면 더 효율적으로 풀 수 있다.

그리고 DFS로 풀었을때 count가 다르게 나왔는데, 잘못된 경로로 이동한다면 백트래킹을 해주는 코드를 작성해주어야한다.

✅ 이동할 좌표 계산

처음 구현했을때는 왼쪽은 필요없다고 생각하고 아래, 오른쪽, 위만 생각했고 일일이 좌표에다가 -1, +1을 해주는 아래와 같은 코드를 작성했다.

if(n <row-1)
        {
            if(visited[n+1][m] != true && maze[n+1][m] === 1 )
            {
                cnt = dfs(n+1,m,cnt+1)
            }
        }

        if(m < column-1)
        {
            //오른쪽
            if(visited[n][m+1]!=true && maze[n][m+1] === 1 )
            {
                cnt =dfs(n,m+1,cnt+1)
            }
        }

        if(n>0)
        {
            if(visited[n-1][m]!=true && maze[n-1][m] === 1 )
            {
                cnt = dfs(n-1,m,cnt+1)
            }
        }

이걸 단순하게 풀기 위해서 dx, dy좌표를 선언하고 반복문을 돌리는 방식을 채택하자. 그리고 특정한 경우를 고려하지 않는 방식(왼쪽선언 x) 보단 모든 경우를 고려하는 코드를 작성하는게 좋은 습관이다.

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


for(let i =0;i<4;i++)
        {
            const [nx,ny] = [x+dx[i],y+dy[i]]
            if(nx >= 0 && ny >= 0 && nx < N && ny <M ) //좌표 범위 내에 있을때
            {
                if(visited[nx][ny]===0 && maze[nx][ny] === 1) //방문하지 않았고 길이 있다면
                {
                    visited[nx][ny] = visited[x][y] +1
                    queue.push([nx,ny])
                }

            }

✅ dfs(재귀)로 풀지 않으니 queue를 사용, 키 값은 좌표로 설정

다시 작성한 정답풀이

const fs = require("fs")
// const input = fs.readFileSync('../text.txt').toString().trim().split('\n')
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n')
const [N,M] = input.shift().split(' ').map(item=>+item)
const maze = []
for(let i = 0 ; i< input.length;i++)
{
    maze.push(input[i].split('').map(item=>+item))
}
const visited = Array.from({length: N}, ()=>Array(M).fill(0))
visited[0][0] = 1

function bfs(row,col)
{
    //왼쪽 위 오른쪽 아래 순서대로 더할 배열 선언
    const xval = [-1,0,1,0]
    const yval = [0,1,0,-1]
    //방문할 노드 담기
    const needVisit = []
    needVisit.push([row,col])
    while(needVisit.length)
    {
        const [x,y] = needVisit.shift()
        for(let i =0;i<4;i++)
        {
            //각 방향의 좌표
            const [nx,ny] = [x+xval[i],y+yval[i]]

            //좌표가 범위안이어야함
            if(nx>=0 && ny >=0 && nx <N && ny <M)
            {
                //방문할 노드가 길이 있다면(maze가 1이라면), 방문을 안했던 노드라면(visited가 0이라면)
                if(maze[nx][ny] === 1 && visited[nx][ny]=== 0)
                {
                    //현재 노드에서 +1
                    visited[nx][ny] = visited[x][y] +1
                    //for문에서 돌린 4가지 좌표중 조건을 만족하는게 있다면 다 needVisit 배열에 넣어서 bfs를 진행하기
                    needVisit.push([nx,ny])
                }
            }
        }

    }
    return visited[N-1][M-1]
}

console.log(bfs(0,0))

문제에서 얻어갈 개념

1. 이차원 배열을 선언하는 방식
2. 최단경로를 구하는 문제는 BFS를 사용하기
3. count를 계산하는 방식을 visited 배열과 연관지어서 생각하기