99클럽 코테 스터디 12일차 TIL - LV2. 게임 맵 최단거리

 

오늘의 학습 키워드

• 너비우선탐색 (BFS)

오늘의 회고

1. 문제

문제 URL

프로그래머스

2. 해결 방안

import java.util.*;

class Solution {
    public static int n, m;
    public static int answer = -1;
    
    public static int dx[] = {-1, 1, 0, 0};
    public static int dy[] = {0, 0, -1, 1};
    public static boolean visited[][];
    
    public int solution(int[][] maps) {
        n = maps.length;
        m = maps[0].length;
        visited = new boolean[n][m];
    
        return bfs(0, 0, maps);
    }
    
    public int bfs(int x, int y, int[][] maps){
        Queue<int[]> que = new LinkedList<>();
    
        que.add(new int[]{x, y, 1});
        visited[0][0] = true;

        while (!que.isEmpty()) {
            int temp[] = que.poll();
            x = temp[0];
            y = temp[1];
            int count = temp[2];
            
            if (x == n-1 && y == m-1) {
                answer = count;
                break;
            }

            for (int i = 0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(maps[nx][ny] == 0) continue;
                if(!visited[nx][ny] && maps[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    que.add(new int[]{nx, ny, count+1});
                }
            }
        }

        return answer;
    }
}

• 전체를 다 찍어볼 필요가 없고 최단 거리를 찾아야하니 BFS 너비우선탐색 알고리즘을 사용한다.
• 정상 이동을 한 경우, 현재의 x,y 값과 기존카운팅+1 값으로 이루어진 배열을 큐에 넣고, 큐에 값이 없을 때 까지 뽑으며 로직을 반복한다.
• 작성예정

3. 피드백

• 대애충 구조 감은 오는데 요구사항에 맞게 짜는게 아직 어렵다. 이번에도 다른 코드 참고해서 분석ㅠㅠ

참고

• [DFS/BFS] 프로그래머스 1844번 게임 맵 최단거리(Java)
• [프로그래머스] 게임 맵 최단거리(Java 자바)