[Algorithms] 게임 맵 최단거리 (JS)

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

 

이 문제는 JS로 코딩했습니다. (문제가 Swift 지원 안 함, 추 후에 혼자 한 번 만들고 맨 밑에 추가하겠다.)
프로 대기업 코테 탈락러로서 말합니다.
이거 무.조.건.반.드.시 외우세요.

 

문제의 요구 사항을 간단하게 말하자면

시작점 (0, 0)에서 도착점 (n-1, m-1)에 도착하기까지 최단거리를 구하고, 도착이 불가능할 경우 -1을 출력하라.

가 되겠죠.

 

전형적인 BFS/DFS 문제입니다.

난 진짜 시간없고 코테만 뚫으면 된다? "최단거리" 키워드 나오면 그냥 BFS 하세요.

 

그럼 BFS(너비우선탐색)랑 DFS(깊이우선탐색) 중 뭐로 하나요?

이건 BFS임. 왜요? 저는 DFS가 더 익숙한데요? ㅇㅇ 나도 그럼. 하지만 이건 BFS가 맞음

 

• BFS는 가까운 곳부터 차례대로 탐색함, 그래서 첫 번째로 도착한 경로가 바로 최단 경로임ㅇㅇ BFS는 가장 가까운 위치부터 탐색하기 때문에, 도착점에 먼저 도착하는 경로가 최단 경로가 되는 거지
• DFS는 한쪽 길을 끝까지 쭉 가버린 다음에 다른 길을 보니까, 중간에 짧은 길을 놓칠 수 있음

---

1. 방향을 먼저 정하자

우선 이동할 수 있는 방향을 선언합니다.

위아래 왼쪽 오른쪽만 가능하다네요 정말 다행입니다. 대각선 나오면 좀 귀찮아짐ㅎ

    const directions = [
        [0, 1],  // 오른쪽
        [0, -1], // 왼쪽
        [1, 0],  // 아래
        [-1, 0]  // 위
    ];

• [0, 1]: 현재 위치에서 오른쪽(동쪽)으로 한 칸 이동
• [0, -1]: 왼쪽(서쪽)으로 한 칸 이동
• [1, 0]: 아래쪽(남쪽)으로 한 칸 이동
• [-1, 0]: 위쪽(북쪽)으로 한 칸 이동

---

2. 맵의 크기 확인

    const n = maps.length;
    const m = maps[0].length;

---

3. BFS 함수 호출

이제 본격적으로 BFS를 돌릴 차례! 현 위치 (0, 0)에서 출발해서 BFS 함수를 호출해요.

    return bfs(0, 0, maps, n, m, directions);

여기서 가장 중요한 BFS 함수를 만들 차례임.

BFS는 가까운 곳부터 차례로 탐색하기 때문에, 최단 경로를 찾는 데 활용됩니다.

아 저는 함수 내에 함수를 선언하는 걸 선호하지 않아서 밖에다 작성했는데, 안 그러시는 분들도 많이 계시니까 알아서 선호하는 걸로 하세요.

---

 

코드 먼저 투척!

const bfs = (startX, startY, maps, n, m, directions) => {
    const queue = [[startX, startY, 1]];
    const visited = Array.from(Array(n), () => Array(m).fill(false));
    visited[startX][startY] = true;

    while (queue.length > 0) {
        const [x, y, distance] = queue.shift();

        if (x === n - 1 && y === m - 1) {
            return distance;
        }
        
        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && maps[nx][ny] === 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.push([nx, ny, distance + 1]);
            }
        }
    }    
    return -1;
};

---

하나씩 뜯어보자!

4. BFS 함수 작성

    const queue = [[startX, startY, 1]];
    const visited = Array.from(Array(n), () => Array(m).fill(false));
    visited[startX][startY] = true;

 

여기서 queue는 탐색할 위치를 기록하는 리스트, 첫 번째로 (0, 0)에서 출발하고, 이동 거리는 1인 거죠

visited는 이미 방문한 곳을 기록해 두는 배열, 이미 지나간 곳을 다시 탐색하지 않기 위해서 사용함, 출발점은 당연히 이미 방문했다고 표시

---

5. 큐에서 하나씩 꺼내서 탐색

    while (queue.length > 0) {
        const [x, y, distance] = queue.shift(); // 현재 위치와 현재까지의 이동거리 가져오기

		// 꺼내온 값이 상대 진영 위치 값과 같다면 이동거리 반환
        if (x === n - 1 && y === m - 1) {
        	return distance;
        }

	...
    
    }

---

6. 네 방향으로 이동 가능 여부 확인

	...

        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;

            if (nx >= 0 && ny >= 0 && nx < n && ny < m && maps[nx][ny] === 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;  // 방문 표시
                queue.push([nx, ny, distance + 1]);  // 새로운 위치와 거리를 큐에 추가
            }
        }
    }

네 방향으로 이동할 수 있는지 확인하는 로직입니다.

directions가 뭐임? -> 아까 처음에 선언한 네 방향이잖슴.

그럼 nx가 뭐겠음? 현 위치 + 행 이동한 값

그럼 ny가 뭐겠음? 현위치 + 열 이동한 값

 

저 if문 안에 뭐가 많죠? 이걸 한글로 써보자면

이동한 행과 열이 0보다 크거나 같고(맵 안에 있고) 이동한 행과 열이 전체 맵보다 작으면서 내가 이동한 위치가 맵에서 벽(0)이 아니고 이전에  방문한 기록이 없으면~~~~ 인 거임.

이거 다 참이라서 if문으로 들어오게 되면? -> 방문 표시를 하고 queue에 현 위치와 거리를 추가하는 거죠!

이 짓을  상대방 진영에 도착하거나 queue.length가 0이 되기전까지 계속하는 거임...

만약 큐를 다 돌렸는데도 도착점에 도달하지 못했다면 -1을 반환해요. -> 도착할 수 없다는 뜻이 되겠죠.

 

확실히 js가 swift보다 유연하기는 한 것 같다. 쓰기 편하네

전체 코드

const bfs = (startX, startY, maps, n, m, directions) => {
    const queue = [[startX, startY, 1]];
    const visited = Array.from(Array(n), () => Array(m).fill(false));
    visited[startX][startY] = true;

    while (queue.length > 0) {
        const [x, y, distance] = queue.shift();

        if (x === n - 1 && y === m - 1) {
            return distance;
        }
        
        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && maps[nx][ny] === 1 && !visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.push([nx, ny, distance + 1]);
            }
        }
    }
    
    return -1;
};

function solution(maps) {
    const directions = [
        [0, 1], 
        [0, -1],
        [1, 0], 
        [-1, 0] 
    ];
    
    const n = maps.length;
    const m = maps[0].length;
    return bfs(0, 0, maps, n, m, directions);
}

 

 

++ 24.10.15: Swift 코드 추가

import Foundation

func bfs(_ startX: Int, _ startY: Int, _ maps: [[Int]], _ n: Int, _ m: Int, _ directions: [(Int, Int)]) -> Int {
    var queue: [(Int, Int, Int)] = [(startX, startY, 1)]
    var visited = Array(repeating: Array(repeating: false, count: m), count: n)
    visited[startX][startY] = true
        
    while !queue.isEmpty {
        let (x, y, distance) = queue.removeFirst()
                
        if x == n - 1 && y == m - 1 {
            return distance
        }
                
        for (dx, dy) in directions {
            let nx = x + dx
            let ny = y + dy
                        
            if nx >= 0 && ny >= 0 && nx < n && ny < m && maps[nx][ny] == 1 && !visited[nx][ny] {
                visited[nx][ny] = true
                queue.append((nx, ny, distance + 1))
            }
        }
    }
    return -1
}

func solution(_ maps: [[Int]]) -> Int {
    let directions: [(Int, Int)] = [
        (0, 1),
        (0, -1),
        (1, 0),
        (-1, 0)
    ]
    
    let n = maps.count
    let m = maps[0].count
    
    return bfs(0, 0, maps, n, m, directions)
}