본문 바로가기

너비 우선 탐색15

[자바] 백준 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.
[자바] 백준 25516 - 거리가 k이하인 트리 노드에서 사과 수확하기 (java) 문제 : boj25516 필요 알고리즘 개념 bfs(너비 우선 탐색), dfs(깊이 우선 탐색) 기본형태의 탐색문제이다. 이 문제의 경우 거리를 따져야 하므로 일반적으로 생각했을 때 bfs가 기본이지만, dfs로도 가능하다. 아무튼 둘 중 하나만 잘 구현할 줄 안다면 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 딱히 뭐 설명이 필요없는 bfs 기본형태의 문제이다. bfs 혹은 dfs에 대해 모른다면 bfs 글.. 2022. 9. 2.
[자바] 백준 5214 - 환승 (java) 문제 : boj5214 필요 알고리즘 개념 BFS (너비 우선 탐색) 너비 우선 탐색 문제이다. 다만 간선 설정이 어려운걸 끼얹은.. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 그냥 생각해보기 문제 자체는 정점과 간선이 주어지고 그냥 BFS를 돌리면 되는 간단한 문제이다. 다만 이 간선이 한번에 K개씩 주어진다는게 문제이다. 즉, 로직 자체는 BFS면 되지만 간선을 어떻게 저장해둘지가 핵심인 문제이다. BFS를 모른다면 이 글.. 2022. 8. 30.
[자바] 백준 22949 - 회전 미로 탐색 (java) 문제 : boj22949 필요 알고리즘 개념 BFS (너비 우선 탐색) 탈출 까지의 최소 이동시간을 빠르게 알 수 있기 위해 BFS를 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 오랜만에 재밌는 BFS 문제였다. BFS를 이해하는데 도움이 많이될 것 같은 문제로, 풀어보면 도움이 많이될 것 같다. 우선 이 문제는 BFS를 상당히 잘 이해하고 있어야 풀 수 있다. 다른거 안들어간 순수 BFS 문제중에서는 거의.. 2022. 8. 27.
[자바] 백준 1682 - 돌리기 (boj java) 문제 : boj1682 내 경우 String을 기준으로 한 bfs로 풀었다. 우선 수열이 '1,2,3,4,5,6,7,8' 이라고 한다면 이걸 String으로 "12348765"로 변경한다. 즉 수열의 순서와 관계없이 그냥 내가 알아보기 편하게 배열에 나타나는 순서대로 String으로 만들었다. 어떻게 하든 상관은 없다. 마찬가지로 입력이 '6 4 2 8 1 3 5 7'일 경우 String으로는 "64287531"로 표현했다. 이런식으로 입력으로 들어온 값을 String으로 변환한걸 GOAL, 시작 수열을 String으로 변환한 "12348765"를 START라고 해보자. 그럼 이제 A, B, C, D의 4가지 변환 과정을 거쳐 START에서 GOAL로 최소 몇 번 만에 변환되는지 알 수 있으면 된다. 이.. 2022. 7. 23.