그래프그래프 정의와 용어그래프 G는 공집합이 아닌 정점 집합 V와 간선 집합 E로 구성된다.G = (V,E)두 정점이 간선으로 연결되었다면 두 정점은 인접(adjacent)하다고 한다.자기 자신을 간선으로 연결하는 것을 Self-loop(또는 Self-edge)라고 한다.V(G`)⊆ V(G)이고 E(G`)⊆ E(G)인 그래프 G`를 그래프 G의 부분 그래프(subgraph)라 한다.정점 u부터 정점 v까지의 경로(path)는 정점 순서 u, i1, i2, ..., ik, v를 말한다.한 경로의 길이(length)는 경로 상에 있는 간선의 수이다.경로 상에서 처음과 마지막을 제외한 모든 정점들이 서로 다를 때, 그 경로를 단순 경로(simple path)라 한다.처음과 마지막 정점이 같은 단순 경로를 사이..

문제https://www.acmicpc.net/problem/1697코드// 첫 번째 풀이// for + switch문 사용#include using namespace std;int N, K;queue q;int line[100001]; // 이동 거리를 저장할 배열void LineBFS() { while (!q.empty()) { auto x = q.front(); q.pop(); // X-1, X+1, 2*X 모두 범위, 이미 방문한 곳인지, K와 같은 지 확인 for (int i = 0; i = 100001) break; // 범위 벗어나면 if (line[x - 1] != -1) break; // 이미 방문했으면 line[x - 1] = line[x] + 1; q.pus..

문제https://www.acmicpc.net/problem/1012코드#include using namespace std;int matrix[50][50];int T, M, N, K, X, Y;int cnt = 0;queue> q;int dy[4] = { -1, 1, 0, 0 };int dx[4] = { 0, 0, -1, 1 };void BFS() { while (!q.empty()) { pair front = q.front(); q.pop(); for (int i = 0; i = M || newY = N) continue; if (matrix[newY][newX] != 1) continue; matrix[newY][newX] = 0; // 방문 처리 q.push(make_pair(new..

https://blog.encrypted.gg/941 [실전 알고리즘] 0x09강 - BFS안녕하세요 여러분, 드디어 올 것이 왔습니다. 마음의 준비를 단단히 하셔야 합니다.. 드디어 실전 알고리즘 강의에서 첫 번째 고비에 도달했는데 이 강의와 함께 이번 고비를 잘 헤쳐나가면 좋blog.encrypted.gg대부분의 내용을 위의 게시물을 참고해 작성한 글이다.BFS의 기본 개념BFS를 사용하면 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문할 수 있다. BFS는 원래 그래프에서 모든 노드를 방문할 때 사용하는 것이 맞지만... 그냥 다차원 배열에서도 사용할 수 있다고 생각하자. (다차원 배열에서의 탐색이 필요한 문제는 전부 BFS로 푼다고 생각해도 된다. DFS는 그래프나 트리에서 자주 사용됨)..