BFS8 불(BJ_G4_5427) 1. 문제 링크 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 2. 나의 코드 메모리: 116604kb 시간: 924ms 코드 길이: 2228B 시간 복잡도 : O(RC) 설명 - 사람이 이동하는 경로와 불이 번지는 경로를 따로 큐로 처리 - 만약 더이상 사람이 이동할 경로가 없으면 Impossible 출력 - 만약 사람이 map의 가장자리에 도착하면 시간을 출력 import java.awt.Point; import java.io.BufferedReade.. 2024. 4. 17. 치즈(BJ_G4_2636) 1. 문제 링크 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 2. 나의 코드 메모리: 16000kb 시간: 160ms 코드 길이: 2639B 시간 복잡도 : O(RC) 설명 - 치즈를 녹이는 과정은 BFS를 통해 바깥쪽 치즈를 0으로 변경 - 치즈의 갯수를 세기 위해서는 완전탐색 import java.awt.*; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre.. 2024. 4. 13. Tree, BFS 1. 트리 1) 트리의 개념 - 비선형 구조 - 원소들 간에 1:N 관계를 가지는 자료구조 - 원소들 간에 계층관계를 가지는 계층형 자료구조 - 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 2) 트리의 용어 - 노드 : 트리의 원소 - 루트 : 최상위 노드 - 형제 노드 : 같은 부모 노드의 자식 노드들 - 조상 노드 : 산선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 - 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 - 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 - 노드의 차수 : 노드에 연결된 자식 노드의 수 - 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 - 단말 노드 : 차수가 0인 노드 - 노드의 높이 : 루트에서 노드에 .. 2024. 2. 6. DFS / BFS 1. DFS - 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘입니다. - 재귀 함수를 이용하므로 스택 오버플로에 유의 - ex. 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 - 작동 원리 - 예제 코드 public class BJ_11724 { static ArrayList[] A; static boolean visited[]; static void DFS(int v) { if (visited[v]) { return; } visited[v] = true; for (int i : A[v]) { if (!visited[i]) { DFS(i); } } } public static vo.. 2024. 1. 22. 이전 1 2 다음
