import java.io.*; import java.util.*; public class Main { static final int MAX = 100000 + 10; static ArrayList<Integer>[] graph; static boolean[] visited; static int[] answer; static int N, M, R; 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]) { 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()); 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 j = 0; j < N; j++) { Collections.sort(graph[j], Collections.reverseOrder()); } // 3. 재귀함수 출력 dfs(R); for (int k = 1; k <= N; k++) { bw.write(String.valueOf(answer[k])); bw.newLine(); } br.close(); bw.close(); } }해당 코드를 구현했는데, 널 포인터 에러가 뜹니다..! 어떤 부분에서 잘못됐는지 피드백 받고자 질문드립니다!감사합니다

선생님 안녕하세요일단 너무 만족스러운 강의 준비해주셔서 감사하고 정말 돈이 하나도 아깝지 않은 강의입니다. DFS 강의 말고도 다른 알고리즘 강의도 준비해주시면 너무 좋을것 같아요 ㅠㅠ 아무튼 질문은요,선생님 강의를 듣고 아래처럼 제가 코드를 짰는데선생님 코드랑 몇번을 비교해도 다른 점이 보이질 않는데 백준에서 제출했을 때 계속 메모리 초과라고 나옵니다.혹시나 제가 바보같은 실수를 했을 수 있으니 미리 사과드립니다 ㅠㅠ!! 감사합니다 import sys sys.setrecursionlimit(10**6) N, M = map(int, sys.stdin.readline().split()) MAX = 1000 + 10 graph = [[False] * MAX for _ in range(MAX)] visited = [False] * MAX answer = 0 for _ in range(M): u, v = map(int, sys.stdin.readline().split()) graph[u][v] = True graph[v][u] = True def dfs(idx): visited[idx] = True for i in range(1, N + 1): if not visited[i] and graph[idx][i]: dfs(i) for i in range(1, N + 1): if not visited[i]: dfs(i) answer += 1 print(answer)

def dfs(idx): global visited, graph, answer visited[idx] = True answer += 1 for i in range(1,N+1): if not visited[i] and graph[idx][i]: dfs(i)이와 같은 dfs 재귀함수에서 dfs(1)이 맨 처음에 실행되고 조건에 따라 계속 재귀되는데 마지막 dfs(7)까지 간다고 했을 때 range(1,N+1)에 범위는 넘지만 dfs(8), dfs(9), ... 이런식으로 계속 코드가 돌아버릴 수도 있는 것이 아닌가요??DFS와 재귀함수가 처음이여서 질문을 명확하게 못 작성한 것 같네요.return이라는게 필요한 것이 아닌지, 재귀함수에 종료조건이 어떻게 되는 것인지 궁금해서 여쭤봅니다.답변 기다리겠습니다. 감사합니다

저는 맵2차원배열을 boolean으로 사용하고싶어아래와 같이 코드를 작성해봤습니당... 예제입력1. 은 답이 잘나오는데 나머지는 왜 틀리게 나올까용... package DFS; import java.io.*; import java.util.StringTokenizer; import java.util.Vector; /* 바닥 장식 https://www.acmicpc.net/problem/1388 */ public class B1388 { final static int MAX =50+10; static boolean [][] map; static boolean [][] visited; static int M,N; static void dfs(int y, int x){ visited[y][x]=true; if (map[y][x]==true&& map[y][x+1]==true){ dfs(y, x + 1); } if(map[y][x]==false&&map[y+1][x]==false){ dfs(y+1,x ); } } 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()); map = new boolean[MAX][MAX]; visited = new boolean[MAX][MAX]; //맵정보 반영 for (int i = 1; i <= N; i++) { String str = br.readLine(); for (int j = 1; j <= M; j++) { map[i][j] = (str.charAt(j - 1) == '-' ? true : false); } } //dfs int answer=0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if(map[i][j]&&visited[i][j]==false){ dfs(i,j); answer++; } } } bw.write(String.valueOf(answer)); bw.flush(); bw.close(); } } 

아래 코드에서 왜DFS를 수행할때 MAP[1] 이 왜 고정인지 잘모르겠습니다... //맵정보 저장 for (int i = 1; i <= N; i++) { String str = br.readLine(); for (int j = 1; j <= M; j++) { map[i][j] = (str.charAt(j - 1) == '0' ? true : false); } } //dfs for (int j = 1; j <= M; j++) { if (map[1][j]) { // 왜 map[1][j] 일까요 dfs(1, j); // 또한 dfs도왜 1,j 일가요 } }

강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :) 안녕하세요!혹시 Main class에 static으로 변수를 선언하는 이유가 궁금합니다!또한, 백준에서 public static void main 에 선언했을 때와 차이가 궁금합니다..!! 감사합니다

제가 경험이 부족해서 그런 것 같은데요, 이 문제는 'x < y'라는 조건이 없다면 DFS로 풀 수 있는 문제가 아닌 것 같다는 생각이 들었습니다.https://www.acmicpc.net/problem/2644에서 '입력' 파트를 보면, '번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.'라고만 나와있습니다. 즉, 'x < y'라는 조건이 주어져 있지 않습니다. 부모 노드 번호가 자식 노드 번호보다 작다는 조건이 주어져 있지 않는 것입니다.그래서 저는 이 문제가 DFS로 풀리는 문제가 아닐 것 같다고 생각했었습니다. 위 그림에서는 노드2의 부모가 1이지만, 2보다 값이 큰 3이 될 수도, 4가 될 수도 있을 것이라 생각했습니다. 따라서 노드2를 방문한 이후에, 노드2와 연결된 노드 중 아직 방문하지 않은 노드들 중 어떻게 부모 노드를 찾아야하지? '부모 노드 번호 < 자식 노드 번호'라는 조건이 없으면, 부모 노드를 찾을 수 없을 것 같은데?하는 생각이 들었습니다. 문제에서 x<y라는 조건이 없는 것 같은데, 어떻게 '나와 연결되어 있고 아직 방문하지 않은 노드 중 번호가 가장 작은 노드를 방문해야겠다'는 생각을 하신 것인지 궁금합니다..

문제(https://www.acmicpc.net/problem/1260)에 다음과 같은 조건이 있는데, 이게 무슨 의미인가요..?어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.

graph, visited의 사이즈를 다음 코드와 같이 노드 개수에 맞게 (n+1)로 하면 되겠다고 생각했는데, 노드 개수의 최댓값인 1000을 이용해 사이즈를 정하신 이유가 무엇인가요??graph = [[False]*(n+1) for _ in range(n+1)] visited = [False]*(n+1)  

T, M, N, K를 입력받아 사용한다고 하셨는데, M과 K는 각각 세로와 가로값으로 입력받고, K는 배추의 위치라는것을 알았습니다. 근데 T는 테스크케이스 라는 언급을 하셨고 코드에서도 아래와 같이 작성되있습니다.while (T-- > 0) { StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(br.readLine()); N = Integer.parseInt(br.readLine()); K = Integer.parseInt(br.readLine()); // map 정보 // dfs 수행 .... }2번의 테스크케이스를 만드는 이유는 무엇인가요?그리고 단순히 궁금해서 여쭤보는데 가로와 세로 순서로 입력받고 코드를 실행하는것이 아닌 거꾸로 세로와 가로 순으로 실행하는지 궁굼합니다.답변 부탁드립니다. 감사합니다.

안녕하세요.위의 코드는 제가 강의를 듣기 전에 작성한 코드입니다.백준에서 2가지로 주어진 테스트 케이스는 통과하는데 코드를 제출하면 틀렸다고 나옵니다.코드 어디가 잘못된지를 모르겠습니다.그리고 강의에서는 dfs 함수에 start 변수만 넣지 않고 count 변수도 넣으셨는데 count변수를 매개변수로 넣지 않고 코드를 작성하는 방법이 있는지 궁금하고, 이러한 방법이 없다면 왜 매개변수로 count 변수를 넣어줘야 하는걸까요? 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); M = Integer.parseInt(br.readLine()); graph = new boolean[N][N]; visited = new boolean[N]; int x, y; for (int i=0; i<=M; i++) { StringTokenizer tokenizer = new StringTokenizer(br.readLine()); x = Integer.parseInt(tokenizer.nextToken())-1; y = Integer.parseInt(tokenizer.nextToken())-1; graph[x][y] = true; graph[y][x] = true; } dfs(0); System.out.println(answer - 1); br.close(); } void dfs(int index) { visited[index] = true; IntStream.range(0, M).forEach(i -> { if (!visited[i] && graph[index][i]) dfs(i); }); answer++; }위에처럼 저는 +1을하지않고(그래프에 0인덱스들은 사용을 안한다고 생각해서요.)대신 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수를 입력받을 때 -1을해줘서 처리했는데요.예제입력은 정상처리 되나 실제 제출해보면 런타임 에러 (ArrayIndexOutOfBounds)가 발생합니다. +1을 해줘야하는거같은데... 제가 생각한 배열사이즈, -1로 입력받기가 잘못된걸까요?

안녕하세요 저는 강사님 강의로 공부하고 파이썬으로 코테를 준비하고 있습니다. 저와 같은 상황에 계신분들과 공유하고 싶어 글을 올립니다. 파이썬 풀이에서 부족한 부분 알려주시면 수정하겠습니다.~import syssys.setrecursionlimit(10 ** 6)N, M = map(int, sys.stdin.readline().split())MAX = 1000 + 10graph = [[False for in range(MAX)] for in range(MAX)]visited = [False for in range(MAX)]for in range(M):x, y = map(int, sys.stdin.readline().split())graph[x][y] = True graph[y][x] = Truedef dfs(idx):visited[idx] = True for j in range(1, N + 1):if not visited[j] and graph[idx][j]:dfs(j)cnt = 0for i in range(1, N + 1):if not visited[i]:dfs(i)cnt += 1print(cnt)

Main 클래스 안에서MAX 변수에 대해 굳이 final로 초기화 하는 이유가 무엇일까요?

저번 수업도 그렇고...반복문 작성할 때 아 이거는 i<N인가? M인가? 이게 햇갈리는데, 뭐 좋은 방법 없을까요?

혹시 구현문제의 대한 강의는 올라오지 않을까요?다음 예정된 강의는 어떤 종류의 알고리즘인지 궁금합니다.

정점의 수 N은 100,000개 까지인데이를 담는 배열의 최대 크기인 MAX가 왜1,000,000로 잡았는지 궁금합니다(+ 10은 연산 때문에 그렇다고 하셨던것같고)

안녕하세요! 강의를 다 듣고, 블로그에 남겨주신 문제들을 풀어보고 있습니다.'백준 1325 효율적인 해킹 문제'인데, 시간 초과가 나는 기준을 이해하지 못해서 질문드립니다!import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static int dfs(int idx) { visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } return count; } 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()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } } 이렇게 작성을 하니 자꾸 시간 초과가 나와서 chat gpt에 질문해보니 메모이제이션을 사용하면 해결할 수 있다는 답변이 나왔습니다. 이미 visited를 사용해 이미 방문한 노드를 다시 방문하지 않는데, 메모이제이션을 사용하는게 의미가 있을까 싶었지만 일단 코드를 변경해봤습니다.import java.io.*; import java.util.*; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static int[] memo; private static int dfs(int idx) { if (memo[idx] != -1) { return memo[idx]; } visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } memo[idx] = count; return count; } 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()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; memo = new int[N + 1]; Arrays.fill(memo, -1); int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } } 이렇게 작성하니까 시간 초과가 나지는 않는데, 어느 테스트 케이스에서 memo 배열에 저장된 값을 사용하는건지 알 수 있을까요?그리고 혹시 강사님은 이 문제를 이것과 다르게 푸셨을까요?? ++ 추가로 배열 대신 HashMap을 사용해도 시간 초과가 납니다... ㅠimport java.io.*; import java.util.*; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static Map<Integer, Integer> map; private static int dfs(int idx) { if (map.get(idx) != null) { return map.get(idx); } visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } map.put(idx, count); return count; } 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()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; map = new HashMap<>(); int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } }

안녕하세요! 선생님이 알리켜주신대로 한번 다시 하다가 저는 bfs 메소드에서 ++count로 했는데 count+1과 무슨 차이가 있을까요?? 백준에서 돌려봤더니 틀렸다고 떠요!  private static void dfs(int start, int count) { visited[start]=true; if(start==end){ answer=count; return; } for(int i=1;i<=N;i++){ if(visited[i]==false&&graph[start][i]){ dfs(i,++count); } } }

안녕하세요, 강의 잘 듣고 있습니다. map 정보 반영에서 map[y+1][x+1] = true; 라고 하셨는데, map[x+1][y+1]도 true값을 넣어야 하지 않을까요?빠른 답변 부탁합니다.감사합니다.