inflearn logo
강의

Khóa học

Chia sẻ kiến thức

Bài kiểm tra lập trình Java - Chủ đề doanh nghiệp IT lớn

4. Giải pháp bài toán "Đường đi ngắn nhất trong mê cung (Tìm kiếm L)"

미로의 최단거리 통로

74

youngyou1324

11 câu hỏi đã được viết

0

안녕하세요 혹시 이 문제를 풀 때 꼭 dist배열을 만들어야 될까요? 제 코드를 아래 보여드립니다.

바로 L를 반환하게 만들었는데 이래도 괜찮을지요?

 

package org.youyk.inflearn.latest.sec07.Problem4;

import java.util.*;
class Solution1 {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    public int solution(int[][] board){
        int answer = 0;
        int[][] ch = new int[board.length][board[0].length];
        Queue<int[]> queue =new LinkedList<>();
        int n = board.length;
        int m = board[0].length;

        queue.add(new int[]{0,0});
        ch[0][0] = 1;
        int L=0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++){
                int[] poll = queue.poll();

                if(poll[0] == n-1 && poll[1] == m-1){
                    return L;
                }
                for(int j=0;j<4;j++){
                    int xx = dx[j] + poll[0];
                    int yy = dy[j] + poll[1];

                    if(xx>=0 && yy>=0 && xx<n && yy<m && board[xx][yy] ==0){
                        board[xx][yy] = 1;
                        queue.add(new int[]{xx,yy});
                    }
                }
            }
            L++;
        }

        return -1;
    }

    public static void main(String[] args){
        Solution1 T = new Solution1();
        int[][] arr={{0, 0, 0, 0, 0, 0, 0},
                     {0, 1, 1, 1, 1, 1, 0},
                     {0, 0, 0, 1, 0, 0, 0},
                     {1, 1, 0, 1, 0, 1, 1},
                     {1, 1, 0, 1, 0, 0, 0},
                     {1, 0, 0, 0, 1, 0, 0},
                     {1, 0, 1, 0, 0, 0, 0}};

        int[][] arr3={{0, 0, 1, 1, 1, 1, 1},
                      {0, 0, 1, 0, 0, 0, 0},
                      {1, 0, 1, 0, 0, 0, 0},
                      {0, 0, 1, 1, 0, 0, 0},
                      {1, 0, 0, 0, 0, 1, 0},
                      {0, 0, 1, 0, 0, 1, 0},
                      {0, 0, 1, 1, 1, 0, 0}};

        int[][] arr2={{1, 0, 0, 0, 1, 0, 0},
                {0, 1, 1, 1, 1, 1, 0},
                {0, 0, 0, 1, 0, 0, 0},
                {1, 1, 0, 1, 1, 1, 1},
                {1, 1, 0, 1, 0, 0, 0},
                {1, 0, 0, 0, 1, 0, 0},
                {1, 0, 1, 0, 1, 0, 0}};
        System.out.println(T.solution(arr));
        System.out.println(T.solution(arr2));
        System.out.println(T.solution(arr3));
    }
}

java 코딩-테스트

Câu trả lời 1

0

codingcamp

안녕하세요^^

네. dist 배열을 사용하지 않고, 레벨값인 L을 바로 리턴해도 됩니다.

비밀번호

0

65

1

과일 가져가기 이러한 경우에는 반례가 생기지 않나요?

0

161

2

cpu 스케줄링

0

105

2

외부 문제 질문

0

122

2

가장 많이 사용된 회의실

0

117

2

심사위원 문제 시간복잡도 질문

0

127

1

현관문 출입순서

0

96

1

집으로 이동 문제 코드

0

124

1

채점 사이트 개설

0

161

2

송아지를 잡자

1

110

1

다익스트라 + 환승횟수

0

135

2

문제풀이 해설 질문입니다.

0

124

2

"이동 횟수" 문제가 변형된다면?

0

156

2

예제 3번의 정답이 이해가 되지 않아요 선생님 ㅜㅜ

0

248

1

"비밀번호" 문제 확인 부탁드립니다!

0

170

1

최대 길이 연속수열 질문

0

192

1

잃어버린 강아지 문제 count 관련 질문있습니다

0

202

1

바둑대회 질문입니당

0

221

1

5. "최대 길이 바이토닉 수열" 에서 설명해주신 방법과 제가 직접 구현한 방법이 달라, 확인 한번 부탁드립니다

0

310

1

알파코드 풀이질문입니다

0

217

1

7번 비밀 번호 문제에 시간복잡도가 궁금합니다!

0

163

1

혹시 이렇게 작성해도 괜찮나요?

0

285

2

문제풀이 확인 부탁드립니다.

0

244

1

혼자서 푼 문제 확인 부탁드립니다.

0

299

1