안녕하세요. 공부하다가 또 질문이 생겨 다시 한 번 질문 드립니다...리스트를 조회하는 것보다 딕셔너리를 조회하는 것이 더 빠를 거 같아서 문제의 그래프를 딕셔너리 자료형으로 바꿔주고 있는데요.제가 작성한 코드가 로컬에서 예시를 넣었을 때는 잘 되는데 백준에서는 틀린 답이라고 나옵니다..코드를 첨부하여 질문 드리고 싶은데, 멘토링 부분이 어디있는지 알려주시면 감사하겠습니다!

안녕하세요. 선생님 덕분에 멋진 강의를 듣고 있는 학생입니다.이제 유형 1을 다 수강했는데, graph를 초기화할 때 보통 N의 개수가 적으면 불리언 2차원 배열로 선언하고, N의 개수가 많으면 빈리스트로 구성된 2차원 리스트로 선언하는데요.그냥 모든 문제에 빈리스트로 구성된 2차원 배열을 선언하지 않는 이유가 N의 개수가 적으면 배열로 선언하고 조회하는 게 더 빠르기 때문인지 여쭤봐도 될까요?

안녕하세요! 강의 수강 중 질문이 있어 질문 드립니다.현재 이런식으로 코드를 작성했고, 백준 스타일에 맞춰 제출을 했는데 오답처리가 되었습니다. 디버깅 시에도 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(); } }  

안녕하세요 강사님 좋은 강의 감사합니다:)다름이 아니라, 출력문을 사용할 때 BufferedReader와 StringBuilder를 사용하는게 일반적으로 사용하는게 좋다고 알고있는데 해당 강의에서는 BufferedWriter를 사용하신 이유가 궁금해서 글을 작성하게 되었습니다. 감사합니다!

선생님 안녕하세요 유튜브에서 보고 오늘 처음 수강했는데 너무 귀에 잘 들어와서 재미있어요 bfs 강의도 올려주세용!다름이 아니고 바이러스 코드 중 이해가 안 되는 부분이 있어 질문 남깁니다!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)바이러스 코드에서 idx가 3이 되고 answer가 3이 되는 부분 까지는 이해를 했는데 idx가 3일 때 for문을 돌면 2는 이미 방문했기 때문에 if문은 7까지 true가 되지 못하고 종료되는 것 아닌가요? 다시 idx=2로 돌아가서 5를 방문하게 되고 1에서 6을 방문하게 되는 부분은 코드 어느 부분에서 이루어지는 건지 잘 모르겠어요ㅜㅜ

선생님 안녕하세요유형2로 들어와서 이제 visited를 2차원 배열로 만들기 시작하고 나서부터 계속 제가 헷갈리는게 선생님은 dfs 배열에 인자로 x,y가 아니고 y,x로 넘기시고 또 배열도 map[y][x]로 접근하시는 이유가 있으실까요? 보통 가로축을 x로 놓고 세로축을 y로 놓는 것으로 알고 있는데혼자 고민해 봤을때는 지금 문제들이 계속 가로 세로 길이가 다르더라구요 그래서 또 2차원 배열로 생각해보면 가로축이 column이 되고 세로축이 row가 되어서 그런건가 싶기도 하고.. 유형 2 파트와서 계속 이 부분이 헷갈리네요두서없는 질문이지만 궁금해서 여쭤봅니다!감사합니다

선생님 안녕하세요!강의 너무 잘 듣고 있습니다!제가 2644번 문제를 혼자 아래 코드로 풀어보았는데저는 선생님께서 count변수를 dfs 함수 인자에 준 것과는 다르게 처음부터 전역변수로 설정해서 조건이 맞으면 count 변수를 1씩 증가시키는 방향으로 작성을 했는데요.이렇게 하니까 백준에서는 틀렸다고 나오더라구요.둘 다 if문 안에서 조건이 맞으면 카운트 변수를 1씩 증가시키는건 같은거라고 생각이 드는데 (물론 다르겠지만..)왜 카운트 변수를 인자로 넘겨줘야할까요? 감사합니다!  

// 1. dfs 실행 int answer = 0; for(int i = 1; i <= N; i++) { for(int j = 1; j <= M; j++) { if(visited[i][j] == false) dfs(i, j); answer++; } }안녕하세요.dfs문을 호출한 이후에 answer++;를 했을 때는, 주어진 값과 다르게 나오는데, 어떤 부분에서 차이가 있는지 궁금합니다.. 감사합니다!

안녕하세요. 해당 문제의 코드를 다음과 같이 짰는데, 출력하면 항상 0이 출력됩니다.강의에 나온 부분과 거의 동일한데, 어느 부분에서 오류가 발생하는지 잘 모르겠습니다. 감사합니다.import java.util.*; import java.io.*; class Main { final static int MAX = 50 + 10; static boolean[][] map; static boolean[][] visited; static int W, H; static int[] DirY = {-1, -1, -1, 0, 0, 1, 1, 1}; static int[] DirX = {-1, 0, 1, -1, 1, -1, 0, 1}; public static void dfs(int y, int x) { visited[y][x] = true; for(int i = 0; i < 8; i++) { int newY = y + DirY[i]; int newX = x + DirX[i]; if(map[newY][newX] && visited[newY][newX] == false) { dfs(newY, newX); } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // 0. 입출력 while(true) { StringTokenizer st; st = new StringTokenizer(br.readLine()); W = Integer.parseInt(st.nextToken()); H = Integer.parseInt(st.nextToken()); // 마지막 입력 값이 0이면 while 문 빠져나오기 if(W == 0 && H == 0) break; map = new boolean[MAX][MAX]; visited = new boolean[MAX][MAX]; for(int i = 1; i <= H; i++) { st = new StringTokenizer(br.readLine()); for(int j = 1; j <= W; j++) { map[i][j] = (Integer.parseInt(st.nextToken()) == '1') ? true : false; } } int answer = 0; for(int i = 1; i <=H; i++) { for(int j = 1; j <=W; j++) { if(map[i][j] && visited[i][j] == false) { dfs(i, j); answer++; } } } bw.write(String.valueOf(answer)); bw.newLine(); } bw.close(); br.close(); } }

알고리즘 수업 깊이우선탐색2의 자료가 올라와 있는 것 같습니다. 

 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번의 테스크케이스를 만드는 이유는 무엇인가요?그리고 단순히 궁금해서 여쭤보는데 가로와 세로 순서로 입력받고 코드를 실행하는것이 아닌 거꾸로 세로와 가로 순으로 실행하는지 궁굼합니다.답변 부탁드립니다. 감사합니다.