알고리즘/DFS33 [백준 17471] 게리맨더링 / 자바 / dfs + bfs #문제 레벨: G3알고리즘: dfs + bfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17471#문제 풀이 1. 지역을 나누는 조합을 구한다.2. 나눈 지역 조합 중 불가능한 조합이 있는지 확인한다.3. 이상이 없다면 차이를 구한다. 가능한 조합으로 나누려고 하니 아이디어 생각이 안 났다. 일단 효율을 포기하더라도 조합을 다 구한 후 그 조합이 가능한 조합인지 판별하는 것이 알고리즘 문제풀이에서는 효율적이라 생각한다.#풀이 코드 import java.io.*;import java.util.*;public class Main_17471_2 { static int N; static int peoples[]; // 구역별.. 2024. 7. 22. [백준 14889] 스타트와 링크 / 자바 /dfs #문제 레벨: S1알고리즘: dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14889 #문제 풀이 dfs로 조합을 구한 후 조합이 완성될 때마다 답의 최솟값을 구하면 되는 쉬운 문제이다. 설명은 생략하겠다.#배운 점 dfs함수는 사람마다 구현하는 게 다 다르다. visited[] = true 순서이다. 재귀호출 전 true만들기 dfs(int i) { for (int j = i; j 재귀호출 후 첫 코드에서 true만들기 dfs(int i) { visited[] =true; for (int j = i; j 이것도 사고의 흐름이 편한대로 작성하면 될 것이다. 자기만의 d.. 2024. 7. 18. [백준 2573] 빙산 / 자바 / dfs #문제 레벨: G4알고리즘: dfs풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/2573 #문제 풀이 이 문제는 두가지를 구현하면 되는 문제이다.1. 빙산의 개수 카운팅 함수2. 빙산을 녹이는 함수하지만 난 보다시피 dfs가 간접적으로 빙하를 카운팅 하는데 도움을 주면서 빙하를 녹였다. 원래 내생각에는 한번 배열을 순회하는 김에 다 처리하자. 그게 성능상 이점을 가져갈 것 같다였다. 그러나 두가지 일을 동시에 하는 코드를 짜니 코드를 짜기 복잡했다.그래서 위에 쓴 과정처럼 논리의 흐름대로 코드를 짰다.#풀이 코드 import java.io.*;import java.util.*;public class Main { st.. 2024. 7. 17. [백준 13023] ABCDE / 자바 / dfs #문제 레벨: G5알고리즘:dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/13023 #문제 풀이 이 문제에 key point는 dfs 경로를 다양하게 탐색할 수 있느냐이다. 보통은 그래프에서 dfs를 사용할 때 연관된 노드들을 모두 방문한다에 포커스가 맞춰져 있다. 그러나 이 문제는 경로에 포커스가 맞춰져있다. 그래서 우리는 dfs 함수 중 boolean[] = false 이 부분을 잘 봐야 한다. 이것 덕분에 이전dfs 경로에서 탐색했던 노드들도 다시 탐색하게 되는 것이다.#풀이 코드 import java.io.BufferedReader;import java.io.IOException;import java.io.I.. 2024. 7. 16. [백준 9466] 텀 프로젝트 / 자바 / dfs + cycle #문제 레벨: G3알고리즘: dfs + cycle풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/9466#문제 풀이 본 유형은 나에게는 신유형이다. 보통 dfs라면 cycle를 돌지 않고 한 번 간 곳은 visited[] 배열로 방문하지 않는다. 그러나 이 문제는 done[] 배열을 만들어 두 번 순회하여 dfs를 마친다. 한 번 순회로 dfs를 마칠 수 있지 않나? (그럴 수도 있을 것 같긴 하다..) 그러나. 가볍게 이해하기 위해서는 dfs를 두 번 도는 것이 좋다. 한 번 돌 때는 연결고리를 만드는 과정이고 두 번 순회할 때는 cycle인지 판별하여 팀원인지 가려내기 위함이다. #풀이 코드 import java.io.Bu.. 2024. 7. 15. [백준 1707] 이분 그래프 / 자바 / dfs #문제 레벨: G4알고리즘: dfs 풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/1707#문제 풀이 이분 그래프가 뭔지 모르는 분들을 위해 설명하겠다. 형식상, 이분그래프의 정의를 먼저 보자면 "모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프이다.".그림으로 더 쉽게 이해해보겠다.1노드를 빨간색이라고 하면 그에 인접한 노드들은 모두 블루여야 한다. 그렇다면 3번 노드는 블루이기 떄문에 3번 노드에 인접한 노드들은 모두 레드여야 한다.만약 아래 그림과 같이 4번 노드가 b라면, 3번 4번이 인접한데 같은 색상이므로 이분 그래프가 아니다.이제 이해가 되는가? 그러면 우리가 코드.. 2024. 7. 13. [백준 14500] 테트로미노 / 자바 / DFS + 구현 문제 레벨: G4알고리즘: DFS + 구현 풀이시간: 1시간 힌트 참조 유무: 유 https://www.acmicpc.net/problem/145001 번째 시도 [알고리즘 설명] 4방향 depth 4로 dfs를 해보면 'ㅜ' 모양 빼고 다 만들 수 있다.'ㅜ' 모양을 만들려면 depth가 2일 때, 즉 'ㅜ'의 중앙일 때 그 위치에서 next로 넘어가지 않고, next의 값만 +해서 파라미터에 넘겨줘 재귀를 한다. 그렇다면 dpeth는 3이 됐는데 전이랑 위치가 변함이 없고 next의 값은 반영 되어있다. 실질적으로 한 칸 갔다 온 걸로 치는 것이다. dfs 구현은 꾸준히 연습해야겠다.import java.io.BufferedReader;import java.io.IOException.. 2024. 7. 3. [백준 1967] 트리의 지름 / 자바 / DFS 문제 레벨: G4알고리즘: DFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/19671 번째 시도: 실패 [깨달은 점]dfs는 리턴값이 void이고 전역변수를 고치는 게 구현하기 편함 리턴값이 int면 구현하기 까다로움[알고리즘 설명]지름의 중심점이 될 수 있는 노드는 자식을 2개 가지고 있는 노드이다.그래서 중심점이 될 수 있는 노드들을 dfs하며 답을 업데이트해간다.dfs는 루트노드에서 양갈래로 찢어져 가장 각각 가장 긴 길을 구한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayL.. 2024. 6. 20. [백준 1987] 알파벳 / 자바 / 백트래킹 문제 레벨: G4알고리즘: 백트래킹풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/19871 번째 시도 백트래킹 기본적인 문제굳이 설명을 적지 않겠다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;public class Main { static int ans = Integer.MIN_VALUE; static boolean[][] visited; static int[] dx = {1,0,0,-1}; static int[].. 2024. 6. 19. 이전 1 2 3 4 다음
