본문 바로가기

백준133

[백준 3548] 가장 가까운 공통 조상 / 자바 / dfs +LCA #문제         레벨: G4알고리즘: dfs + LCA 풀이시간: 50분힌트 참조 유무: 유https://www.acmicpc.net/problem/3584#문제 풀이        LCA(Lowest Common Ancestor) 문제에서 풀이법은 다양하다.   첫 번째 방법\1. dfs를 통해 각 노드에 깊이를 매겨준다.2. 9와 7의 공통조상을 찾으려면 둘의 깊이가 맞을 때까지 한 쪽이 올라간다.3. 깊이가 맞다면 두 숫자가 동시에 한 칸 씩 올라간다.4. 결국 8을 찾게 된다. 두 번째 방법15와 11의 공통조상을 찾는다고 가정하자1. 15가 루트노드를 만날 때까지 visited[]를 체크하며 올라간다.2. 그 후 11은 visited[] = true로 되어 있는 노드를 만날 때 까지 올라간다.. 2024. 7. 25.
[백준 16946] 벽 부수고 이동하기4 / 자바 / bfs or dfs(방향탐색) #문제         레벨: G2알고리즘: bfs or dfs  풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/16946#문제 풀이        처음에 문제를 보고 무슨소리인가 했다. 나와 같을 수도 있는 여러분들을 위해 쉽게 말해보겠다.1에 위치해있을 때 바로 근처에 있는 0에게 갈 수 있다. 0을 가고나서는 근처 0까지 돌아다닐 수 있다. 즉, 우린 인접해 있는 0의 섬의 넓이와 개수를 구하면 되는 거다. 1. 전체를 순회하며 0의 섬에게 그룹네이밍으로 바꿔준다. ex) A, B, C, D ....  (구현에서는 숫자로 할거임) && 그룹네이밍과 넓이는 map에 저장한다2. 다시 순회하며 1(벽)의 관점으로 근처에 어떤 섬이 있는 지 찾은 후 배열에 넣어둔다.. 2024. 7. 24.
[백준 17472] 다리 만들기2 / 자바 / dfs + 크루스칼 알고리즘 ** #문제         레벨: G1알고리즘: dfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17472#문제 풀이         전체적인 알고리즘 과정은 이렇게 된다.1. 전체를 탐색하며 섬에게 숫자를 매겨준다.2. 섬끼리 연결 가능한 다리를 다 찾는다.3. 그 중 전체를 포함하지만 최소인 다리들을 찾는다.      G1 정도 문제를 푸시는 분들이라면 1,2 번 정도는 머리 속에서 어떻게 구현할지 감이 잡힐 것이다. 그래도 간단하게 설명해보겠다. 1. 섬에게 번호를 지목한다. 이중 for문으로 map 전체를 순회하면서 숫자 1을 찾는다. 숫자 1을 찾으면 4방향으로 dfs 혹은 bfs하여 섬의 번호를 새겨준다. 검정색: 이중 for문 탐색 방향파란색: 이.. 2024. 7. 24.
[백준 3109] 빵집 / 자바 / dfs #문제         레벨: G2알고리즘: dfs 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/3109#문제 풀이         1. 왼쪽에서 오른쪽으로 움직인다.2.  X는 갈 수 없는 곳이다. 3. 최대한 많은 곳을 가기 위해서는 왼쪽 맨위부터 시작해 오른쪽에 놓을 수 있는 가장 위 부터 차근차근 파이프를 설치해야 한다. 문제에서는 말해준다. 세 방향으로 움직일 수 있다고. (오른쪽 위, 오른쪽, 오른쪽 아래 ) 그러면 dfs 탐색을 4방향{ dx = {1,0,0,-1}  dy = { 0,1,-1,0} } 처럼 오른쪽으로 가는 건 고정이니 dy = {1, 0, -1} 로 만들 수 있겠다. 여기서 놓치면 안 되는 게 dy의 순서이다. 가장 위부터 놓여야.. 2024. 7. 23.
[백준 2251] 물통 / 자바 / 브루트포스(dfs or bfs) ** #문제         레벨: G5알고리즘: dfs or bfs풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2251#문제 풀이         물을 옮기는 방법은 6가지이다.{ (A->B)  ( A -> C)  ( B -> A)  (B -> C)  (C -> A)  (C -> B) } 우린 물을 옮기는 6가지 방법을 계속 꼬리를 물어 탐색하면 되는 것이다. 구현은 어떻게 할 것인가? 이중 for문으로 구현하던가 4방향으로 움직이는 dx = {1,0,0,-1}  dy = {0,1,-1,0}처럼 from[], to[]로 구현하면된다. 그러면 언제 탐색을 멈춰야 하나? 세 물통의 담겨있는 용량을 방문한적 있을 때 멈춰야한다. 물통의 리터제한은 200리터이다. 리터제.. 2024. 7. 23.
[백준 2638] 자바 / 치즈 / bfs #문제         레벨: G3알고리즘: bfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2638#문제 풀이         1. 2변이상 접촉 시 1시간만에 다 녹음 2. 치즈 내부에 있는 경우에는 안 녹음3. 치즈가 다 녹는데 걸리는 시간은? 이 문제의 중심은 치즈의 안인지 밖인지 어떻게 판단할 것인지이다.처음엔 치즈 안 쪽을 표시해야겠다고 생각했다. 그러나 구현이 복잡해 보였다.(알고리즘 문제에서 구현이 복잡하면 웬만하면 올바른 방향으로 풀이되는 게 아님) 그래서  치즈 바깥 쪽을 표시하기로 결정했다. 치즈 바깥면을 구하는 건 bfs로 해결할 수 있다. 녹이기 전,  치즈 밖에 있는 (0,0)에서부터 bfs를 시작한다. 1을 만나면 airconta.. 2024. 7. 23.
[백준 2458] 키 순서 / 자바 / dfs #문제         레벨: G4알고리즘: dfs 풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/2458#문제 풀이        자기가 간접적으로 지목(화살표)을 당해도, 간접적으로 지목(화살표)을해도 그 사람이 나보다 키가 작은지, 큰지 알 수 있다. 그래서 우리는 키 작은 사람을 지목하는 그래프 하나, 키 큰 사람을 지목하는 그래프 하나 두개를 만들어야 한다. 그 두 개의 그래프를 따로 따로 dfs하여 자기가 알 수 있는 학생의 수를 알아낸다.  #풀이 코드      import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { static.. 2024. 7. 22.
[백준 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.
[백준 2178] 미로 탐색/ 자바 / bfs #문제         레벨: S1알고리즘: bfs풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/2178 #문제 풀이        bfs 문제의 기본 문제이다. queue와 visited[][]배열을 이용해서 길을 되돌아 가지도 않고 최단 거리를 찾을 수 있다. visited[][]배열을 쓰고 싶지 않다면 distance[][]배열에 해당위치에 도달하기 까지 걸린 이동횟수를 기입하면 된다. distance[][]에 0 이 아닌 숫자가 있다면 방문한 것이므로 해당 위치는 또 queue에 넣지않는다.(방문하지 않는다.) #풀이 코드      import java.util.*;import java.io.*;public class Main { static int N.. 2024. 7. 21.

티스토리툴바