# BFS

kjh107704

BFS와 DFS의 구현 방법에 대하여 알아보자.

99bang2

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로

jangwonyoon

DFSBFSBacktracking

polynomeer

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집

polynomeer

그래프 중에서는 위 그림과 같이 여러 개로 나누어져 있을 수도 있다. 위 그림을 보고 두 개의 그래프라고 볼 수도 있지만, 하나의 그래프에 두 개의 연결 요소를 가진다고 볼 수도 있다. 그 이유는 정점 사이에 겹치는 것이 없기 때문이다. 연결 요소로 본다면, 나누어진

polynomeer

너비 우선 탐색(breadth-first search, BFS)는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다. 가까운 정점을 모두 저장해놓고 순서대로 방문해야 하므로, 스택 구조로는 구현이 어렵다. 따라서 큐(Queue) 자료구조를 사용한다. BFS

1571min

트리는 root에서 자식방향으로만 edge가 흘러가고 사이클이 없는 그래프의 한 종류 이다그럼 그래프는 무엇인가?그래프의 구성 요소정점(vertex)간선(edge)그래프는 정점과 간선으로 구성된 자료구조를 이야기한다 트리와 구조적으로 비슷하지만 그래프는 각 간선이 방

devjuun_s

문제 링크 : 프로그래머스-가장 먼 노드n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들

hyeon930

BOJ 2665 미로만들기단순한 BFS인데도 불구하고 굉장히 고민했다... 이 문제는 구불구불하게 갈 수 있다. 즉 최단거리가 아니라 최소로 검은 방을 없애고 가는 것이기 때문에 많은 방을 들리는 것은 상관없다. 따라서왼쪽 위에서 오른쪽 아래로 갱신해가는 DP는 불가하

hyeon930

BOJ 1981 배열에서 이동투포인터 + BFS 문제다. 투포인터는 두 변수가 변화하면서 상관관계를 만들어낼 때 사용하면 되는 것 같다? 또 모든 문제가 그렇듯이 주어진 문제를 단순화해야한다. 단순화의 가장 쉬운 방법이 변수를 고정하는 것이다.완전탐색으로 풀기에는 너무

hyeon930

BOJ 2842 집배원 한상덕이 문제는 투포인터 + 그래프 탐색 문제다. 방문한 칸 중 가장 높은 곳과 가장 낮은 곳의 차이가 피로도라고 한다. 이 때 가장 높은 곳과 가장 낮은 곳을 정하고 탐색 가능 여부에 따라서 가장 높은 곳과 가장 낮은 곳을 조정해나가면 된다.투

hyeon930

BOJ 1939 중량제한이분탐색을 풀고있어서 이분탐색 + BFS로 풀었지만 다시보니 크루스칼로 푸는게 더 쉬울거 같다.1\. left를 1, right를 다리의 하중 중에 최댓값으로 두고 이분탐색을 실시한다.2\. mid 값을 바탕으로 BFS 그래프 탐색을 수행해서 목

hyeon930

BOJ 16988 Baaaaaaaaaduk2 (Easy)예전에 봤을 때는 왜 그렇게 어려웠던건지... 다시 보니 간단한 문제다.1\. 돌 두개를 놓는 모든 경우를 수행한다.2\. 맵 전체 검은 돌에 대한 라벨링을 한다. 동시에 죽은 그룹의 돌을 모두 세어 ans에 최댓

hyeon930

BOJ 16985 Maaaaaaaaaze초보자 입장에서 정말 변태같은 문제였다... 사실 알고리즘은 어려운게 아니지만 할게 너무 많았다.. 또 맵을 계속해서 복사해서 사용해야 했기에 까다로웠던 문제판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다.5개의 판을 쌓는 방법

hyeon930

BOJ 12904 A와 B주어진 상태로부터 특정한 연산을 통해 목표 상태로 도달하는 문제에서 반대로 생각하여 목표 상태에서 역연산을 통해 시작 상태로 도달하게 한다면 경우의 수를 많이 줄일 수 있다. 이 문제 또한 반대로 생각하는 아이디어가 가장 중요한 문제였다.

hyeon930

BOJ 17090 미로 탈출하기처음 생각했던 풀이 각 지점으로부터 시작하여 명령어를 따라 진행하며 탈출할 수 있는 경로였으면 탈출 경로로 기록, 탈출 못하면 탈출 불가 경로로 기록, 아직 가, 불가로 기록되지 않은 곳을 출발점으로 반복한다. 또한 경로확인 중 가, 불

hyeon930

BOJ 16137 견우와 직녀괜히 맵에 패딩 값 주고서 엄한데서 이유 찾다가 엄청 오래걸린 문제...단순히 오작교를 만들 수 있는 모든 지역에 오작교를 만들고 BFS 탐색을 수행하여 최소시간을 갱신하면 된다.절벽이 교차하는 지역인지 확인하는 것은 다음과 같다. 현재

hyeon930

BOJ 12906 새로운 하노이 탑시간제한 5초, 메모리 512MB 하고싶은거 다 해봐라라는 느낌? 방문체크를 어떻게 할 것인가가 핵심이였다.현재 탑의 상태를 해쉬코드 처럼 하나의 코드로 만들어 set에 저장하는 방식으로 방문체크하였다. 해쉬코드 대신에 statusCo

hyeon930

BOJ 3197 백조의 호수너무너무너무 어렵다... 보통 이런 유형의 문제는 지시하는 바를 순서대로 반복 수행하면 되는 것이였으나 이 문제는 최악의 경우에 맵이 무려 1500 x 1500 이다. 따라서 매번 새롭게 BFS를 수행한다거나 방문체크를 수행시 마다 리셋하는

hyeon930

BOJ 2234 성곽단순 BFS 라벨링 문제라고 생각했으나 보통의 문제에서 벽과 같은 장애물이 한 칸을 차지하게 주어지는 반면 이 문제에서는 한 칸에 동서남북의 벽에 대한 정보가 주어졌다. 이 데이터를 어떻게 정제하는가가 이 문제의 핵심이다.비트연산자를 통해 각 칸의