DFS/BFS-Level2-게임 맵 최단거리(Java,C++,Python,Javascript)

코딩테스트 연습 - 게임 맵 최단거리

[문제 설명]

[제한사항]

maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

[입출력 예]

maps	answer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]	11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

공통로직

1. 최단거리를 찾기 위한 문제로 BFS를 활용
2. BFS를 활용하기 위해 queue를 기반으로 이동해야할 tesk를 관리
3. 재귀를 통해 현재 지점에서 반복적으로 map을 검사해 나감

Python

from collections import deque

def solution(maps):
    x_move = [1, 0, -1, 0]
    y_move = [0, 1, 0, -1]

    x_h, y_h = (len(maps[0]), len(maps))
    queue = deque([(0, 0, 1)])

    while queue:
        x, y, d = queue.popleft()

        for i in range(4):
            nx = x + x_move[i]
            ny = y + y_move[i]

            if nx > -1 and ny > -1 and nx < x_h and ny < y_h:
                if maps[ny][nx] == 1 or maps[ny][nx] > d + 1:
                    maps[ny][nx] = d + 1
                    if nx == x_h - 1 and ny == y_h - 1:
                        return d + 1

                    queue.append((nx, ny, d + 1))

    return -1

1. xy의 효율적인 처리를 위해 이동을 위한 변수(x_move, y_move)를 선언
2. map에 길이를 각각 x_h, y_h에 저장
3. 처리 대상을 관리하기 위핸 deque 선언(시작지점은 0,0로 값을 1을 주어 시작)
4. queue에 데이터가 존재하는 한 while을 통해 반복
   queue에 가장 왼쪽 값(선입 선출)을 x, y 그리고 d에 할당
5. 4가지 방향으로 이동하기 때문에 range(4)를 통해 반복
   x_move, y_move에 값을 차례로 주는 것으로 우,상,좌,하 순으로 이동
6. if를 통해 -1과 map의 길이(x_h, y_h)를 벗어나는지 검사
   맵을 벗어나지 않았다면 해당 위치에 길이 있거나, 지금까지 걸어온 값보다 큰지 확인
   True라면 현재 위치에 지금까지 걸어온 길의 count를 넣어줌
7. 만약 map의 마지막 위치라면 현재까지 걸어온 값을 return
8. 마지막 위치가 아니라면 queue에 다음 탐색지를 append
9. queue를 전부 조회해도 답이 안나오면 도달 할 수 없다는 뜻으로 -1 리턴

C++

#include<vector>
#include<iostream>
#include<queue>

using namespace std;

int check[101][101];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int solution(vector<vector<int> > maps)
{
    int n, m;
    n = maps.size();
    m = maps[0].size();
    queue<pair<int, int>> q;
    q.push(make_pair(0, 0));
    check[0][0] = true;

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m){
                if(check[nx][ny] == false && maps[nx][ny] > 0){
                    check[nx][ny] = true;
                    maps[nx][ny] = maps[x][y] + 1;
                    q.push(make_pair(nx, ny));
                }
            }
        }
    }

    int answer = 0;
    if(maps[n-1][m-1] == 1){
        answer = -1;
    }else{
        answer = maps[n-1][m-1];
    }
    return answer;
}

1. 방문 여부 검사를 위한 check와, 상하좌우 이동을 위한 dx, dy 선언
2. solution에서 처리를 위한 전처리를 진행
   map의 길이를 n과 m에 할당
   작업 목록 관리를 위한 queue 준비 후 0,0 데이터를 넣어줌
   make_pair는 입력된 매개변수를 이용해 pair 객체를 만들고 반환함
3. 시작 지점은 check[0][0]은 방문 처리를 해둠
4. q(작업 목록)에 작업할 요소가 있는 한 무한 반복
   q에 가장 처음 요소에 첫번째(first) 값과 두번째(second) 값을 x와 y에 할당(좌표 할당)
   q에서 가장 처음 요소를 제거(pop)
5. for문을 이용해 상하좌우를 처리하기 위해 4까지 반복
6. 이동 할 다음 지점을 nx, ny에 담아주고 if를 통해 해당 좌표가 맵을 벗어나는 지 확인
   벗어나지 않았다면 check[nx][ny]를 통해 다음 좌표가 아직 방문 전인지 확인하고, maps[nx][ny]를 통해 길이 존재하는지 확인
7. 길이 존재한다면 이동할 좌표를 방문 목록에 추가하고 maps 상에서 현재 위치에 값(누적된 count)에 +1을 해서 다음 이동 좌표에 값으로 넣어줌
8. 다음 좌표를 q(작업 목록)에 넣어줌
9. 모든 처리가 끝나서 더이상 q에 작업 요소가 없다면 maps에 마지막 위치를 검사함
   1인 경우 도달하지 못했다는 뜻으로 -1 리턴
   아닌 경우 마지막 좌표에 저장된 누적된 count값을 리턴

Java

import java.util.LinkedList;
import java.util.Queue;
import java.awt.Point;
class Solution {
    public static int solution(int[][] maps) {
        int X = maps[0].length;
        int Y = maps.length;
        boolean[][] visited = new boolean[Y][X];
        Queue<Point> q = new LinkedList<Point>();
        int x = 0;
        int y = 0;
        int size = 0;
        int cnt = 0;
        Point p = new Point();
        q.add(new Point(Y-1,X-1));
        while(q.isEmpty()==false) {
            size = q.size();
            cnt++;
            for(int i=0;i<size;i++)
            {
                p = q.peek();
                x = p.y;
                y = p.x;
                q.remove();
                if(visited[y][x]==true)
                    continue;
                maps[y][x] = 0;
                visited[y][x] = true;
                if(x==0 && y==0) {
                    return cnt;
                }
                if(x-1>-1 && maps[y][x-1]==1) { //왼쪽 한칸
                    q.add(new Point(y,x-1));
                }
                if(x+1<X && maps[y][x+1]==1) { //오른쪽 한칸
                    q.add(new Point(y,x+1));
                }
                if(y-1>-1 && maps[y-1][x]==1) { //위쪽 한칸
                    q.add(new Point(y-1,x));
                }
                if(y+1<Y && maps[y+1][x]==1) { //아래쪽 한칸
                    q.add(new Point(y+1,x));
                }
            }
        }
        return -1;
    }
}

1. 처리를 위한 전처리로 maps에 길이값을 X, Y에 저장
   방문 여부를 확인하기 위한 visited 선언
   작업 목록을 위한 Queue를 선언하지만, LinkedList를 활용
   (일반 array는 배열에 들어있는 양에 따라 동적으로 계산해주어야 하기 때문에 효율적인 자원 관리를 위해 LinkedList를 사용)
   방문한 좌표 처리를 위한 Point 객체 선언
2. q(작업 목록)에 map의 마지막 지점에 좌표를 등록
   q에 요소가 존재하는 한 while을 통한 반복 진행
3. 현재 작업 목록 반복을 위해서 q의 size를 size라는 변수로 선언
   이동 count인 cnt을 증가시킴
   for을 통해 작업 목록만큼 반복
   q(작업 목록)에 peek()를 사용해 맨 앞에 있는 값을 반환시킴
   q에 맨 앞에 요소였던 point 객체의 x, y 좌표값을 가져옴(초기 선언때 Y, X를 반대로 넣었음)
   q에 remove를 사용해 첫번째 요소 삭제
4. visited를 검증해 현재 위치가 방문한 적이 있다면 continue를 통해 생략
   현재 위치의 값을 0으로 만들고, visited에 true를 적용시켜 방문했음을 표시
   만약 현재 위치가 시작지점인 0,0이라면 cnt를 return
5. if를 통해 상하좌우 이동을 진행함
   맵의 범위를 벗어났는지 및 다음 이동 위치에 길이 존재하는지를 확인 후 q에 해당 좌표 point 객체를 add 시켜서 작업 목록에 등록함
6. 모든 반복이 종료되고 return 되지 않았다면, 도달할 수 없다는 뜻으로 -1 반환

Javascript

function solution(maps) {

    var yLen = maps.length - 1;
    var xLen = maps[0].length - 1;

    var queue = [[0, 0]];

    var visited = Array.from(new Array(maps.length), () => new Array(maps[0].length).fill(false));

    var result = 0;

    while (queue.length) {
        result++;
        var size = queue.length;
        for (var i = 0; i < size; i++) {
            var point = queue.shift();
            var curY = point[0];
            var curX = point[1];

            if (visited[curY][curX]) continue;

            maps[curY][curX] = 0;

            visited[curY][curX] = true;

            if (curY === yLen && curX === xLen) return result;

            if (curY < yLen && maps[curY + 1][curX] === 1) queue.push([curY + 1, curX])
            if (curX < xLen && maps[curY][curX + 1] === 1) queue.push([curY, curX + 1])
            if (curY > 0 && maps[curY - 1][curX] === 1) queue.push([curY - 1, curX])
            if (curX > 0 && maps[curY][curX - 1] === 1) queue.push([curY, curX - 1])
        }
    }

    return -1;
}

1. 길이를 저장하기 위한 yLen, xLen, 작업 목록을 위한 queue
   방문 여부 확인을 위해 visited를 선언하고 false를 통해 값을 채워줌
   while을 통해 queue에 작업 요소가 있는지 확인해 반복 진행
2. 반복이 시작되면 result를 증가시킴
   작업 목록 반복을 위해서 queue의 길이를 size에 저장
   queue에 가장 왼쪽 값을 꺼내 point에 담음
   현재 위치 값을 curY, curX에 각각 담음
3. if를 통해 현재 위치가 이미 방문한 적 있다면(visited 사용) continue로 다음 반복을 진행
   방문한 적이 없다면 현재 위치를 maps 상에서 0으로 표시 및 visitied를 통해 방문 처리
   만약 현재 위치가 마지막 위치라면 result를 return
   if를 통해 맵의 범위를 벗어나지 않으며, 다음 이동할 위치에 길이 존재한다면 queue에 push를 통해 다음 좌표값을 넘겨줌
4. 모든 queue 처리가 완료되고 return이 발생하지 않으면 마지막에 도달하지 못한 것임으로 -1을 return

정리

python: 특이점으로 queue에 데이터를 넣을 때 x,y 및 3번째 값인 d를 활용함, deque를 활용해 가장 왼쪽 값을 popleft를 통해 추출함, 타 언어에 비해 코드가 간결하고 visited에 대한 선언을 3번째 값으로 대체함

C++: queue를 사용시 pair 객체를 활용함

Java: queue를 관리하는 방식으로 LinkedList 방식을 사용, queue에 Point 객체를 명시해 사용하는 방법을 씀

Javascript: visitied를 선언 시 Array를 통해 false값을 채워주는 방식을 사용