[코딩테스트] Java 게임 맵 최단거리

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

BFS를 활용한 문제였습니다. BFS/DFS 문제들은 중복 방문에 대한 처리를 확인해주셔야하며 OutOfRange가 나지 않기 위해
validation 체크를 진행해주셔야 합니다.

소스코드

import java.util.*;

class Solution {
    
    class Pair {
        int x, y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    int n, m;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int[][] s;
    boolean[][] visited;
    int[][] globalMaps;
    Queue<Pair> q = new LinkedList<>();
    
    public void init() {
        s = new int[n][m];
        visited = new boolean[n][m];
        q.add(new Pair(0, 0));
        s[0][0] = 1;
        visited[0][0] = true;
    }
    
    public boolean inRange(int x, int y) {
        return 0 <= x && x < n && 0 <= y && y < m;
    }
    
    public boolean canGo(int x, int y) {
        if(!inRange(x, y)) return false;
        if(visited[x][y] || globalMaps[x][y] == 0) return false;
        return true;
    }
    
    public void bfs() {
        while(!q.isEmpty()) {
            Pair cur = q.poll();
            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(canGo(nx, ny)) {
                    q.add(new Pair(nx, ny));
                    visited[nx][ny] = true;
                    s[nx][ny] = s[cur.x][cur.y] + 1;
                }
            }
        }
    }
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        globalMaps = new int[n][m];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                globalMaps[i][j] = maps[i][j];
            }
        }
        
        init();
        bfs();
        
        if(s[n-1][m-1] == 0) {
            return -1;
        }
        return s[n-1][m-1];
    }
}

코드 설명

• 변수 설명
  • n: maps의 행
  • m: maps의 열
  • globalMaps: 다른 메소드에서 접근하기 위한 maps의 복사본
  • s: 각 위치까지의 이동 거리를 저장하는 2차원 배열입니다.
  • visited: i행 j열 방문했는지 확인하기위한 배열
  • q: BFS 탐색을 위한 큐로, 탐색해야 할 좌표를 저장합니다.

public void init() {
    s = new int[n][m];
    visited = new boolean[n][m];
    q.add(new Pair(0, 0));
    s[0][0] = 1;
    visited[0][0] = true;
}

public boolean inRange(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

public boolean canGo(int x, int y) {
    if(!inRange(x, y)) return false;
    if(visited[x][y] || globalMaps[x][y] == 0) return false;
    return true;
}

• init 메소드
  전역 변수 초기화 메소드
• inRange 메소드
  다음 탐색해야하는 좌표가 배열 내부인지 확인하기 위한 메소드
• canGo 메소드
  다음 탐색해야하는 좌표로 이동이 가능한지 확인하기 위한 메소드(배열 내인지, 방문한 좌표인지, 다음 좌표가 벽인지)

public void bfs() {
    while(!q.isEmpty()) {
        Pair cur = q.poll();
        for(int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if(canGo(nx, ny)) {
                q.add(new Pair(nx, ny));
                visited[nx][ny] = true;
                s[nx][ny] = s[cur.x][cur.y] + 1;
            }
        }
    }
}

• dx와 dy 테크닉을 통해 다음 탐색 좌표로 이동할 수 있으면 방문 처리 후 스텝을 1 증가시킵니다.

if (s[n-1][m-1] == 0) {
    return -1;
}
return s[n-1][m-1];

• s배열이 0이면 -1을 아니면 그 값을 반환합니다.