import java.util.*; import java.io.*; public class jelly { static int size; static int[][] map; static boolean[][] visited; // //size,size도달하면 HaruHaru, 아니면 hing public static void dfs(int y, int x){ visited[y][x] = true; if(y == size && x == size) return; int n = map[y][x]; if( (x + n) <= size && !visited[y][x+n]) dfs(y,x+n); if( (y + n) <= size && !visited[y+n][x]) dfs(y+n,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)); size = Integer.parseInt(br.readLine()); int Max = size +10; map = new int[Max][Max]; visited = new boolean[Max][Max]; for(int i = 1; i <= size; i ++){ StringTokenizer st = new StringTokenizer(br.readLine()); for(int j = 1; j <= size; j ++){ map[i][j] = Integer.parseInt(st.nextToken()); } } dfs(1,1); if(visited[size][size]){ System.out.print("HaruHaru"); }else System.out.print("Hing"); bw.close(); br.close(); } }

일반적으로 수학 좌표계로 생각하면 (2,3) 이라했을때 x축이 2, y축이 3이지만 우리는 맵이나 2차원 리스트로 생각하게됐을떄array[row][col]이여서 이게 반대가되고, 그래프로 치면 정점에 간선이 연결된거기 때문에 이러는것 같은데   graph[y+1][x+1] = true;지난 배추문제부터 이런건 이해가 가는데 static int[] dirY = {-1, 1, 0, 0}; static int[] dirX = {0, 0, -1, 1}; static void dfs(int y, int x){ visited[y][x] = true; for(int i = 0; i < 4; i ++){ int newY = y + dirY[i]; int newX = x + dirX[i]; if(graph[newY][newX] && !visited[newY][newX]) dfs(newY,newX); } }  이게 너무 이해안갑니다. 그냥 파라미터도 x, y로 하고 visited[x][y] , dirX = {-1,1,0,0} dirY = {0,0,-1,1} 이렇게 하면 안되나요? 생각하기가 너무 복잡해요

안녕하세요. 기존처럼 dfs함수내에서 함수가 실행될때마다 answer++를 해서 조건에 일치 할 떄 그냥 answer를 출력하게해도 될것같은데count라는 파라미터는 answer를 -1로 초기화를 해놨기 때문에 넣는건가요? 아니면 answer로 하면 단순 dfs 함수 호출 횟수를 늘리는거고, 이 문제의 본질은 트리의 depth를 물어보는거가 되는거고 그래서 count로 depth를 알려주는건가 싶습니다

그 전 문제들까지는 graph를 채울 때조건문에서 i < M으로 간선의 개수로 했는데 왜 이번문제에서는 i <=N으로 하나요? 전에 2차원 배열을 가득 채우고 할 때 i<=N은 dfs 함수에서 사용했었는데..이해를 못하겠스빈다

혹시 이런 유형에서 N 이 크면 ArrayList 를 사용해야하는데 2차원 배열 어레이 리스트 사용은 어떤식으로 하나요??

안녕하세요! 24년도부터 강의 잘 보고 있습니다!덕분에 알고리즘이 재미있어졌습니다!이직준비를 위해 강의를 연장했는데, 다른 강의는 언제쯤 나오나요?너무 너무 기다리고 있습니다~그리디 부탁드립니당 ㅎㅅㅎ 강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :)

강의 정말 잘 듣고있습니다. DFS 너무 어려웠는데 저에게 한 줄기 빛 같은 존재십니다..! 원본 문제가 바뀐것같기도 한데,13565번 백준 원본을 보면 M, N 순서대로 입력을 받는 것 같습니다. M이 행에 해당되고, N이 열에 해당이 되어서 전반적으로 반대가 되어야하고,강의에서 말씀 주신 이 부분도defdfs(y, x): global visited, map_, answer, N if y == N: answer = Truereturny == M으로 바뀌어야할 것 같은데 맞을까요?

침투/섬의개수 질문드립니다.  침투 문제에서는 연속된 숫자가 들어와서 row=input() 이렇게 표현 하셨는데 연속된 숫자가 들어올거라는 것을 어떻게 유추할수 있을까요? 섬의개수 문제에서는 침투와 달리 row=list(map(int,input().split())) 이렇게 표현하셨는데, 침투랑 동일하게 row=input()으로 표현해도 되는거 아닌가요? 연결정보 채우는거에 대한 언급을 어떻게 찾는지 궁금합니다    

강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 🙂좋은 강의 감사합니다.노드간의 거리를 계산하는 유형을 정리하실 때 "DFS의 인자에 count 변수를 전달하는 방식" 에 대해서 말씀해주셨습니다. 제가 이해한 바로는 사이클이 없는 구조, 즉 u와 v간의 경로가 하나만 존재할 경우에만 유효하다는 생각이 듭니다. 혹시 제가 오해한 부분이 있다면 알려주시길 바랍니다.감사합니다. 

import java.util.*; public class Main { static int N; static ArrayList<Integer>[] graph; static ArrayList<Integer>[] graphReverse; static ArrayList<Integer> orderNode = new ArrayList<>(); static ArrayList<Integer> reverseOrderNode = new ArrayList<>(); static boolean[] visited; public static void dfs(int idx) { visited[idx] = true; orderNode.add(idx); for(int next : graph[idx]) { if(!visited[next]) { dfs(next); } } } public static void dfsReverse(int idx) { visited[idx] = true; reverseOrderNode.add(idx); for(int next : graphReverse[idx]) { if(!visited[next]) { dfsReverse(next); } } } public static void main (String[] args) { Scanner input = new Scanner(System.in); boolean isReverseOrder = true; boolean isOrder = true; N = input.nextInt(); graph = new ArrayList[N+1]; graphReverse = new ArrayList[N+1]; visited = new boolean[N+1]; for(int i = 1; i <= N; i++) { graph[i] = new ArrayList<>(); graphReverse[i] = new ArrayList<>(); } for(int i = 0; i < N-1; i++) { int x = input.nextInt(); int y = input.nextInt(); graph[x].add(y); graph[y].add(x); graphReverse[x].add(y); graphReverse[y].add(x); } input.nextLine(); String[] orderStr = input.nextLine().split(" "); for(int i = 1; i <= N; i++) { Collections.sort(graphReverse[i], Collections.reverseOrder()); } for(int i = 1; i <= N; i++) { if(!visited[i]) { dfs(i); } } visited = new boolean[N+1]; for(int i = 1; i <= N; i++) { if(!visited[i]) { dfsReverse(i); } } for(int i = 1; i <= orderStr.length; i++) { // System.out.println(orderStr[i-1]); if(reverseOrderNode.get(i-1) != Integer.parseInt(orderStr[i-1])) { isReverseOrder = false; } if(orderNode.get(i-1) != Integer.parseInt(orderStr[i-1])) { isOrder = false; } } if(isOrder || isReverseOrder) { System.out.println(1); } else { System.out.println(0); } } }안녕하세요 강사님,,덕분에 비전공자인 제가 dfs 26개의 문제를 풀고 골드에 진입했습니다.정말 너무나도 감사합니다.하지만 골드에서 막히는게 많은데 이번 문제는 도저히 검색하고,반례를 다 찾아보고 해봐도 해결이 되지않아 답답한 마음에 여기에 글을 적습니다..문제는 백준 https://www.acmicpc.net/problem/16964 DFS 스페셜 저지입니다.제가 푼 방법은 2개의 그래프를 만든 후,1개는 sort, 다른 한개는 reverseOrder을 하여,정점 방문 순서를 2개 구한 후,마지막에 제시되는 4개의 숫자와 비교하여 출력하는 방식으로 코드를 작성하였습니다.하지만 제가 찾아본 모든 반례와 백준에서 제공되는 예제들은 통과되는데,6%에서 틀렸다고 나옵니다.다른문제로 곤란하게 해드렸다면, 바로 글 삭제하겠습니다.감사합니다.

재귀함수에서 보통 베이스 케이스에 리턴이 있는 경우를 많이 봤는데 베이스 케이스 부분에 return 안쓰는거랑 return 쓰고 그 뒤에 비워놓는거랑 같은 건가요??예를 들어 이 두개가 같은건가요? (함수 안 부분 띄어쓰기해도 질문등록하면 다 왼쪽으로 정렬되서 보이네요ㅠ)함수1: def function()for _ in range(N):... 함수 2: def function()return for _ in range(N):...

안녕하세요 🙂 bfs 에서 질문이 있는데 왜 프린트(print(idx, end = ' ')를 for loop 안에서 queue.append(i) 한 다음 프린트하지 않고 큐에서 팝할때 프린트 하나요?

영상 2:53왜 연결된 노드중에 가장 작은 노드부터 방문해야 하나요??

안녕하세요!! 먼저 좋은 강의 너무 감사드립니다 이해가 너무 잘돼요 ㅜㅜ전에 글중에서 올해 하반기에 다른주제 강의들도 올리실 계획 있다고 본 것 같은데 (DP, BFS 등등) 혹시 구체적인 일정 나온게 있나요? 나오면 꼭 결제하고 싶습니다! 감사합니다^-^

import java.util.*; public class Main { static int N, M, R; static int[] answer; static ArrayList<Integer>[] graph; static boolean[] visited; static int order = 1; public static void dfs(int idx) { visited[idx] = true; answer[order] = idx; order++; for(int i = 0; i < graph[idx].size(); i++) { if(!visited[graph[idx].get(i)]) dfs(graph[idx].get(i)); } } public static void main(String[] args) { Scanner input = new Scanner(System.in); N = input.nextInt(); M = input.nextInt(); R = input.nextInt(); answer = new int[N+1]; visited = new boolean[N+1]; graph = new ArrayList[N+1]; for(int i = 1; i <= N; i++) { graph[i] = new ArrayList<>(); } for(int i = 0; i < M; i++) { int x = input.nextInt(); int y = input.nextInt(); graph[x].add(y); graph[y].add(x); } for(int i = 1; i < graph.length; i++) { Collections.sort(graph[i], Collections.reverseOrder()); } dfs(R); for(int i = 1; i < answer.length; i++) { System.out.println(answer[i]); } } }이렇게 구현한 경우, 틀렸다고 나오는데,ide로 돌리고 출력해보면14320으로 정상 출력되는데.. 이유를 모르겠습니다ㅠㅠ!선생님이 작성해주신 코드answer[idx] = order; order++; 제가 작성한 코드answer[order] = idx; order++;이렇게해도, 제가 하나씩 디버깅해서 따라가보면, 정답과 맞게 나오는데, 틀렸다고합니다.. !

이렇게 구현한 경우, 틀렸다고 나오는데,ide로 돌리고 출력해보면14320으로 정상 출력되는데.. 이유를 모르겠습니다ㅠㅠ!

//2. 오름차순 정렬 -> 내림차순 정렬로 수정하셔야 할 듯 ^^

package com.study.book.graph; import java.util.*; import java.io.*; public class Baekjoon24479 { private static ArrayList<Integer>[] adjList; private static boolean[] visited; private static int[] answer; private static int visitOrder; 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()); int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int R = Integer.parseInt(st.nextToken()); adjList = new ArrayList[N + 1]; for (int i = 0; i < adjList.length; i++) { adjList[i] = new ArrayList<>(); } for (int i = 1; i < N + 1; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); adjList[x].add(y); adjList[y].add(x); } for (ArrayList<Integer> list : adjList) { Collections.sort(list); } visited = new boolean[N + 1]; answer = new int[N + 1]; visitOrder = R; dfs(R); for (int i = 1; i <= N; i++) { bw.write(String.valueOf(answer[i])); bw.newLine(); } br.close(); bw.close(); } private static void dfs(int now) { visited[now] = true; answer[now] = visitOrder; visitOrder++; for (int next : adjList[now]) { if (!visited[next]) { dfs(next); } } } } 안녕하세요 개취님!알고리즘 강의 잘 듣고 있습니다 ㅎㅎ다름이 아니라, 위 코드로 문제를 풀고 테스트 코드 또한 정상적으로 통과하여 백준에서 제출을 진행했는데, 단순히 "틀렸습니다" 라고만 나와서 어떤 점에서 문제가 있는지 정상적으로 파악이 안되서 문의드립니다!한번 확인 후 피드백 주시면 감사하겠습니다.

강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 🙂 graph 만들때 boolean[][] 으로 만드는 경우랑 int[][] 나 ArrayList<Integer>[] 로 만드는 기준이 어떻게 되나요?

dfs 영상을 쭉 보고있는데요 ㅎ문제들 마다 규칙이거의 무조건적으로 visited 와 2차원 graph 가 생성이 되나요 ??visited = []graph = [[False] *MAX for _ in range(MAX)]2. MAX 를 두시는 이유가 뭔가요 ??