# BFS

58개의 포스트
post-thumbnail

[그래프] BFS와 DFS

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

5일 전
·
0개의 댓글
post-thumbnail

백준 BFS 1697 숨바꼭질

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

2020년 4월 1일
·
0개의 댓글
post-thumbnail

TIL(20.03.30) DFS,BFS,Backtracking

DFSBFSBacktracking

2020년 4월 1일
·
0개의 댓글
post-thumbnail

BOJ 2667. 단지번호붙이기

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

2020년 3월 30일
·
0개의 댓글
post-thumbnail

연결 요소(Connected Component)

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

2020년 3월 30일
·
0개의 댓글
post-thumbnail

너비 우선 탐색(BFS)

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

2020년 3월 30일
·
0개의 댓글
post-thumbnail

TIL(20.03.23) DataStructure Graph

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

2020년 3월 23일
·
0개의 댓글
post-thumbnail

가장 먼 노드-프로그래머스(python)

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

2020년 3월 21일
·
0개의 댓글

[BOJ 2665] 미로만들기 (Java)

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

2020년 2월 27일
·
0개의 댓글

[BOJ 1981] 배열에서 이동 (Java)

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

2020년 2월 27일
·
0개의 댓글

[BOJ 2842] 집배원 한상덕 (Java)

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

2020년 2월 27일
·
0개의 댓글

[BOJ 1939] 중량제한 (Java)

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

2020년 2월 24일
·
0개의 댓글

[BOJ 16988] Baaaaaaaaaduk2 (Easy) (Java)

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

2020년 2월 23일
·
0개의 댓글

[BOJ 16985] Maaaaaaaaaze (Java)

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

2020년 2월 21일
·
0개의 댓글

[BOJ 12904] A와 B (Java)

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

2020년 2월 17일
·
0개의 댓글

[BOJ 17090] 미로 탈출하기 (Java)

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

2020년 2월 17일
·
0개의 댓글

[BOJ 16137] 견우와 직녀 (Java)

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

2020년 2월 16일
·
0개의 댓글

[BOJ 12906] 새로운 하노이 탑 (Java)

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

2020년 2월 16일
·
0개의 댓글

[BOJ 3197] 백조의 호수 (Java)

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

2020년 2월 15일
·
0개의 댓글

[BOJ 2234] 성곽 (Java)

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

2020년 2월 15일
·
0개의 댓글