프로그래머스 '게임 맵 최단거리' 자바

 

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

 

 

프로그래머스

* 문제 링크

 

 

import java.util.*;

class Solution {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0,0,-1, 1}; 
    
    public int solution(int[][] maps) {
        int answer = 0;
        
        int[][] visited = new int[maps.length][maps[0].length];
        bfs(maps, visited);
        answer = visited[maps.length-1][maps[0].length-1];
        if(answer == 0){
            answer = -1;
        }
            
        return answer;
    }
    
    void bfs(int[][] maps, int[][] visited){
        Queue<int[]> q = new LinkedList<>();
        //큐에 현재 좌표 노드 넣고 표시
        q.add(new int[]{0,0});
        while(!q.isEmpty()){
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            visited[0][0] = 1;

            //상하좌우 탐색
            for(int i = 0; i < 4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx >= 0 && nx < maps.length && ny >=0 && ny < maps[0].length
                        && visited[nx][ny] ==0 &&maps[nx][ny] != 0 ){
                    visited[nx][ny] = visited[x][y] + 1;
                    q.add(new int[]{nx, ny});
                }
            }
        }
    }
}

이 문제를 풀면서 bfs에 대한 감을 좀 익힌 거 같다

보통 dfs/bfs를 보면 노드를 방문했는지 안했는지에 대한 배열을 만들어 주는 거 같다

확실히 자료구조, 알고리즘 등에서 전공과 비전공이 갈린다는 것을 많이 느낀다

그리고 배열 관련해서는 항상 length의 범위 안에 있도록 index 땡땡 out of  length 땡땡 오류를 조심해야 될꺼 같다

으렵다 으려워