프로그래머스 1844 게임 맵 최단거리 자바 풀이

난이도 : Lv. 2

풀이일 : 2410174

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

프로그래머스

---

문제

---

풀이

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int N = maps.length;
        int M = maps[0].length;
        int visited[][] = new int[N][M];
        
        // queue 생성 및 초기 위치 추가
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        queue.add(0);
        
        // BFS
        while (!queue.isEmpty()) {
            // 현재위치 및 4방향 지표
            int i = queue.poll();
            int j = queue.poll();        
            int[] di = {-1, 1, 0, 0};
            int[] dj = {0, 0, -1, 1};
            
            // 4방향 탐색
            for (int k = 0; k < 4; k++) {
                int ni = i + di[k];
                int nj = j + dj[k];
                
                // 맵 범위 내에 있으며 방문한 적이 없고 길이 있다면
                // 방문 기록 및 큐에 추가
                if (0 <= ni && ni < N && 0 <= nj && nj < M) {
                    if (visited[ni][nj] == 0 && maps[ni][nj] == 1) {
                        visited[ni][nj] = visited[i][j] + 1;
                        queue.add(ni);
                        queue.add(nj);
                    }
                }
            }
        }
        // 상대방 진영까지의 칸 수 혹은 방문불가 여부 저장
        answer = visited[N-1][M-1] > 0 ? visited[N-1][M-1] + 1 : -1;
        return answer;
    }
}

• N, M : 맵의 행열 크기를 저장하는 변수
• visited : 지금까지 방문한 곳의 거리를 기록하는 2차원 배열
• queue : 진행 경로 정보 저장, 해당 자리에서 4방향 탐색을 진행
• i, j : queue에서 가져온 현재 위치 정보
• di, dj : 4방향 탐색을 위한 방향 지표
• ni, nj : i, j를 기준으로 4방향 지표를 더한 진행 칸
• ni, nj가 맵 범위 내에 있으며 방문한 적이 없고, 길이 있는 경우에는 방문 기록과 함께 큐에 추가
• queue가 비었다면 while 반복문을 중단하고 answer를 기록한다.
• visited[N-1][M-1]에 기록된 숫자가 있다면 해당 숫자를, 기록된 숫자가 없다면 -1을 answer로 재할당

---

개선

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[][] maps) {
        int answer = 0;
        int N = maps.length, M = maps[0].length;
        int visited[][] = new int[N][M];
        
        // queue 생성 및 초기 위치 추가
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        queue.add(0);
        
        // BFS
        while (!queue.isEmpty()) {
            // 현재위치 및 4방향 지표
            int i = queue.poll(), j = queue.poll();       
            int[] di = {-1, 1, 0, 0}, dj = {0, 0, -1, 1};
            
            // 4방향 탐색
            for (int k = 0; k < 4; k++) {
                int ni = i + di[k], nj = j + dj[k];
                
                // 맵 범위 내에 있으며 방문한 적이 없고 길이 있다면
                // 방문 기록 및 큐에 추가
                if (0 <= ni && ni < N && 0 <= nj && nj < M) {
                    if (visited[ni][nj] == 0 && maps[ni][nj] == 1) {
                        visited[ni][nj] = visited[i][j] + 1;
                        queue.add(ni);
                        queue.add(nj);
                    }
                }
            }
        }
        // 상대방 진영까지의 칸 수 혹은 방문불가 여부 저장
        answer = visited[N-1][M-1] > 0 ? visited[N-1][M-1] + 1 : -1;
        return answer;
    }
}

• N, M 설정 시 등 두 줄 반복되는 내용들이 한 줄로 처리가 되길래 한 줄로 수정한 버전

---

배운점

• 자바 queue에서 요소를 뽑아낼 때에는 poll을 사용한다. -> 처음에는 pop으로 작성했다가 안되는 이유를 찾았다.
• 0과 숫자가 있는 경우 !변수 형태의 검사가 불가능한다.
• System.out.println() 내에 삼항 연산자를 추가하는 경우, 조건식에 () 괄호가 필요하다.

느낀점

• queue가 비었을 때 조건을 처음에는 queue.size() == 0으로 작성했었는데, 이런 사소한 것들이 아직 자바에 익숙하지 않다.
• 메서드를 모르겠을 때나 파이썬과 차이 때문에 막혔을 때는 바로 확인하고 배우고 기억하자.