본문 바로가기

BFS68

[자바] 백준 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.
[자바] 백준 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.
[자바] 백준 25498 - 핸들 뭘로 하지 (java) 문제 : boj25498 필요 알고리즘 개념 그리디 알고리즘 각 트리 깊이마다 사전상 마지막에 오는 문자를 택하는 규칙을 세워야 한다. bfs, dfs 트리를 탐색하기 위해 bfs 혹은 dfs를 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 대회 당시에 규칙은 맞게 세워놓고 구현을 침착하게 안하다보니 엄청 틀렸었다 ㅠ. 어차피 트리이니 사이클이 없고, 루트 노드도 주어졌으므로 루트노드부터 시작해서 리프노드까지.. 2022. 8. 26.
[자바] 백준 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.
[ABC259] D - Circumferences (AtCoder Beginner Contest 259 in Java) 문제 : abc259_d 내 경우엔 그래프로 변경해서 풀었다. 우선 ArrayList의 idx를 기준으로 0번에 s, 1번에 t를 둔다. 이후 N개의 원을 입력받으면서 s와 t를 포함해서 모든 원의 쌍들에 대해 서로 인접해 있다면 양방향 간선을 연결한다(코드의 edgeChk, O(3000^2)). 단, s와 t의 경우엔 외곽선에 겹칠 경우에만 겹친다고 판단하고 간선을 연결한다(코드의 circumferenceChk). 예를들어 이하의 입력을 보자. 4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3 이에 대한 이미지와 각 idx는 다음과 같다. 그리고 간선정보는 다음과 같다. (예를들어 1행 4열의 v는 idx 1과 idx 4가 인접함을 뜻한다.) 그럼 이제 이 문제는 N+2개의 정점이 있는 .. 2022. 7. 11.

티스토리툴바