Portfolio

🔎 문제

🧩 구현과정 및 코드

개인 토글 영역에 구현 과정과 코드를 자유롭게 작성해주시면 됩니다.

사용할 데이터 구조와 풀이 방향성

적용할 알고리즘 혹은 메서드

수영

구현

DFS → BFS

코드(미완성)


function solution(maps) {
    let answer = 1;
    let visited = maps;
    const n = maps.length - 1;
    const m = maps[0].length - 1;
    const queue = [[0, 0]];
    const dx = [-1, 1, 0, 0];
    const dy = [0, 0, -1, 1];
    
    while (queue.length) {
        let size = queue.length;
        for(let i = 0; i < size; i++) {
            let [x, y] = queue.shift();
            // 상하좌우 확인
            for (let j = 0; j < 4; j++) {
                let nx = x + dx[j];
                let ny = y + dy[j];

                if(nx >= 0 && nx < n && ny >= 0 && ny < m && visited[nx][ny] === 1) {
                    queue.push([nx, ny]);
                    visited[nx][ny] = 0;
                }
            }
        }
        answer++;
    }
		// 실패
    return -1;
}

정은

구현

queue를 이용

👩‍💻

동서남북 push (1칸)

1-동의 동서남북 push (2칸)

1-서의 동서남북 push

2-동의 동서남북 push (3칸)

이렇게 영역을 넓혀가다가 도착지에 제일 먼저 도착했을 당시의 칸 수가 최단 거리가 되는 것이다!

최종 코드 (bfs)


function solution(maps) {
    var step = 1; //칸 수
    let visitedMaps = maps;
    const finish = [maps.length-1, maps[0].length-1]; //도착지점
    let bfsQueue = [[0,0]];
    let next = [[1,0],[-1,0],[0,1],[0,-1]]; //다음 방향을 위해
    
    visitedMaps[0][0] = 2; //지금 지점을 방문표시, 다시 접근하지 않는다.
    
    while (bfsQueue.length) { //가능한 모든 경우의 수(도착지에 도착하면 중간에 종료될 수 있음)
        
        const queueSize = bfsQueue.length;  //현재 큐에 들어있는 요소 개수 == 다음 칸으로 갈 수 있는 방법의 수
        
        for (let i=0; i<queueSize; i++) { //다음에 갈 수 있는 칸 수
            const [x,y] = bfsQueue.shift(); //dequeue, 현재지점
            
            for (let i=0; i<4; i++){  //동서남북
                const nextX = x+next[i][0]; //다음 칸 계산
                const nextY = y+next[i][1];
                
								//다음칸이 갈 수 있는 칸이면
                if (nextX>=0 && nextY>=0 && nextX<=finish[0] && nextY<=finish[1] && visitedMaps[nextX][nextY] != 2 && visitedMaps[nextX][nextY] != 0) {
                    if (nextX===finish[0] && nextY===finish[1]) { //도착하면
                        return step+1;
                    }
                    //도착하지 않았으면 다음 칸을 방문 표시하고 큐에 추가
                    visitedMaps[nextX][nextY] = 2; 
                    
                    bfsQueue.push([nextX,nextY]);
                }
            }
        }
        step++; //칸 증가
    }
    
    return -1; //return되지 않았다면, 도착하지 않았다는 것
}

처음 코드 (dfs - 효율성 테스트 미통과)


function solution(maps) {
    var answer = Infinity;
    const finish = [maps.length-1, maps[0].length-1];
    
    function dfs(i,j,count) {
        if (i < 0 || i > finish[0] || j < 0 || j > finish[1] || maps[i][j] === 0 || maps[i][j] === 2) {
            return;
        } //범위 밖 or 갔다온 곳이라면 이전으로 돌아감
        
        if (i === finish[0] && j === finish[1]) { //도착
            answer = Math.min(answer, count);
            return;
        }
        maps[i][j] = 2; //흔적 표시
                
        dfs(i+1,j,count+1);
        dfs(i,j+1,count+1); 
        dfs(i-1,j,count+1);
        dfs(i,j-1,count+1);
        
        maps[i][j] = 1; //흔적 표시 해제
    }
    
    dfs(0,0,1);
    
    return answer === Infinity ? -1 : answer;
}

종혁

구현

좌표에서 상하좌우 이동하는 문제+이동거리까지 구하는 문제는 bfs밖에 생각이 안났음

bfs를 이용하여 상대 팀 진영으로 갈 수 있는지 - 갈 수 있다면 이동거리는 얼마나 되는지를 구해야 함

[0,0]이 담긴 큐에서 시작하여 큐에서 shift() 되어 나온 좌표에서 인접한 좌표 중 막혀있지 않거나 , 인덱스를 넘어가지 않는 좌표들은 모두 큐에 넣으면서, 해당 좌표까지 이동할 수 있는지를 체크

visited 배열을 사용하여 이미 방문했던 좌표를 관리 + 이동시간까지 체크

Ex)[0,0]좌표에서 출발했으면 [0,1] , [1,0] 까지는 이동거리가 1, [0,1]에서 출발하여 [1,1]로 가는 이동거리는 1+1 = 2

코드


function solution(maps) {
    const n = maps.length-1
    const m = maps[0].length-1
    const visited = maps.map((v) => v.map((c) => 0))
     const direction = [
        [-1,0],[0,-1],[1,0],[0,1]
    ]
    const queue = [[0,0]]
    visited[0][0] = 1
    while(queue.length){
        const [y,x] = queue.shift()
        for(let dir of direction){
            let nextY = y + dir[0]
            let nextX = x + dir[1]
            if(nextX>= 0 && nextY >= 0 && nextX <= m && nextY <= n){
        if(maps[nextY][nextX] === 0 || visited[nextY][nextX] !== 0){continue}
            queue.push([nextY,nextX])
            visited[nextY][nextX] = visited[y][x] + 1
        }
        }
    }
    const result = visited[n][m] === 0 ? -1 : visited[n][m]
// [
//   [ 1, 0, 9, 10, 11 ],
//   [ 2, 0, 8, 0, 10 ],
//   [ 3, 0, 7, 8, 9 ],
//   [ 4, 5, 6, 0, 10 ],
//   [ 0, 0, 0, 0, 11 ]
// ]
    return result
}

재웅

구현

최단거리? BFS(queue)

조건 고려 후 이동, 이동 시마다 Score 계산

맵 범위를 벗어나지 않는 경우

벽(0)이 아닌 경우 길(1)인 경우

목표지점 도달 시의 Score 반환

코드




function solution(maps) {
    const dx = [0,0,1,-1]
    const dy = [1,-1,0,0]
    const queue = [[0,0,1]]
    
    while(queue.length>0){
        let [currentX,currentY,score] = queue.shift()
        const height = maps.length-1
        const width = maps[0].length-1
        
        // 목표 지점 도달 시 Score 반환
        if(currentX === width && currentY ===height) return score
        
        for(let i=0;i<4;i++){
            const nextX = currentX + dx[i]
            const nextY = currentY + dy[i]
            
            // 이동하려는 좌표가 맵 안에 있고, 유효한 길인 경우 이동
            if(nextX >=0 && nextY >=0 && nextX <= width && nextY <= height && maps[nextY][nextX] === 1){
                // 이동할 좌표 방문 표시 후 큐에 추가
                maps[nextY][nextX] = 0
                queue.push([nextX,nextY,score+1])
            }
        }
    }
    return -1
}

✏️ 후기

문제를 풀고 느낀 점, 막혔던 부분 혹은 개선 사항 등을 자유롭게 작성해주시면 됩니다.

👧🏻

수영

처음에 dfs+스택으로 구현하려고 했다.

다시 풀어볼 예정

👧🏻

정은

문제 보자마자 익숙한 dfs만 떠올랐지 bfs는 전혀 고려해보지 않았다

dfs와 다른 방식이라 신선했다. 다음번엔 최소거리는 두가지 방법을 모두 고려해봐야겠다.

bfs의 개념을 잡고, 구현하는 것에 감을 잡을 수 있는 시간이었다.

👦🏻

종혁

bfs + 이동거리까지 탐색해야 하는 문제

👦🏻

재웅

완탐은 DFS, 최단거리는 BFS로 풀면 된다는 노하우? 고정관념이 있는데 세션 내용을 바탕으로 개선해봐야겠습니다.

전형적인 2차원 배열에서의 최단거리 탐색이라 큰 어려움 없이 해결할 수 있었습니다.

게임 맵 최단거리

🔎 문제

🧩 구현과정 및 코드

수영

구현

코드(미완성)

정은

구현

최종 코드 (bfs)

처음 코드 (dfs - 효율성 테스트 미통과)

종혁

구현

코드

재웅

구현

코드

✏️ 후기