[백준 2178 javascript] 미로탐색 2178

레슬코딩·2023년 8월 12일

Javascript 코테준비

목록 보기

1/9

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

미로탐색 문제이다.

처음 접근 :

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))