-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
강사님 안녕하세요! 깊이 우선 탐색 2 (백준 24480)에서 제공하는 풀이 코드에서 궁금한 점이 있어서 질문 드립니다!
24.04.28 23:21 작성 24.04.28 23:24 수정 조회수 91
1
import java.util.*;
import java.io.*;
class Main {
final static int MAX = 100000 + 10;
static ArrayList<Integer>[] graph;
static boolean[] visited;
static int N, M, R;
static int[] answer;
static int order;
public static void dfs(int idx){
visited[idx] = true;
answer[idx] = order;
order++;
for(int i = 0; i < graph[idx].size(); i++){
int next = graph[idx].get(i);
if(visited[next] == false)
dfs(next);
}
}
public static void main(String[] args) throws IOException{
// 0. 입력 및 초기화
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
// 1. graph에 연결 정보 채우기
graph = new ArrayList[MAX];
for(int i = 1; i <= N; i++)
graph[i] = new ArrayList<>();
visited = new boolean[MAX];
answer = new int[MAX];
order = 1;
for(int i = 0; i < M ;i++){
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
graph[x].add(y);
graph[y].add(x);
}
// 2. 오름차순 정렬
for(int i = 1; i <= N; i++)
Collections.sort(graph[i], Collections.reverseOrder());
// 3. dfs(재귀함수 호출)
dfs(R);
// 4. 출력
for(int i = 1; i <=N; i++){
bw.write(String.valueOf(answer[i]));
bw.newLine();
}
bw.close();
br.close();
}
}
위 제공 답안 코드에서
Collections.reverseOrder()
위 처럼 revserOrder()를 걸어주신게 잘못 작성된 내용 같은데 혹시 제가 잘못 확인한걸까요?
일단 해당 코드로 그대로 백준에 올리면 안되고 있는 상태입니다!
그리고 answer나 visited에 MAX를 넣으시는 이유가 궁급합니다! 방문정보나 answer의 경우 N+1로도 초기화가 가능하지 않나요?
혹시 더 복잡한 문제등에서 풀이의 간결성을 위해 필요한 방법일까요??
--
강의 너무 잘 보고 있습니다! 훌륭한 강의 찍어주셔서 감사합니다!
답변을 작성해보세요.
1
개발자로 취직하기
지식공유자2024.04.29
찬혁님 안녕하세요 🙂 알림 메일을 늦게 확인해서 이제야 답변 드려서 죄송합니다 ㅠ 많이 늦어졌네요.
댓글 남겨주신 대로 위 답안은 정답이 잘 나오는 것 같아요!
그리고 MAX와 N+1과 관련된 질문에 대해서는 찬혁님 말씀이 맞습니다! N+1로 해도 정답이 나오고, 이렇게 짜는 게 가장 효율적인 답변이 되는 것이 맞습니다.
다만 때에 따라서 N+2를 해야되는 경우도 생기고, N+100도 필요할 때가 있더라고요. 그런데 시험장에서 N+2인지 N+100인지를 의심하고 문제를 확인하기 까지는 시간이 꽤나 오래 걸리고, 실제로 이것 때문에 떨어지는 경우가 종종 발생하기 때문에, 그냥 문제에서 나오는 가능한 최댓값으로 시작하는 것이 가성비 좋은(?) 해결책이라 이렇게 작성하고 추천드리고 있습니다.
그런데 찬혁님께서 가능하시다면, 더 최적화 된 답변을 제출하는 게 당연히 더 좋은 코드이고 정답이 됩니다!
0
0
인프런 AI 인턴
2024.04.28
안녕하세요, 인프런 AI 인턴입니다.
최찬혁님의 질문에 대해 유사한 상황을 해결한 기존 답변을 참고하기 위해 관련된 정보를 찾아보았습니다. 다음 링크에서 비슷한 문제 상황에 대한 해결책을 제공하고 있습니다:
이 링크의 내용은 백준 문제 풀이에서 정렬 관련 궁금증에 대해 설명되어 있습니다. 특히, Collections.sort()
와 Arrays.sort()
의 사용법 및 차이점에 대해 설명하고 있으며, 문제 풀이에서 정렬 방식의 선택 기준에 대해서도 언급하고 있습니다. 이 내용은 질문 내용 중 정렬 방식에 대한 궁금증에 도움이 될 수 있을 것입니다.
질문에서 언급한 Collections.reverseOrder()
사용에 대한 의문은 정렬 방식에 대한 선택과 관련이 있습니다. 일반적으로 Collections.sort()
를 사용할 때는 오름차순 정렬이 기본입니다. 만약 내림차순 정렬이 필요한 경우 Collections.reverseOrder()
를 인자로 전달하여 내림차순으로 정렬할 수 있습니다. 문제의 조건이 내림차순 정렬을 요구하는지, 아니면 상황에 맞게 오름차순 정렬이 적합한지 확인이 필요할 것입니다.
MAX
를 사용하여 graph
, visited
, answer
배열의 크기를 정하는 부분은 백준과 같은 온라인 저지 시스템에서 특정한 최대 값으로 배열을 초기화하는 것이 일반적인 관행 중 하나입니다. 여기서 MAX
값을 사용하는 것은 주어진 문제의 최대 범위를 안전하게 커버하기 위한 것입니다. 그러나 최찬혁님께서 언급하신대로 N+1
로도 충분히 가능하다는 점에서, 실제 필요한 배열의 크기와 메모리 효율성을 고려하여 수정할 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
답변 3