[프로그래머스] 게임 맵 최단 거리 구하기 (bfs)

 

 

요즘에 인텔리제이를 사용하지 않고 메모장에 문제를 푸는 수준으로.... IDE없이 풀고있다..

그래서 그런지 평소에 그래도 잘 풀었던 문제들도 잘 안풀리는 경우가 발생하기 시작했다.. (모든 테스트를 통과하기까지 오래걸린다는 의미...)

실력부족 탓이라 생각하자.

암튼 이번 문제는 최단 거리 문제인 bfs문제이고 ide없이 처음으로 코드를 쫘르륵 펼친 문제이다. (bfs 고전 문제 + 백준에서 가장 많이 풀어본 유형이라 가능했었던 것 같다)  

 

실수했던 부분이 몇 부분이 있었는데

• dy배열을 0,1,0,-1로 해줬어야했는데 오마이 갓 1,0,-1,0으로 해버렸다는점!
  • 이래서 n,m까지 도달하지 못했다 (왜 계속 -1이 뜨는지 모르겠었는데 이런 어처구니 없는 실수를 했다
• bfs호출하기 전에 visited[0][0]을 true로 초기화해주지 않았다.
• nx >= 0 && nx < maps.length && ny >= 0 && ny < maps[0].length 범위 처리 부분에서 nx > 0 이라고 설정해서 인덱스가 0일 때 처리를 할 수 없었다.

 

import java.util.*;

class Solution {
    public Queue<Position> queue = new LinkedList<>();
    public int[] dx = {-1,0,1,0};
    public int[] dy = {0,1,0,-1};
    public boolean[][] visited;
    
    public int solution(int[][] maps) {
        int answer = 0;
        
        int n = maps.length;
        int m = maps[0].length;
        visited = new boolean[n][m];
        
        Position p = new Position(0,0,1);
        queue.add(p);
        visited[0][0] = true;
        
        answer = bfs(maps);
        return answer;
    }
    //최단 거리 : bfs
    
    public int bfs(int[][] maps){
        
        while(!queue.isEmpty()){
            
            Position p = queue.poll();
        
            int x = p.x;
            int y = p.y;
            int cnt = p.cnt;

            if(x == maps.length - 1 && y == maps[0].length-1){
                return cnt;
            }
            
            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){
                    if(maps[nx][ny] == 1 && !visited[nx][ny]){
                        visited[nx][ny] = true;
                        Position np = new Position(nx,ny,cnt+1);
                        queue.add(np);
                    }
                }
                
                 
            }
        }
        return -1; //목적지에 도달하지 못했을 경우
    }
}

class Position {
    int x;
    int y;
    int cnt;
    
    Position(int x, int y, int cnt){
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}

 

 

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

프로그래머스