BFS17 [백준 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. [백준 16988] Baaaaaaaaaduk2 (Easy) / 자바 / 구현 + bfs #문제 레벨: G3알고리즘; bfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/16988#문제 풀이 문제를 보는 순간 규칙이 없고 완전탐색(브루트 포스)로 해결해야겠다고 생각이 들었다. 시간복잡도를 구해보자면 2개의 바둑돌을 놓는 경우의 수(400 C 2) X 상대 바둑돌을 잡아먹는 수 구하기(400) = 400 x 399 % 2 X 400 = 대략삼천 이백만 정도 되므로 가능한 경우의 수이다. 이제 구현할 차례이다. dfs를 돌며 바둑 돌을 놓는 구현은 0인 자리에만 놓고 dfs 재귀 깊이가 2인 함수를 구현하면 된다. 여기서 막혔다. 어떻게 함수를 구현해야 겹치치 않고 400 C 2를 구현할 수 있을까? 정답은 이중 for문을 돌며 .. 2024. 8. 18. [백준 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. [백준 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. [백준 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. [백준 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. 이전 1 2 다음
