BFS68 [자바] 백준 20303 - 할로윈의 양아치 (java) 문제 : boj20303 필요 알고리즘 개념 분리집합 또는 dfs 또는 bfs DP로 실제 답을 구하는 로직 이전에 아이들의 그룹을 만들기 위해 분리집합 알고리즘(union-find) 혹은 그래프 탐색이 필요하다. 이하 풀이는 분리집합으로 풀었다. DP (Knapsack) DP 활용법 중 유명한 냅색류의 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 결국 연결된 아이들의 그룹별로 선택할 수 밖에 없다. 따라서 만약.. 2023. 1. 11. [자바] 백준 8783 - Architektura niezależna (java) 문제 : boj8783 필요 알고리즘 개념 - 그래프 탐색 (bfs, dfs) 단순히 bfs 혹은 dfs로 그래프 탐색만 해주면 된다. 다만 약간의 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 bfs를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자. 문제 자체는 간단하다. '#'으로 둘러싸인 부분 내부의 빈칸까지 포함해서 넓이를 구하면 된다. 예를들어 예.. 2023. 1. 10. [자바] 백준 8111 - 0과 1 (java) 문제 : boj8111 필요 알고리즘 개념 수학 나머지 연산의 규칙에 대해 알고 있어야 풀 수 있다. 너비 우선 탐색 (BFS) 수학적으로 풀 방법이 생각났다면, 이후 BFS를 적용해서 구현할 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS를 모른다면 이 글을 참고하자. 문제 조건 자체는 그리 어렵지 않다. 테스트 케이스야 동일 동작이니 일단 생각하지 말자. 그냥 1부터 시작해서(시작이 0이면 안된다고 .. 2022. 12. 27. [자바] 백준 14588 - Line Friends (Small) (java) 문제 : boj14588 필요 알고리즘 개념 Floyd-warshall 또는 BFS, 그래프 이론 플로이드 와샬 혹은 BFS로 풀 수 있는 그래프 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 결국 서로간의 최단거리를 구해야 함. 그럼 bfs, 플로이드 와샬, 다익스트라 정도가 생각남. 2. O(N^3) 해도 N이 300이라 매우 충분하므로 대충 구현 쉬운 플로이드 와샬로 진행함. 3. 중요한건 일단 위치정보.. 2022. 12. 21. [자바] 백준 1981 - 배열에서 이동 (java) 문제 : boj1981 필요 알고리즘 개념 투 포인터, 이분 탐색 투 포인터 혹은 이분 탐색을 섞은 그래프 탐색 문제이다. 일단 태그는 이분 탐색이긴 한데, 난 투 포인터로 풀었다. 그래프 탐색(BFS, DFS) 투포인터 혹은 이분 탐색으로 제한된 범위 내에서 시작점부터 끝 점까지 탐색이 가능한지 확인해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이하 풀이는 투 포인터를 사용한 풀이이다. 태그를 보니 대부분 이분.. 2022. 12. 13. [자바] 백준 2842 - 집배원 한상덕 (java) 문제 : boj2842 필요 알고리즘 개념 투 포인터, 그래프 탐색 당연히 bfs나 dfs 문제처럼 생겼는데, dfs나 bfs는 그저 탐색을 위해 거들뿐인 문제이다. 투 포인터 혹은 이분탐색 등을 사용해 범위를 조정해나가는 아이디어가 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 혹시 BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고하자. 투 포인터는 써둔게 없지만.. 2022. 12. 12. [자바] 백준 17114 - 하이퍼 토마토 (java) 문제 : boj17114 필요 알고리즘 개념 BFS BFS긴 하다. BFS긴 한게 맞다. 구현 코딩은 체력이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. 우선 BFS는 기본적으로 문제없이 다룬다는 가정하에 풀 수 있다. BFS를 잘 모른다면 BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS 글을 참고하자. 2. 기본 BFS를 알고, 2차원에서의 BFS만 해봤다면 3차원에서의 BFS를 우선 풀어보자.. 2022. 12. 7. [자바] 백준 17071 - 숨바꼭질 5 (java) 문제 : boj17071 필요 알고리즘 개념 그래프, BFS (너비 우선 탐색) 결론적으로 보면 그냥 BFS 문제이다. 다만 아이디어가 좀 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 생각 과정 및 풀이 이 문제의 경우 상당히 많이 잘못 생각했고, 결론적으로 proof by AC (정답 맞췄으니 증명됬다!) 느낌으로 풀었다 ㅋㅋ. 그러니 풀이를 생각한 과정을 적어보겠다. 정답 코드만 볼꺼면 맨 아래의 코드만 보면 될 .. 2022. 11. 29. [자바] 백준 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. 이전 1 2 3 4 5 6 7 다음
