[Programmers] 1844 게임 맵 최단거리 (L2 / BFS) - Java

링크

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

프로그래머스

 

 

 

 

문제 해석

(1, 1)에서 (N, M)까지의 최단 거리 구하기

 

 

 

 

풀이 & 코드 해석

기본적인 BFS 문제입니다.

 

BFS의 길찾기 관련 문제를 풀 수 있으면 쉽게 해결 가능합니다.

 

BFS 개념이 익숙하지 않으시다면 아래 링크를 참고하셔서 개념 정리 후 문제를 풀어주세요.

 

https://angelplayer.tistory.com/404

[알고리즘] BFS (너비 우선 탐색)

 

 

 

 

코드

// 길은 1, 벽은 0

import java.io.*;
import java.util.*;

class Solution {
    
    static boolean[][] v; // 방문 배열
    static int answer;
    public int solution(int[][] maps) {
        answer = -1; // 정답의 시작 값을 -1로 지정
        v = new boolean[maps.length][maps[0].length];
        
        // 화면 출력용
        //print(maps);
        
        bfs(maps);
        
        return answer;
    }
    
    public class Point {
        int x; // x좌표
        int y; // y좌표
        int level; // 지나온 칸의 개수
            
        Point(int x, int y, int level) {
            this.x = x;
            this.y = y;
            this.level = level;
        }
    }  
    
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    
    public void bfs(int[][] maps) {
        Queue<Point> q = new LinkedList<>();
        
        q.offer(new Point(0, 0, 1)); // 자기 시작 위치도 포함해서 길을 개수 세야 함
        v[0][0] = true;
        
        // q가 비어있지 않은 동안 반복
        while(!q.isEmpty()) {
            Point p = q.poll();
            
            // 도착했다면
            if (p.x == maps.length - 1 && p.y == maps[0].length -1) {
                System.out.println("도착 : !! : " + p.level);
                answer = p.level;
                return;
            }
            
            // 사방 탐색
            for (int d = 0; d < dx.length; d++) {
                int nx = p.x + dx[d];                 
                int ny = p.y + dy[d];     
                
                // 맵 밖을 벗어나지 않고 / 벽이 아니며 / 방문하지 않았다면
                if (nx >=0 && nx < maps.length && ny >=0 && ny < maps[0].length 
                    && maps[nx][ny] != 0 && !v[nx][ny]) {
                    v[nx][ny] = true;
                    q.offer(new Point(nx, ny, p.level + 1));
                }
            }
        }
    }
    
    // 화면 출력용
    public void print(int[][] maps) {
        for (int i = 0; i < maps.length; i++) {
            for (int j = 0; j < maps[i].length; j++) {
                System.out.print(maps[i][j] + " ");
            }
            System.out.println();
        }    
    
    }
}

 

 

 

 

발생한 문제 & 해결 방안

확인을 위해서 map을 출력하는 변수를 만들어두었는데, 그것 때문에 시간초과 문제가 발생하였다.

 

앞으로는 테스트 출력을 위한 print를 사용한 후에는 지우거나 주석처리하도록 하자!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java