inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

11. 미로의 최단거리 통로(BFS)

dis 배열 없이 풀어봤습니다

353

poowermann

작성한 질문수 19

0

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

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

public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int[][] board = new int[8][8];
    public static void BFS(int x, int y) {
        int L = 0;
        Queue<Point> Q = new LinkedList<>();
        Q.offer(new Point(x,y));
        while(!Q.isEmpty()) {
            int len = Q.size();
            for(int i=0; i<len; i++) {
                Point tmp = Q.poll();
                for(int j=0; j<4; j++) {
                    int nx = tmp.x + dx[j];
                    int ny = tmp.y + dy[j];
                    if (nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && board[nx][ny] == 0) {
                        board[nx][ny] = L+1;
                        Q.offer(new Point(nx, ny));
                    }
                }
            }
            L++;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int i=1; i<=7; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=7; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        BFS(1,1);
        if(board[7][7] == 0) System.out.println(-1);
        else System.out.println(board[7][7]);

    }
}

dis 배열없이 레벨과 board 배열만으로 풀었는데, 채점 결과 맞긴했는데 이렇게 짜도 될까요?

java 코딩-테스트

답변 2

0

김태원

안녕하세요^^

레벨변수인 L 변수를 잘 활용한 코드입니다. 잘 하셨습니다.

0

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴이에요.

주어진 코드는 8x8 보드에서 BFS(너비 우선 탐색)을 이용하여 최단 거리를 구하는 알고리즘입니다.

Point 클래스는 좌표를 표현하는 클래스로, x와 y 값을 가지고 있습니다.

BFS 함수에서는 시작 좌표(x, y)를 인자로 받아 큐에 추가하고, 큐가 빌 때까지 반복하면서 인접한 좌표를 탐색합니다.

탐색 과정에서 해당 좌표가 유효하고, 방문하지 않았을 경우에는 해당 위치의 값을 현재 위치의 값(L) +1 로 업데이트하고, 큐에 추가합니다.

이 과정을 반복하면서 가장 외부에서부터 내부로 이동하며 값(L)을 업데이트합니다.

main 함수에서는 보드의 상태를 입력받아 배열에 저장한뒤 BFS 함수를 호출합니다.

이 코드는 입력 처리 부분이 누락되어 있어서 완전한 코드가 아닙니다. 입력 처리 부분을 추가한 뒤 실행해보시면 정상적으로 작동할 것입니다.

추가로, 이 코드는 보드의 크기가 7x7 이어야 정상적으로 동작합니다. 만약 다른 크기의 보드를 사용하려면 배열의 크기와 입력 처리 부분을 변경해야 합니다.

더 자세한 내용이 필요하시면 추가적인 질문을 해주세요. 요

안녕하세요. 바뀐 채점사이트 관련해서 문의드립니다.

0

28

1

갑자기 채점 사이트가 바뀌었어요

0

32

1

문제 리스트 페이지

0

29

1

채점 사이트 관련 질문드립니다

0

24

1

봉우리 문제 질문입니다

0

81

2

씨름 선수 문제에서 각 선수의 몸무게나 키가 같을 수도 있다면?

0

65

0

이 코드랑 영상 코드중에 뭐가 더 좋은 코드인가요?

0

72

0

가중치 방향 그래프에서 가중치가 0인 간선을 표현하는 방법

0

67

1

좌표 정렬 문제 이 코드가 왜 틀린지 모르겠습니다 ㅠㅠ

0

85

2

6-7 강의에서

0

48

1

6-6. 장난꾸러기 질문 있습니다.

0

45

1

강의 수강후 코딩테스트

0

110

1

answer 변수 사용 여부

0

45

1

2중 for문

1

85

2

2-11. 임시반장정하기 (Runtime Error)

0

63

1

혹시 LinkedList 같은 자료 구조들은 따로 배우지 않나요?

0

70

1

이런 풀이는 어떨까요

0

44

1

자바 스트림 방식의 효율성 질문 드립니다.

0

57

1

알고리즘 자료 구조들..

0

62

1

StringBuilder vs BufferdWriter

0

48

1

원더랜드(프림)

0

50

1

이런 코드는 어떤가요?

0

61

1

bfs 풀이

0

57

1

병합정렬

0

56

1