알고리즘/BFS13 [백준 16234] 인구 이동 / 자바 / bfs #문제레벨: G4알고리즘: bfs풀이시간: 50분힌트 참조 유무:https://www.acmicpc.net/problem/16234#문제 풀이특정 국가(A)를 기준점으로 삼고 그 국가와 연할될 수 있는 국가(B)를 찾고 B와 연합될 수 있는 국가를 찾고(C) 반복한다. 이 형식 어디서 보지 않았는가? 4방향+bfs(or dfs)이다. 그런데 bfs 한 번으로 모든 국가를 다 탐색할 수는 없다. 그래서 이중 for문으로 모든 국가를 돌대 visited =false(방문하지 않은) 곳만 bfs(or dfs)를 돌린다. 코드는 둘 다 첨부하겠다.코드를 보면 bfs(or dfs)를 마치고나서 인구이동을 시킨다. bfs로 인접국가를 순회하는 김에 인구이동까지 하면 안되나? 라는 충동이 들었지만, 구현이 복잡하고 .. 2025. 1. 17. [백준 9328] 열쇠 / 자바 / bfs + 구현 #문제 레벨: G1알고리즘: bfs + 구현풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/9328#문제 풀이 이 문제에서 중요한 건 bfs가 아니다. 구현에 초점에 맞춰진 문제이다. 그냥 bfs로 탐색하면 지금은 못가더라도 나중에 키(소문자)를 획득하고 나서 갈 수 있는 곳은 어떻게 갈 것인가? 어떻게 구현할 것인가를 묻고 있다. 아이디어는 간단하다. 지금 열 수 없는 문은 나중에 열 수도 있으니 저장해둔다. 그리고 해당 키를 얻었을 때 열 수 있는 문을 다 열고 마저 탐색한다.나머지는 주석참고 바란다.#풀이 코드 import java.io.BufferedReader;import java.io.IOException;imp.. 2024. 9. 10. [백준 16930] 달리기 / 자바 / bfs + dp #문제 레벨: P3알고리즘: bfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/16930#문제 풀이 위 문제는 dp + bfs(우선순위 큐) 문제이다. 기존 비슷한 문제와 다른 점은 1초에 1칸 움직이는 것이 아니라 1 ~ K 개수 만큼 이동할 수 있다는 거다. 그래서 우선순위큐를 사용하더라도 해당 위치에 도달하기 까지가 최소 이동횟수가 아닐 수도 있다. 최소이동횟수가 아닐 것을 이용해 계속 탐색하면 의미가 없지 않은가?(시간초과) 그래서 우린 이때, dp를 도입하는 거다. dp를 도입하여 각 칸에 도달한 최소 이동횟수를 적어준다. 그보다 많다면 break해줘 탐색시간을 줄이는 거다.#풀이 코드 import java.i.. 2024. 8. 13. [백준 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. [백준 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. [백준 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. [백준 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. [백준 13460] 구슬 탈출2 / 자바 / BFS 문제 레벨: G1알고리즘: BFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/134601 번째 시도: 성공 [알고리즘 설명]처음엔 변수를 여러개 만들어 정답을 관리하려고 했다. 예를 들면, blue가 움직인 횟수, red가 움직인 횟수, blue의 움직인 경로, red의 움직인 경로 등등. 왜 이렇게 하려고 했냐면 BFS함수를 재사용하기 위해서이다. BFS(A), BFS(B) 이와 같이 말이다. 각각 함수를 돌려 리턴받은 값으로 비교하려고 했으나 복잡해져 다른 방법을 사용했다.그냥 지엽적으로 bfs 한코드에 다 넣었다. 신경써야 하는 변수들도 줄어드니 의식의 흐름대로 코드를 작성할 수 있어 수월했다. 자세한 설명은 주석으로 하겠다.imp.. 2024. 7. 3. [백준] 아기상어 / 자바 문제 레벨: G3알고리즘: 풀이시간: 12:34힌트 참조 유무:https://www.acmicpc.net/problem/162361 번째 시도: 실패 [알고리즘 선택 사고 과정]먹을 수 있는 것들을 다 먹어야 함(배열 탐색)먹을 수 있는 것에서 갈 때에는 최소한의 거리로 가야 함 -> BFS 선택되게 간단히 알고리즘 선택했다 [풀이 과정]반복문상어가 먹을 수 있는 것을 찾을 때까지 탐색(BFS)한다.만약 먹을 것이 없다면 반복문을 종료하고 답을 반환한다.자세한 건 주석 참조 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;i.. 2024. 5. 25. 이전 1 2 다음
