그래프4

• 

  백준 14938 java - 서강 그라운드(플루이드와샬, 다익스트라) 해당 문제는 35분여간 bfs로 풀다가 밑에 문제 분류 보고 플루이드와샬, 다익스트라인 걸 보고 바로 플루이드와샬로 돌려서 풀었다. 그 과정에서 문제를 입력값을 제대로 안봐서 m, r를 혼동하는 바람에 이왜틀 3분간 시전... 1. A에서 B까지 가는 거리가 m(수색가능 범위) 이내면 아이템 회수 가능 2. BFS돌리면서 계속 합해줘서 MAX값 찾아야 겠다. 3. 이왜틀???? 아! bfs로 방문처리하면 더 최단거리가 될 수 있음에도 불구하고 방문처리돼서 최단거리로 가는 게 아닐 수 있겠구나 4. 다익스트라 구현보다 플루이드와샬이 구현할 때 더 빠르니까 플와 써야겠다. 5. 문제 접근, 풀이, 제출, pass까지 약 50분 소요 import java.io.BufferedReader; import java.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 7. 2.

• 

  백준 1707 java 이분그래프 (그래프) 이분그래프에 대한 정의를 이해 하지 못해서 한 1주일 정도는 그냥 바라본 문제다. 답지를 보기에는 골드4라는 티어 때문에 용납이 되지 않았고 금방 풀 수 있을 것 같아서 뚫어져라 쳐다 봤다. 결국 두색 칠하기 문제로 귀결되는 듯 보였다. 1. 인접한 두 수는 다른 색, 다른 숫자, 다른 그룹으로 짝지어 질 수 있는가 2. 그렇다면 조합으로는 안되나? => 조합으로는 시간 복잡도가 터질 수 있음 3. dfs 또는 bfs를 돌리며 색칠해 나가다가 인접한 정점이 같은 색깔 또는 같은 숫자인지를 보면 되겠구나 4. 간선이 연결되지 않은 정점들은 어떻게 처리하지? 5. 간선이 연결되지 않은 정점들은 또 dfs 또는 bfs를 돌리면서 집합을 두 집합으로 만들면 되겠구나! 1번 집합 2번 집합이 나오면 3번 집합/4.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 6. 15.

• 

  백준 2178 java - 미로탐색 DP 문제, 대회 문제를 붙잡고 있다가 도저히 풀리지 않아서 도피용으로 푼 BFS 문제이다. 흑흑 1. 전형적인 bfs 문제이다. 2. 4방 delta를 만들어서 풀어야 한다. 3. 1,1 -> N,M 이기 시작점을 0,0이 아닌 1,1? -> 패딩을 활용하자 4. 최단거리이기 때문에 BFS를 통해서 풀어야 한다. -> DFS 활용하면 stackoverflow가 뜰 수도 있으니 조심하자 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.Stri.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 1.

• 

  그래프(Graph), 그리고 DFS와 BFS - 1. 그래프에 관하여 DFS와 BFS는 탐색 알고리즘의 한 종류이다. 이 알고리즘은 그래프를 알고 있어야 이해할 수 있는 알고리즘이다. 그래서 그래프부터 다루고자 한다. 그래프란 점(정점)과 선(간선)으로 이루어진 자료구조를 의미한다. 별개 아니다. 그냥 숫자(인덱스)가 붙은 점들과 그 점들 간의 관계를 선으로 표시한 것 뿐이다. 단순한 점과 선들의 조합인 그래프를 활용해 마크주커버그가 페이스북을 만들었다. 이 페이스북을 사례로 그래프를 설명할 것이다. 자고로 본인은 페이스북 안한지 100만년된 듯 싶다. 각 점을 사람으로 간주하고 각 선을 팔로우하여 관계를 표시하면 그것이 그래프다. 눈치 챈 사람도 있겠지만 A가 B를 팔로우하였다. B가 A를 맞팔로우하였다와 같이 (간)선들은 일종의 방향성을 가질 수 있다. 이와 같은 방향.. 알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory) 2022. 2. 22.