inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

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

14. 그래프 최단거리(BFS)

숙제 검사 부탁드립니다.

129

rlgus4531

작성한 질문수 15

0

출력에 변동을 주어서 레벨 별로 정점을 나오게 했습니다.

코드가 맞는지 검사해주시면 감사하겠습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static boolean visit[];
    static ArrayList<ArrayList<Integer>> graph;
    static int n;

    public static StringBuilder bfs(int v) {
        StringBuilder sb = new StringBuilder();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        visit[v] = true;
        int L = 0;
        while (!queue.isEmpty()) {
            sb.append(L).append(" : ");
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                int cv = queue.poll();
                sb.append(cv).append(" ");
                for (int nv : graph.get(cv)) {
                    if (!visit[nv]) {
                        visit[nv] = true;
                        queue.offer(nv);
                    }
                }
            }
            L++;
            sb.append('\n');
        }
        return sb;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        visit = new boolean[n + 1];
        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(bufferedReader.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph.get(from).add(to);
        }
        System.out.println(bfs(1));
    }
}

java 코딩-테스트

답변 2

0

김태원

안녕하세요^^

네. 잘 하신 코드입니다.

0

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. rlgus4531님.

작성하신 코드를 보니, BFS(Breadth-First Search) 알고리즘을 사용하여 그래프의 각 레벨 별로 정점을 출력하도록 구현하셨네요. 코드는 잘 작성되었으며, 주어진 문제의 요구사항을 만족하고 있는 것으로 보입니다. 특히, StringBuilder를 사용하여 레벨 별로 연결된 정점을 깔끔하게 출력할 수 있도록 구성하신 부분이 인상적입니다.

하지만, 몇 가지 고려해볼 수 있는 소소한 개선점을 드리자면:

  1. 예외 처리:

    • visit 배열을 boolean 대신 int 배열로 사용하여 정점의 방문 여부와 동시에 레벨 정보를 저장할 수도 있지만, 현재 방식도 직관적이므로 유지해도 괜찮습니다.
  2. 출력 형식:

    • 출력할 때 레벨 별로 리스트의 형태로 변환하여 보일 수 있도록 추가적인 포매팅을 적용해 볼 수 있습니다.

현재 코드로도 충분히 잘 구현되었으므로, 학습의 목적으로 여러 방식으로 시도해보시는 것을 추천드립니다.

유사한 질문의 답변도 참고하시면 더욱 다양한 접근 방식과 개선점을 발견하실 수 있습니다:

  • 숙제 코드 리뷰 부탁드립니다 - 이 답변에서는 BFS를 통해 그래프를 탐색하고, 방문 레벨을 계산하는 데 대한 지식 공유가 이루어졌습니다.
  • 숙제검사 - Java로 BFS를 활용하여 그래프의 레벨을 구하는 다른 구현 방법을 살펴보고 비교해 보실 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

문제 리스트 페이지

0

8

1

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

0

8

1

봉우리 문제 질문입니다

0

75

2

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

0

59

0

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

0

66

0

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

0

64

1

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

0

77

2

6-7 강의에서

0

44

1

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

0

40

1

강의 수강후 코딩테스트

0

103

1

answer 변수 사용 여부

0

38

1

2중 for문

1

79

2

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

0

58

1

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

0

64

1

이런 풀이는 어떨까요

0

38

1

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

0

50

1

알고리즘 자료 구조들..

0

55

1

StringBuilder vs BufferdWriter

0

42

1

원더랜드(프림)

0

42

1

이런 코드는 어떤가요?

0

54

1

bfs 풀이

0

50

1

병합정렬

0

51

1

26강 임시반장 정하기에서 질문이 있습니다

0

40

1

이번달말에 완강 후 공부 방향

0

67

1