본문 바로가기

알고리즘182

[백준 1405] 미친 로봇 / 자바 / dfs #문제         레벨: G4알고리즘: dfs풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/1405#문제 풀이         되게 간단한 문제이다. 문제에서는 배열에서 움직인다고 말을 안해서 눈치를 못챌 수도 있는데, 자기가 직접 30x30(넉넉한 배열)배열 중앙을 시작점으로 로봇을 움직이면 되는 문제이다. 갔던 길은 visited = true로 표시한채 말이다.주의해야 할점은 정답은 10의 마이너스9승까지 나타낸다 했으니 float이 아닌 double로 출력해야 한다.#풀이 코드      import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer.. 2024. 7. 30.
[백준 20058] 마법사 상어와 파이어스톰 / 자바 / 구현 + bfs 조금 *** #문제         레벨: G3알고리즘: 구현 + bfs 조금풀이시간: 2시간힌트 참조 유무: 유 https://www.acmicpc.net/problem/20058#문제 풀이        이 문제는 bfs문제로 분류되어있지만, 사실상 구현문제라 생각한다. 이 문제에 핵심은 격자회전시키는 식을 잘 세울 수 있는지이다. 그 방법을 바로 말하겠다. 오른쪽으로 90도 회전한다고 하면 map[i][j]가 map [j][n-1-i]가 된다. 즉, i와 j를 바꿔주고 열은 n-1에다가 바꾼 i를 빼준다. (왼쪽으로 90도 회전한다고 하면 거꾸로 돼서 map[i][j]가 map[n-1-j][i]가 된다.) 우리는 덩어리 째 회전을 시켜야 하므로 이중 for문에서 i+=L 씩 증가시켜줘야 한다. 위 방식을 이해하고 .. 2024. 7. 29.
[백준 2250] 트리와 높이와 너비 / 자바 / dfs *** #문제         레벨: G2알고리즘: dfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2250 #문제 풀이         처음에는 이런 생각을 했다. 가장 오른쪽에 있는 노드를 찾은 후 같은 레벨에 있고 가장 왼쪽에 있는 노드를 찾은 것을 이용하여 구한 값과, 가장 왼쪽에 있는 노드를 찾은 후 같은 레벨에 있고 가장 오른쪽에 있는 노드를 찾은 것을 이용하여 구한 값 중 최솟값을 구한다. 그러나 나 너무 지엽적인 방법이기도 하고 깊이와 x값을 성정하는 dfs 하나 가장 오른쪽 노드 찾는 dfs 하난 가장 왼쪽 노드 찾는 dfs 하나 dfs를 총 세 번 돌아야 한다. 위 방법보다 더 좋은 방법을 소개하겠다.바로 dfs함수 하나에서 레벨과 x좌표와  그.. 2024. 7. 27.
[백준 4803] 트리 / 자바 / bfs #문제         레벨: G4알고리즘: bfs 풀이시간: 40분힌트 참조 유무:https://www.acmicpc.net/problem/4803#문제 풀이         이 문제는 트리와 그래프를 구별할 수 있냐 없냐이다.트리의 간선 개수는 노드-1이다. 그래프의 간선 개수는 노드개수보다 많다.  그래서 우린 노드와 간선의 개수를 비교해서 트리를 구별해야한다. 그 노드를 방문 했든 안했던 해당 노드와 이어져 있는 노드의 간선들을 더한다. 오른쪽 그림을 예시를 들면1 방문    2개 추가(2,3)2 방문   2개 추가 (1,3)3 방문  2개 추가(1,2)총 간선의 개수는 6개이다. 이렇게 나온 이유는 같은 선을 중복해서 계산하기 때문이다. 중복해서 계산을 안 하려고 하면 구현이 어려워진다. 구한 간선.. 2024. 7. 26.
[백준 10159] 저울 / 자바 / dfs #문제         레벨: G4알고리즘: dfs 풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/10159#문제 풀이         그래프로 나타내면 문제풀이 하기 더 수월하다.위 그래프는 자기보다 가벼운 노드를 나타낸 거다.아래 그래프는 자기보다 무거운 노드를 나타낸 거다. 두 번의 dfs를 통해 자신보다 무거운 노드들, 가벼운 노드들을 알아내면 정답을 알 수 있다. 1번 노드를 예를 들어보자dfs(1,lighter)를 하면  1 -> 2  -> 3 -> 4     =  3(자기자신제외)dfs(1,heavier)를 하면  1  -> x =  0(자기자신제외)6(N) -  1(자기 자신) - 3 - 0 =  2   #풀이 코드      import java.ut.. 2024. 7. 25.
[백준 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.

티스토리툴바