DFS40 [백준 1167] 트리의 지름 / 자바 / 트리순회(dfs) 문제 레벨: G2알고리즘: DFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/11671 번째 시도 dfs를 통해 임의의 정점 하나에서 가장 먼 정점을 구한다. (임의의 정점은 아무거나 상관없다.)dfs를 통해 구한 정점으로 부터 가장 먼 정점까지의 거리를 구한다. 이게 가장 긴 지름임을 보장하는 이유는 예를 들어 설명하겠다.1 - 2 - 3 - 4 - 5 - 6 이런 일직선의 트리를 생각해보자가장 긴 지름을 구하려면 끝점 두 개를 구해야 한다. 1. 임의점에서 dfs를 하면 끝점 하나가 찾아진다.2. 그 끝점을 기준으로 dfs 하면 다른 끝점이 찾아진다.import java.util.*; public class Main { .. 2024. 5. 6. [백준 10026] 적록색약 / 자바 / 그래프 순회(dfs) 문제 레벨: G2알고리즘: DFS 풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/100261 번째 시도 할 일 배열 초기화적록색맹x 일때 dfs적록색맹o 일때 dfs인접해있는 요소를 비교하는 문제일 때는 방향 설정 배열을 쓰는 것이 Point! static int[] x = {1,0,0,-1}; static int[] y = {0,1,-1,0};dfs함수의 for문과 main함수에서 for문을 짤 때 헷갈릴 수도 있다.dfs함수는 동,서,남,북 방향으로 주어진 글자랑 같은 게 무엇인지 찾는 것이고 main함수의 for문은 전체배열을 순서대로 순회하는 것이다 문제가 카드의 경우의 수를 구하는 경우라면 main함수의 for문은 없을 것이다. .. 2024. 5. 5. [백준 1260] DFS와 BFS / 자바 / 그래프 순회(dfs,bfs) 문제 레벨: S2알고리즘: DFS, BFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/12601 번째 시도 가장낮은 숫자부터 탐색해야 한다하니 인접행렬로 그래프 구성dfs 메소드 작성 순서visted[] = true할 일for문으로 dfs 재귀호출import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;import java.util.StringTokenizer;public class Main { static StringBuilder sb = new.. 2024. 5. 3. [프로그래머스] 네트워크 / 자바 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1 번째 시도 DFS 문제인접행렬 탐색할 때 대각선 기준으로 위 아래 둘 중 하나만 봐도 된다.이거 구현하려니 머리가 터질 것 같았다 패스 ~방문한 적이 없다면 그 노드를 기준으로 dfs 해주고 answer++ 해준다..dfs는 연결되어 있는 모든 노드들을 탐색한다.중복탐색을 방지하기 위해 visted = true인 곳은 가지 않는다.import java.util.*;class Solution { public int solution(int n, int[][] compu.. 2024. 4. 22. 이전 1 2 3 4 5 다음
