본문 바로가기

PS

[Programmers] LV2 - 게임 맵 최단거리

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

 

코딩테스트 연습 - 게임 맵 최단거리

[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1

programmers.co.kr

문제 입출력 예

BFS를 활용하여 푸는 문제이다.

마지막 상대 진영까지 가지 못할 경우 -1을 return 해주는 부분만 잘 처리해주면 무난한 문제

 

더보기
import java.util.*;
class Solution {
    static int n,m;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public int solution(int[][] maps) {
        int answer = 0;
        
        n = maps.length;
        m = maps[0].length;
        
        answer = BFS(maps);
        
        return answer;
    }
    public int BFS(int[][] maps){
        Queue<Point> q = new LinkedList<Point>();
        q.add(new Point(0,0));
        
        int cnt = 1;
        
        boolean[][] visited = new boolean[n][m];        
        
        while(!q.isEmpty())
        {
            int size = q.size();
            
            for(int sz = 0; sz<size;sz++)
            {
                Point p = q.poll();
                int x = p.x;
                int y = p.y;
                
                if(x == n-1 && y == m-1){
                    return cnt;
                }
                for(int cycle = 0; cycle<4;cycle++)
                {
                    int cx = x+dx[cycle];
                    int cy = y+dy[cycle];
                    
                    if(0<=cx && cx<n && 0<=cy && cy<m && maps[cx][cy] == 1 && !visited[cx][cy])
                    {
                        visited[cx][cy]=true;
                        q.offer(new Point(cx,cy));
                    }
                }
            }
            cnt++;
        }
        return -1;
    }
}
class Point
{
    int x;
    int y;
    
    Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

 

'PS' 카테고리의 다른 글

[BOJ]14502번: 연구소  (0) 2021.06.18
[BOJ]16234번: 인구 이동  (0) 2021.06.16
[Programmers]LV2 - 예상대진표  (0) 2021.06.14
[BOJ]17144번 : 미세먼지 안녕!  (0) 2021.06.14
[BOJ] 1958번: LCS 3  (0) 2021.06.03