본문 바로가기

BFS30

[자바] 백준 25601 - 자바의 형변환 (java) 문제 : boj25601 필요 알고리즘 개념 그래프 탐색 (bfs, dfs) 그래프 탐색을 할 수 있어야 한다. bfs, dfs 등 해시를 사용한 집합과 맵 String에 대한 간선 표현을 위해 HashMap 등의 자료구조를 사용할 수 있어야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이게 뭔가 복잡해보일 수 있는데, 결국 그냥 그래프 정점과 간선이 주어지고 특정 지점에서 다른 지점으로 그래프 탐색이 가능하냐고 묻.. 2022. 10. 7.
[자바] 백준 14562 - 태권왕 (java) 문제 : boj14562 필요 알고리즘 개념 너비 우선 탐색 (bfs) 너비 우선 탐색을 떠오르기 힘들 수 있고 다른 풀이도 존재하는 문제이다. 이하 풀이는 너비 우선 탐색으로 진행한다. 백트래킹 부가적으로 백트래킹 개념도 넣으면 좋다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 일반적으로 bfs는 목적지(이 문제에서는 t에 해당)는 고정되어 있고 목적지까지 탐색해나가곤 한다. 하지만 출발지점과 목적지를 동시에 사용해서 .. 2022. 10. 1.
[자바] 백준 3197 - 백조의 호수 (java) 문제 : boj3197 필요 알고리즘 개념 너비 우선 탐색 (bfs) 만날 수 있는 시간을 구해야 하므로 너비 우선 탐색으로 탐색하는 것이 적합하다. 분리 집합 (disjoint set) 분리 집합 알고리즘 (유니온 파인드)를 사용해 두 백조가 서로 만날 수 있는 구한다면 매번 백조가 만날 수 있는지 dfs 등을 통해 확인하지 않아도 된다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS에 대해 잘 모른다면 이 글.. 2022. 9. 17.
[자바] 백준 5993 - Invasion of the Milkweed (java) 문제 : boj5993 필요 알고리즘 개념 너비 우선 탐색 (bfs) 기본적인 형태의 너비우선 탐색 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 BFS를 모른다면 이 글을 보자. 깁노적인 형태의 BFS 문제이므로 별다른 구현 풀이는 필요 없다. 주의점은 일반적인 문제와 다르게 입력이 가로, 세로 순서로 들어온다는 점과, Mx, My도 마찬가지로 가로, 세로 순서로 들어오고 좌측 아래부터 (1,1)이라는 점이다. .. 2022. 9. 8.
[자바] 백준 18251 - 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) (java) 문제 : boj18251 필요 알고리즘 개념 스위핑 문제를 단순화 시키면 사실 여러번의 스위핑을 통해 풀 수 있는 문제이다. 다만 이건 내 경우이고, 이 문제는 DP 등 다른 풀이들도 있다. 내가 푼 방식은 스위핑을 이용한 풀이이므로 그걸로 해설을 진행한다. bfs (너비 우선 탐색) 내 경우 트리의 루트부터 주어진 가중치들을 스위핑을 하기 위해 위치 순서대로 정렬하려고 bfs를 사용했다. 꼭 필요한 방식은 아니고, 이 역시 다양한 방식으로 가능하다. 혹시 bfs를 모른다면 이 글을 참고하자. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백.. 2022. 9. 6.
[자바] 백준 25418 - 정수 a를 k로 만들기 (java) 문제 : boj25418 필요 알고리즘 개념 동적계획법(DP), 너비 우선 탐색(BFS), 탐욕법(greedy) DP, BFS, 그리디 정도가 풀이로 생각나는 문제이다. 셋 다 알아야 하는건 아니고, 셋 중 하나만 알면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1 - DP 풀이 dp[x]를 x를 만들기 위한 최소 횟수로 정의하자. 그리고 dp[x]를 모두 무한대로(이 문제의 경우 나올 수 있는 최대수치가 .. 2022. 9. 4.