BFS8 [백준] bfs - 3055번 탈출 (Java) 문제링크 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 접근한 방법 두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다. 풀이방법 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다. 물이 번지는 것도 고려해야하므로, 물의 시작지점부터 BFS를 수행한다. 물이 번지는 동작이 수행되었으면 그 이후로 시작지점(고슴도치가 있는 좌표)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다. 특정한 노드를 방문하면 그 이전 노.. 2021. 8. 11. [백준] bfs - 5427번 불 (Java) 문제링크 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 접근한 방법 두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다. 풀이방법 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다. 불이 번지는 것도 고려해야하므로, 불의 시작지점부터 BFS를 수행한다. 불이 번지는 동작이 수행되었으면 그 이후로 시작지점(상범이가 있는 좌표)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다. 특정한 노드를 방문하면 그 이전 노드.. 2021. 8. 4. [백준] bfs- 6593번 상범빌딩 (Java) 문제링크 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 접근한 방법 두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다. 증명/ 풀이방법 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다. 시작지점(S가 있는 좌표)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 배열에 넣는다. 소스코드 작성 방법 이 문제는 흔히 푸는 2차원 배열 문제에 .. 2021. 7. 28. [백준] bfs - 2178번 미로탐색 (Java) 문제링크 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근한 방법 두 개의 노드 간의 거리를 구하는 문제이므로, bfs로 접근해보았다. 풀이방법 BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문에, 이 문제는 BFS를 이용했을 때 효과적이다. 시작지점(0,0)에서부터 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣는다. 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 배열에 넣는다. 소스코드 작성 방법 미로의 크기(n, m)을 전역 필드로 선언한다. 미로의 정보(maze), 방문 여부 .. 2021. 7. 26. [백준] dfs/bfs - 1260번 DFS와 BFS(Java) 문제링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 접근한 방법 문제에 대놓고 DFS와 BFS로 적혀있으므로 각 알고리즘으로 구현 풀이방법 dfs 1. dfs 메소드를 선언하여 파라미터를 정점 번호로 받는다. 2. 현재 정점을 방문 처리하고, 3. 그 정점과 연결되어 있으며 방문하지 않은 정점을 방문한다 (dfs 메소드를 호출한다). bfs 1. 탐색 시작 정점을 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 정점을 꺼내 해당 정점의 인접 정점 중에서 방문하지 않은 .. 2021. 6. 30. DFS와 BFS 간단 정리 DFS BFS 동작 원리 깊이 우선 탐색 (연결된 노드를 우선으로 탐색) 너비 우선 탐색 (거리가 가까운 노드를 우선으로 탐색) 스택 (LIFO) 큐 (FIFO) 구현 방법 재귀 함수 이용 큐 자료구조 이용 DFS와 BFS 문제 유형을 풀 때는 1차원 배열이나 2차원 배열을 그래프 형태로 생각하면 수월하게 풀 수 있다. 예를 들어, 아래의 그림처럼 2차원 배열 좌표의 형태를 그래프의 형태로 바꿔서 생각할 수 있다. 2021. 5. 4. BFS BFS(Breadth First Search) : 너비 우선 탐색 : 가까운 노드부터 탐색하는 알고리즘 : 큐 자료구조를 이용 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 예시) 더보기 클릭 더보기 다음과 같은 그래프를 살펴보자. 탐색을 수행함에 있어 O(N)의 시간이 소요된다. 코딩 테스트에서는 보통 DFS보다는 BFS 구현이 조금 더 빠르게 동작한다. 예제 코드 - ja.. 2021. 5. 4. 꼭 필요한 자료구조 기초 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 오버플로우(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 언더플로우(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로우가 발생한다. 스택 선입후출(First In Last Out)구조 또는 후입선출(Last In First Out)구조 e.g. 쌓아올린 박스를 연상 큐 선입선출(First In First Out) 구조 e.g. 놀이공원 줄을.. 2021. 5. 2. 이전 1 다음 반응형
