-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
안녕하세요 11724번 질문드려요!
23.11.17 00:30 작성 조회수 162
2
안녕하세요! 강의 수강 중 질문이 있어 질문 드립니다.
현재 이런식으로 코드를 작성했고, 백준 스타일에 맞춰 제출을 했는데 오답처리가 되었습니다. 디버깅 시에도 1번예제
6 5 1 2 2 5 5 1 3 4 4 6
이걸 입력했을 때 2가 나오는 것이 아닌 dfs를 호출시 if절에서 전부 vistied[i] 부분이 false처리가 되어서 입력한 크기인 6이 answer로 계속 출력되고 있습니다.
어느 부분이 문제여서 계속 찾고 있지만 발견하지 못하여 질문드립니다.package algorithmstudy.dfs; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class boj11724 { final static int MAX = 1000 + 10; static boolean[][] graph; static boolean[] visited; static int N, M; static int answer; static void dfs(int idx) { visited[idx] = true; for (int i = 1; i <= N; i++) { if (!visited[idx] && graph[idx][i]) { dfs(i); } } } public static void main(String[] args) throws IOException { 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()); // 1. graph에 연결 정보 채우기 graph = new boolean[MAX][MAX]; visited = new boolean[MAX]; for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()); int v = Integer.parseInt(st.nextToken()); graph[u][v] = true; graph[v][u] = true; } for (int i = 1; i <= N; i++) { if (!visited[i]) { answer++; dfs(i); } } bw.write(String.valueOf(answer)); br.close(); bw.close(); } }
답변을 작성해보세요.
2
개발자로 취직하기
지식공유자2023.11.17
이정우님 안녕하세요 🙂
작성해주신 코드는 99% 정답인데 딱 하나 잘못된 것 같습니다!
for (int i = 1; i <= N; i++) {
if (!visited[idx] && graph[idx][i]) {
dfs(i);
}
}
DFS 함수 내부에서 다음 DFS를 재귀적으로 호출하는 이 부분에서 첫 번째 조건이 잘못되었습니다.
반복문위에서 visited[idx] = true라고 값을 담아주고, 조건문에서 !visited[idx]를 보고 있기 때문에 재귀 호출이 절대 이뤄지지 않는 코드가 됐습니다.
원래 의도했던 것은 "다음 노드를 방문한 적이 없는지"를 확인하고 싶었던 것이기 때문에 !visited[i]를 확인하도록 다음과 같이 수정하면 정답이 나올 거에요!
for (int i = 1; i <= N; i++) {
if (!visited[i] && graph[idx][i]) {
dfs(i);
}
}
이 외에도 혹시 궁금한 점이 있으면 알려주세요! 공부 화이팅하세요 :)
답변 1