Today I Learned

일주일째 DFS/BFS 문제를 푸는 중. 코테 중에서 빈도가 가장 높은 편이기도 하고 실제로 적용할 곳도 많아서 풀면서 재미는 있다. 이번 기회에 이쪽은 아예 마스터를 해보자!!

게임 맵 최단거리(BFS)

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

• 문제
  맵의 왼쪽 구석에서 오른쪽 구석으로 가장 빨리 가는 경로의 이동 횟수를 구하는 문제. 막힌 부분은 갈 수 없고, 한번에 동서남북 4방향으로만 움직일 수 있다. 만약 갈 수 없다면 -1을 반환하고 가능하다면 최단 경로의 횟수를 return 하라.

• 풀이 과정

1. DFS와 BFS에서 약간 고민했다. 일반적으로 미로찾기 문제는 dfs라고 알고는 있었지만 이번 문제 같은경우는 최단 경로를 찾고 그 경로의 이동 횟수를 구하는 문제기 때문에 bfs로 한단계씩 이동 횟수를 늘려가면서 찾는것이 더 낫다고 판단했다.

2. 동서남북 이동을 구현하기 위해 배열 2개를 x좌표이동과 y좌표 이동용으로 준비했다.

3. bfs 구현은 큐로. LinkedList가 아닌 ArrayDeque을 구현체로 써 봤다.

4. x좌표, y좌표, 이동횟수(깊이) 3가지 정보를 큐에다 저장해야 했기에 int[] 배열의 사이즈를 3으로 설정했다.

5. for문 안에서 0,1,2,3으로 돌면서 동남서북으로 움직인다. 새로운 좌표가 범위를 넘어서거나 이미 방문했거나 이동 불가능하면(map에서 0) 큐에 넣지 않는다.

6. 원래는 최종좌표가 맞는지 확인한 후 아니면 방문처리를 했었지만 이렇게 할 경우 효율성테스트에서 시간 초과가 발생했다. 제대로 방문처리가 되고 있지 않다고 생각하여 방문 처리 위치를 바꿨다. 큐에서 열어볼 때 하는 것이 아니라 큐에 넣자마자 방문처리를 해서 제대로 방문 처리가 되도록 만들었다.

• 최종 구현

import java.util.*;

class Solution {
    boolean[][] visited;
    int[] xMove = {1,0,-1,0};
    int[] yMove = {0,1,0,-1};
    
    public int bfs(int x, int y, int n, int m, int[][] maps){
        visited[x][y] = true;
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0,0,0});
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int tmpX = tmp[0];
            int tmpY = tmp[1];
            int tmpDepth = tmp[2];
            
            if (tmpX == n-1 && tmpY == m-1) {
                return tmpDepth+1;
            }
            
            for(int i=0; i<4; i++){
                int newX = tmpX+xMove[i];
                int newY = tmpY+yMove[i];
                if(newX<0 || newY<0 || newX>=n || newY>=m) continue;
                
                if(visited[newX][newY] || maps[newX][newY]==0) continue;
                    int[] newTmp = {tmpX+xMove[i], tmpY+yMove[i], tmpDepth+1};
                
                q.offer(newTmp);
                visited[newX][newY] = true;
            }
            
        }
        
        return -1;
        
    }
    
    public int solution(int[][] maps) {
        int answer = 0;
        int n = maps.length;
        int m = maps[0].length;
        visited = new boolean[n][m];
        
        
        return bfs(0,0,n,m,maps);
    }
}