BFS14

• [Algorithm] 백준 2573 (BOJ 2573) 빙산 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 2573번 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/2573 1. 문제 설명 해당 문제에서 요구하는 바는 단순합니다. 주변에(상하좌우 인접)에 바다가 있으면 바다의 개수만큼 빙산의 높이가 감소하고, 주어진 빙산이 2 덩이로 분리될 때는 최초의 년수를 구해서 출력하면 됩니다. 한 가지 신경 써야 할 부분은 빙산의 높이가 얼마큼 감소하는지를 계산할 때, 이전 빙산이 다 녹아서 바다가 된 경우는 계산에 포함하지 않아야 한다는 점입니다. 실제로는 동시다발적으로 높이가 감소하는 형태이니까요 이 부분만 고려하시면 어렵지 않게 풀 .. Algorithm & Data Structure/문제풀이 2022. 4. 11.

• [Algorithm] 백준 2468(BOJ 2468) 안전 영역 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 2468번 안전영역 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/2468 1. 문제 설명 해당 문제는 BFS순회를 통해 2차원 배열의 상하좌우가 연결되어있는 영역이 최대일 때의 개수를 구하면 되는 문제입니다. 문제에서는 따로 비가 얼마나 내린다라는 명시가 없는데, 지문을 자세히 보면 "내리는 비의 양에 따른 개수를 모두 조사해보면~" 이란 문구가 있는데 이를 통해서 내릴 수 있는 비의 모든 높이를 탐색해보라는 것을 알 수 있습니다. 여기까지 보면 전부 탐색해야 하나 싶으실 텐데, 사실 그렇진 않습니다. 결국 땅이 잠기는 건.. Algorithm & Data Structure/문제풀이 2022. 4. 7.

• [Algorithm] 백준 5014(BOJ 5014) 스타트링크 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 5014번 스타트 링크 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/5014 1. 문제 설명 해당 문제는 내가 현재 있는 층(S)에서 목표로 하는 층(G)으로 이동하기 위해 엘리베이터를 몇 번을 이용해야 하는지를 출력해야 하는 문제입니다. 사실문제가 S, G, U, D 이런 문자들을 서서 읽기가 조금 불편할 뿐이지 BFS를 통해서 아주 쉽게 풀 수 있습니다. 간단한 풀이이므로 글로 설명을 해보자면 다음과 같습니다. 현재 있는 층에서 엘리베이터를 이용해 이동할 수 있는 2가지의 경우를 모두 구합니다. 이동한 층을 모두 방문 .. Algorithm & Data Structure/문제풀이 2022. 4. 5.

• [Algorithm] 백준 2644(BOJ 2644) 촌수계산 문제풀이!! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 2644번 촌수 계산 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/2644 1. 문제 설명 문제에서 요구하는 것은 두 사람 간의 촌수를 계산하는 것입니다. 문제 해결을 위해서 DFS, BFS 둘 중 어느 걸로 접근해도 상관은 없습니다. 저는 둘 중에서 BFS를 선호하기 때문에 BFS로 풀었습니다. 그래프 문제를 풀 때처럼 문제에서 주어진 사람 간에는 간선의 길이가 1로 연결되었다고 보고, 인접한(이동 가능한) 노드로 이동한다고 생각하면서 코드를 작성하였습니다. 어려운 문제는 아니므로 바로 코드를 살펴보겠습니다. 2. Jav.. Algorithm & Data Structure/문제풀이 2022. 4. 5.

• [Algorithm] 백준 17142(BOJ 17142) 연구소 3 문제풀이! (Java) 안녕하세요 coding-knowjam입니다. 오늘은 백준 온라인 저지에 있는 17142번 연구소 3 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/17142 1. 문제 설명 해당 문제는 많이 풀어봤던 BFS문제를 응용해서 풀면 되는 문제입니다. 기본적으로 문제에서 요구하는 바는 바이러스가 가장 빨리 퍼지는 최소의 시간을 구하는 것이기 때문에, 주어진 바이러스에서 활성 바이러스를 선택하는 모든 경우의 수를 고려해야 합니다. 모든 경우의 수마다 BFS를 수행하여 가장 빨리 바이러스가 퍼졌을 때를 찾으면 되는 문제입니다. 해당 요구사항을 구현할 때 주의할 점은 다음과 같습니다. 비활성 바이러스는 활성 바이.. Algorithm & Data Structure/문제풀이 2021. 11. 14.

• [Algorithm] 백준 17144(BOJ 17144) 미세먼지 안녕 문제 풀이!! (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 17144번 미세먼지 안녕! 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/17144 1. 문제 설명 해당 문제는 단순하게 구현하면 되는 문제입니다. 구현할 때 주의해야 할 부분은 다음과 같습니다. 먼지가 확산되고 난 이후 새롭게 생성된 먼지들도 체크할 것 먼지가 확산될 때, 기존 먼지량을 따로 저장하지 않고 덮어쓰면 먼지량이 달라지므로 주의 공기청정기가 2개의 방향을 가지고 바람을 내뿜기 때문에 상하좌우 탐색범위 설정할 때 주의 위의 사항을 주의해서 BFS를 활용해서 구현하시면 어렵지 않게 풀 수 있습니다. 그럼 코드를 살.. Algorithm & Data Structure/문제풀이 2021. 10. 7.

• [Algorithm] 백준 4963(BOJ 4963) 섬의 개수 문제 풀이(Java)!! 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 4963번 섬의 개수 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/4963 1. 문제 설명 해당 문제는 그래프 탐색 문제로 BFS혹은 DFS를 구현할 줄 아신다면 쉽게 풀 수 있는 문제입니다. 문제를 풀 때 주의하셔야 할 점은 테스트 케이스가 여러 개라는 것과 이동좌표 계산할 때 대각선도 고려해야 한다는 점입니다. 해당 부분만 고려하면 어려운 부분은 없으므로 바로 코드를 살펴보겠습니다. 2. Java로 문제 풀이 package study.blog.codingnojam.algorithm.boj; import java.io.*.. 카테고리 없음 2021. 10. 2.

• [Algorithm] 백준 16234번(BOJ 16234) 인구 이동 문제풀이!! (Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 16234번 인구이동 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/16234 1. 문제 설명 해당 문제는 BFS를 사용해서 주어진 내용에 맞게 구현을 하면 풀 수 있는 문제입니다. 문제를 풀 때 생각을 좀 해야 하는 부분은 BFS를 수행하면서 연합이 된 국가들을 어떻게 저장할지를 고려해야 합니다. 저는 BFS과정에서 연합이 된 국가들을 따로 List에 저장하고, 국가들의 인구수들의 합을 저장하는 변수를 별도로 선언해서 연합국가들의 정보를 저장해서 문제를 해결했습니다. 그럼 코드를 살펴보겠습니다. 2. Java로 문제 풀이 .. Algorithm & Data Structure/문제풀이 2021. 9. 21.

• [Algorithm] 백준 16236(BOJ 16236) 아기상어 문제 풀이!!(Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 아기 상어 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/16236 1. 문제 설명 해당 문제는 구현 문제이면서 BFS를 같이 사용해줘야 하는 문제입니다. 문제를 읽어보면 아기 상어가 먹이를 찾기 위해서 이동해야 하는데 이동하는 과정에서 먹이의 거리가 동일하면 가장 왼쪽의 위에 있는 먹이를 먹어야 합니다. 먹이를 찾기 위한 과정을 BFS로 풀어내고 이후에 찾아낸 먹이로 이동하여 먹이를 먹고, 먹은 횟수를 계산하여 몸집을 키워주는 형태로 코드를 작성하여 반복적으로 수행하여 먹이가 없을 때 이동한 거리(문제에서는 시간)를 결괏값.. Algorithm & Data Structure/문제풀이 2021. 9. 12.

• [Algorithm] 백준온라인저지 13460번 구슬 탈출2 Java로 문제풀이!! (BOJ-13460) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 13460번 구슬 탈출 2 문제를 풀어보겠습니다. 해당 문제는 백준 온라인 저지 삼성 SW 역량테스트 기출문제집에 들어있는 문제입니다. 1. 문제 설명 설명에 앞서 아래에 있는 링크를 통해서 풀어볼 문제를 읽어보고 오시길 바라겠습니다. https://www.acmicpc.net/problem/13460 해당 문제는 빨간 구슬이 탈출하는데 보드판을 몇 번 움직였는지를 구하는 문제입니다. 기본적으로 이런 문제는 BFS알고리즘을 통해서 접근을 하는 것이 좋다고 생각합니다. BFS알고리즘을 통해서 보통의 탈출 문제는 문제에서 요구하는 객체에 대한 이동 횟수를 구하기 마련인데 해당 문제는 빨간 구슬과 파란 구슬이 동시에 움직여야 하므로 .. Algorithm & Data Structure/문제풀이 2021. 7. 12.

• [Algorithm] BOJ-14502 Java로 문제풀이 (완전탐색) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 문제를 풀어보겠습니다. 문제에 대한 설명은 따로 하지 않으니, 문제를 직접 보고 오시길 바랍니다. https://www.acmicpc.net/problem/14502 1. 문제 해설 난이도 : 골드 5 문제풀이 키워드 : 완전 탐색, BFS, 순열, 조합, 재귀 문제를 읽어보셔서 아시겠지만 목적은 기둥 3개를 빈 곳에 새로 심고 나서 바이러스가 퍼지지 않은 안전한 영역이 최대일 때의 값을 출력하는 것입니다. 그러면 우선 기둥 3개를 어떻게 심어야 안전한 영역의 개수가 최대가 될지를 고민해야 하는데, 문제의 조건 중 전체 영역의 크기가 최대 8 X 8 이므로 완전 탐색으로 해결해 볼 수 있습니다. 완전 탐색을 수행하기 위해 기둥이.. Algorithm & Data Structure/문제풀이 2021. 4. 18.

• 

  [Algorithm] DFS (Depth-first Search)를 Java로 구현해보자! 안녕하세요 Coding-Knowjam입니다. 오늘은 그래프와 트리를 탐색할 때 사용되는 DFS알고리즘에 대해서 알아보겠습니다. 1. DFS (Depth-first Search)란? DFS는 번역하면 깊이 우선 탐색이라고 합니다. 이름에서도 알 수 있듯이 연결된 노드를 따라서 계속 방문을 한 후에 더 이상 연결된 노드들을 없을 때 그 전 노드로 되돌아가고 다시 연결된 노드를 따라서 탐색을 합니다. 사실 글로 설명하기는 좀 애매해서 그림과 같이 설명을 드리겠습니다. 위와 같은 그래프가 존재한다고 하고, 1번 노드부터 DFS탐색을 시작해보겠습니다. 1번 노드 방문처리 후 출력 (탐색 순서 : 1) 1번 노드에 인접한 노드 2번, 3번, 8번 중 하나를 방문해야 하는데 오름차순으로 방문하기로 가정하겠습니다. 2.. Algorithm & Data Structure/이론 2021. 4. 16.