[프로그래머스/Java] 미로탈출_bfs

자바...
파이썬으로는 쉽게 풀었던 거 같은데, 동적할당부터 String 배열 처리 등등 생각해야 할 게 너무 많다...
자바로 코테 고정시켜놓은 사람 누구ㅇ ㅑ....

import java.util.*;

class Solution {
    String[][] map;
    int r;
    int c;
    int[] row = {1,-1,0,0};
    int[] col = {0,0,1,-1};
    
    public int solution(String[] maps) {
        r = maps.length;
        c = maps[0].length();
        int answer = 0;
        
        map = new String[r][c];
        
        int[] start = new int[2];
        int[] lever = new int[2];
        int[] end = new int[2];
        
        for (int i = 0; i < r; i++) {
            String[] temp = maps[i].split("");
            map[i] = temp;
            for (int j = 0; j < c; j++) {
                if (temp[j].equals("S"))
                    start = new int[] {i,j};
                else if (temp[j].equals("L"))
                    lever = new int[] {i,j};
                else if (temp[j].equals("E")) {
                    end = new int[] {i,j};
                }
            }
        }
        int result1 = bfs(start, lever);
        int result2 = bfs(lever, end);
        
        if(result1 == -1 || result2 == -1)
            return -1;
        return result1 + result2;
    }
    
    public int bfs(int[] start, int[] e) {
        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[r][c];
        q.add(new int[] {start[0], start[1], 0});

        
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            visited[cur[0]][cur[1]] = true;
            
            if (cur[0] == e[0] && cur[1] == e[1])
                    return cur[2];
            
            for(int k = 0; k < 4; k++) {
                int nrow = cur[0] + row[k];
                int ncol = cur[1] + col[k];
                
                if(nrow >= 0 && nrow < r && ncol >= 0 && ncol < c){
                    if(!map[nrow][ncol].equals("X")) {
                        if(visited[nrow][ncol] == false) {
                            visited[nrow][ncol] = true;
                            q.add(new int[] {nrow, ncol, cur[2] + 1});
                        }
                    }
                }
            }
            
        }
        return -1;
    }
}

설명에서 몇번째 줄인지 명시가 필요해 사진도 첨부했다.

여기서 포인트는 63번째줄에서 인접한 칸들을 탐색하고 큐에 추가하는 동시에, visited true처리도 반드시 해줘야 한다는 거다.

처음에는 50번째 줄에서 true처리 해줄거니까 상관없겠다 생각했는데, 여기서 조금 생각이 필요하다.
이 처리를 안해주면, (1,1)에서 인접 칸 (2,1)를 탐색하는 경우, (2,1)이 큐에 추가되었지만 (2,1)에 대한 visited가 true가 되지 않았기에, 다른 칸 예를 들어 (2,2)에서 인접 칸(2,1)를 다시 탐색하고, 아직 visited 처리가 안되었기 때문에, (2,1)이 큐에 또 들어가게 될 수 있으며, 이럴 경우 최소거리를 구하지 못하게 된다.
최단거리 구할 때는 인접노드 탐색하고 큐 추가할 때 무조건 방문처리도 같이 해줄 것 명심하자.