23,100원
다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
강사님 안녕하세요! 깊이 우선 탐색 2 (백준 24480)에서 제공하는 풀이 코드에서 궁금한 점이 있어서 질문 드립니다!
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로도 초기화가 가능하지 않나요? 혹시 더 복잡한 문제등에서 풀이의 간결성을 위해 필요한 방법일까요?? --강의 너무 잘 보고 있습니다! 훌륭한 강의 찍어주셔서 감사합니다!
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
촌수 계산
count라는 매개변수를 같이 전달해주기 보다 dfs가 호출될 때마다 answer를 넣어주는 방식으로 풀어봤는데 왜인지 end 값을 찾았을 때 return이 적용이 안되는 거 같습니다. 혹시 어떤 문제가 있는지 봐주실 수 있나요? import java.util.*; import java.io.*; class Main { static int N, start, end, M; static boolean[] visited; static ArrayList<Integer>[] graph; static int answer = -1; private static void dfs(int i) { if (i == end) { System.out.println("end: " + end); return; } visited[i] = true; for (int j = 0; j < graph[i].size(); j++) { int next = graph[i].get(j); if (visited[next] == false) { System.out.println("next: " + next); dfs(next); answer++; } } } public static void main(String[] args) throws IOException{ // 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); N = Integer.parseInt(br.readLine()); // 노드의 개수 StringTokenizer st = new StringTokenizer(br.readLine()); start = Integer.parseInt(st.nextToken()); // 시작 노드 end = Integer.parseInt(st.nextToken()); // 끝 노드 System.out.println(end); M = Integer.parseInt(br.readLine()); // 간선의 개수 visited = new boolean[N+1]; // graph 선언 후 초기화 graph = new ArrayList[N+1]; for (int i = 1; i <= N; i++) { graph[i] = new ArrayList<>(); } for (int i = 1; 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); } System.out.println(Arrays.toString(graph)); // dfs 호출 dfs(start); System.out.println(answer); bw.close(); br.close(); } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
연결 요소의 개수 (백준 11724)
강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :)1. 저번 강의에서 풀이하신 것처럼 이번 강의에도 재귀 함수의 depth를 그려보았는데 맞나요?2. 혹시 CS 면접 관련해서 대략 어떻게 준비해야 하는지 질문 드려도 되나요?
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
백준 24479 문제 시간 초과 질문 드려요
안녕하세요 백준에서 테스트 결과 시간 초과 오류가 납니다 . 확인 한번 가능할까요?import java.io.*; import java.util.*; public class Main { static final int MAX = 100000 + 10; static int N, M, R; static ArrayList<Integer>[] graph; static boolean[] visited; 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 { 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); } for (int i = 1; i <= N; i++) { Collections.sort(graph[i]); } dfs(R); for (int i = 1; i <= N; i++) { bw.write(String.valueOf(answer[i])); bw.newLine(); } bw.close(); br.close(); } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
백준 실행시 틀립니다.
안녕하세요 강사님. 문제를 풀고 백준에 제출했을 때 계속 오답으로 나와 질문 드립니다..제가 봤을 때 강사님 코드랑 거의 비슷하게 수정까지 한 것 같은데.. 어떤 부분이 잘못되었는지 확인 한번 부탁드립니다.import java.io.*; import java.util.StringTokenizer; public class Main { final static int MAX = 50 + 10; static boolean map[][]; static boolean visited[][]; /* static int dirY[] = {1, 1, 1, 0, 0, -1, -1, -1}; static int dirX[] = {-1, 0, 1, -1, 1, -1, 0, 1};*/ static int dirY[] = {-1, -1, 0, 1, 1, -1, 0, -1}; static int dirX[] = {0, 1, 1, -1, 0, -1, -1, -1}; static int N, M; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); while (true) { StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(st.nextToken()); // 너비 x N = Integer.parseInt(st.nextToken()); // 높이 y if (N == 0 && M == 0) break; map = new boolean[MAX][MAX]; visited = new boolean[MAX][MAX]; // 1. map 정보 반영 for (int i = 1; i <= N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 1; j <= M; j++) { map[j][i] = Integer.parseInt(st.nextToken()) == 1; } } // 2. dfs int result = 0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (map[i][j] && !visited[i][j]) { dfs(i, j); result++; } } } // 3. 출력 bw.write(String.valueOf(result)); bw.newLine(); } bw.close(); bw.close(); } private static void dfs(int y, int x) { visited[y][x] = true; for (int i = 0; i < 8; i++) { int newY = dirY[i] + y; int newX = dirX[i] + x; if (map[newY][newX] && !visited[newY][newX]) { dfs(newY, newX); } } } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
재귀대신 스택으로 구현하면 안될까요?
이 문제의 재귀는 이해가 됬지만, 다른 문제들에서 마주치는 재귀함수들은 손이 잘 안가고, 항상 남의코드를 봐야만 이해가 되더라구요.여기서 dfs함수를 스택으로 구현하면 라인이 더 길어져 재귀보다는 깔끔하지가 않은데, 이해 및 구현이 쉬운거 보다 명확한거 같은데, 코딩테스트의 재귀들은 모두 스택으로 구현하면 어떨지 궁금합니다.
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
dfs 매개변수에서 y,x 를 왜 순서를 반대로 쓰셨는지 궁금합니다.
점프왕 젤리문제에서 dfs 메서드에 dfs(int x, int y)가 아닌 dfs(int y, int x)인지 궁금합니다!이전 문제부터 계속 궁금해했는데, 왜 순서를 바꾸셨는지에 대한 명확한 이유를 못찾겠어서 질문올렸습니다.// 점프왕 젤리 import java.util.*; import java.io.*; class Jump_king_jelly { static final int MAX = 3 + 100 + 10; static int map[][]; static boolean visited[][]; static int N; static int dirY[] = {1, 0}; static int dirX[] = {0, 1}; public static void dfs(int y, int x) { visited[y][x] = true; if(y == N && x == N) return; for(int i = 0; i < 2; i++) { int newY = y + dirY[i] * map[y][x]; int newX = x + dirX[i] * map[y][x]; if(visited[newY][newX] == false) { dfs(newY, newX); } } } 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)); N = Integer.parseInt(br.readLine()); map = new int[MAX][MAX]; visited = new boolean[MAX][MAX]; // 1. map에 정보 반영 for(int i = 1; i <= N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for(int j = 1; j <= N; j++) { map[i][j] = Integer.parseInt(st.nextToken()); } } // 2. dfs 수행 dfs(1,1); // 3. 출력 if(visited[N][N]) bw.write("HaruHaru"); else bw.write("Hing"); bw.close(); br.close(); } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
안녕하세요 11724번 질문드려요!
안녕하세요! 강의 수강 중 질문이 있어 질문 드립니다.현재 이런식으로 코드를 작성했고, 백준 스타일에 맞춰 제출을 했는데 오답처리가 되었습니다. 디버깅 시에도 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(); } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
출력할 때 BufferedWriter? StringBuilder?
안녕하세요 강사님 좋은 강의 감사합니다:)다름이 아니라, 출력문을 사용할 때 BufferedReader와 StringBuilder를 사용하는게 일반적으로 사용하는게 좋다고 알고있는데 해당 강의에서는 BufferedWriter를 사용하신 이유가 궁금해서 글을 작성하게 되었습니다. 감사합니다!
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
answer++ 위치 질문
// 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++;를 했을 때는, 주어진 값과 다르게 나오는데, 어떤 부분에서 차이가 있는지 궁금합니다.. 감사합니다!
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
code의 어디가 잘못된지 도저히 모르겠습니다..
안녕하세요. 해당 문제의 코드를 다음과 같이 짰는데, 출력하면 항상 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(); } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
널 포인터 에러
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(); } }해당 코드를 구현했는데, 널 포인터 에러가 뜹니다..! 어떤 부분에서 잘못됐는지 피드백 받고자 질문드립니다!감사합니다
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
바닥 장식 (백준 1388) 문제 질문입니당
저는 맵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(); } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
침투 (백준 13565) 문제중 질문입니당
아래 코드에서 왜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 일가요 } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
Main class에 static으로 선언하는 이유
강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :) 안녕하세요!혹시 Main class에 static으로 변수를 선언하는 이유가 궁금합니다!또한, 백준에서 public static void main 에 선언했을 때와 차이가 궁금합니다..!! 감사합니다
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
dfs를 호출 할 때 매개변수..?
안녕하세요! 강의 넘 잘 듣고 있습니다. 하루만에 거의 다들었네요,,ㅋㅋ질문이 있습니다혹시 dfs를 호출할 때 이런 '-'나 '|' 같은게 나오면매개변수로 '-' 나 '|' 를 추가해서 dfs함수에 넘겨도 되는건가요?저는 이렇게 할 때가 많은데 이렇게 하지 않고 오히려 dfs 함수 안에서 해결해주는 게 더 간단한 것 같기도 해서요.. 보통은 어떻게 하시나요? 전 4방 탐색을 하면서 이렇게 풀었었네요,, 한 방향만 탐색하는 팁 배워갑니다 ㅎㅎimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[] dr = {-1, 1, 0, 0}; static int[] dc = {0, 0, -1, 1}; static int N, M; static char[][] arr; static int ans; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); arr = new char[N+2][M+2]; for (int i = 1; i <= N; i++) { String str = br.readLine(); for (int j = 1; j <= M; j++) { arr[i][j] = str.charAt(j-1); } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if (arr[i][j] == '|') { dfs(i, j, '|'); ans++; } else if (arr[i][j] == '-'){ dfs(i, j, '-'); ans++; } } } System.out.println(ans); } private static void dfs(int r, int c, char shape) { int start = 0; int end = 0; if (shape == '|') { start = 0; end = 1; } else if (shape == '-'){ start = 2; end = 3; } arr[r][c] = '1'; for (int d = start; d <= end; d++) { int nr = r + dr[d]; int nc = c + dc[d]; if(arr[nr][nc] == shape) { arr[nr][nc] = '1'; dfs(nr, nc, shape); } } } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
유기농배추에서 T는 무엇을 의미하나요?
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번의 테스크케이스를 만드는 이유는 무엇인가요?그리고 단순히 궁금해서 여쭤보는데 가로와 세로 순서로 입력받고 코드를 실행하는것이 아닌 거꾸로 세로와 가로 순으로 실행하는지 궁굼합니다.답변 부탁드립니다. 감사합니다.
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
촌수계산 문제 질문
안녕하세요.위의 코드는 제가 강의를 듣기 전에 작성한 코드입니다.백준에서 2가지로 주어진 테스트 케이스는 통과하는데 코드를 제출하면 틀렸다고 나옵니다.코드 어디가 잘못된지를 모르겠습니다.그리고 강의에서는 dfs 함수에 start 변수만 넣지 않고 count 변수도 넣으셨는데 count변수를 매개변수로 넣지 않고 코드를 작성하는 방법이 있는지 궁금하고, 이러한 방법이 없다면 왜 매개변수로 count 변수를 넣어줘야 하는걸까요?
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
인덱스설정문의
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로 입력받기가 잘못된걸까요?
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
연결요소개수 - 파이썬 풀이 공유
안녕하세요 저는 강사님 강의로 공부하고 파이썬으로 코테를 준비하고 있습니다. 저와 같은 상황에 계신분들과 공유하고 싶어 글을 올립니다. 파이썬 풀이에서 부족한 부분 알려주시면 수정하겠습니다.~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)