[1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5]을 통해 1 > 2 > 3 > 46 > 5 > 4를 유도할 수 있다. 이는 일종의 단방향 그래프로 볼 수 있다.3 > 4, 5 > 4일 때 3과 5 중 어떤 값이 더 크고 작은지 알 수 없다. 여기서 구하는 값은 물건과의 비교 결과를 알 수 없는 물건의 개수이다.따라서 탐색을 통해 (n - 1) - (i에 도달할 수 있는 모든 값의 수)를 구하면 된다. dfs, bfs, 플로이드-와셜을 사용하여 i, j 사이에 경로(i > j, j > i)가 있음을 판단하면 된다. 첫 접근 시, 경로상 가중치 값을 통해 구하려고 했지만 사실 경로 판단만 하면 되는 문제였다... 단, dfs, bfs 사용 시 매번 경로를 탐색하지 말고 move..

문제 설명국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다.위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.연합을 해체하고, 모든 국경선을 닫는다.위 과정을 반복하며 더 이상 연합이 이루어지지 않는 경우 종료한다. 첫번째 풀이처음 풀이 시 80%에서 시간초과 났다. bfs 과정에서 이미 탐색한 구역을 다시 탐색하는 코드가 문제였다. 이 때 시간복잡도는 O(n^4)으로 최적화가 필요했다..

출처: 본 글의 내용 및 이미지는 [바킹독의 실전 알고리즘] 0x18강 - 그래프에서 참고했습니다.https://blog.encrypted.gg/1016 [실전 알고리즘] 0x18강 - 그래프안녕하세요, 드디어 무려 0x09강에서 BFS를 배울 때 처음 언급했던 그래프를 소개해드릴 수 있게 됐습니다. 그래프도 자료구조의 일종이지만 실제로도 다른 대학 교재나 뭐 기타 알고리즘 교재들blog.encrypted.gg BFS (Breadth-First Search, 너비 우선 탐색)탐색 과정: 시작 정점에서 너비 우선으로 가까운 정점들을 먼저 탐색한다. 마치 물결이 퍼져나가듯 현재 레벨의 모든 정점을 탐색한 후 다음 레벨로 넘어간다.자료 구조: 큐(Queue)를 사용하여 다음에 방문할 정점을 저장하고 관리한다...

한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력하면 된다. 순환선은 사이클에 포함되는 역들, 지선은 트리 형태의 노선(사이클 없는 무방향 그래프)이므로 사이클에 포함되지 않는 역들이다. 풀이 방법그래프에서 사이클을 탐색한다. (위상 정렬 응용 또는 dfs)임의의 역에서 사이클까지의 거리를 구한다. (bfs 탐색) 사이클 구하기위상 정렬 응용첫번째 방법으로 사이클을 탐색하기 위해 위상 정렬을 사용한다.queue q;for (int i = 1; i 위와 같이 탐색하면 사이..

풀이 방법은 다음과 같다. 1. 빈 공간 중 3개를 선택해서 벽을 설치한다.void dfs(){ int emptySize = emptyPoints.size(); for (int i = 0; i 2. 2번 위치에 존재하는 바이러스를 퍼트린다.void virusBfs(){ queue> q; for (int i = 0; i top = q.front(); q.pop(); for (int i = 0; i currentPos = { top.first + nearPoints[i].first, top.second + nearPoints[i].second }; bool outOfRange = OutOfRange(currentPos); if (outOfRange == true) continue; if (..

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 이분 그래프를 판별하기 bfs를 돌리며 서로 다른 두 색으로 표시하면 된다. 위 그림처럼 2부터 시작해서 인접 노드는 다른 색으로 칠하며 다른 집합임을 표시한다.bfs 중 인접 노드가 같은 색으로 칠해진 경우 이분 그래프가 아니다. 그럼 비연결 그래프의 경우를 생각해보자 이때 연결되지 않은 정점은 어떤 색으로 칠해도 인접한 노드가 없으므로 이분 그래프 여부와 상관 없다.모든 정점에서 bfs를 돌리며 인접 노드가 모두 다른 색으로 칠해진 경우 이분 그래프다.모든 정점에서 bfs를 돌리며 인접 노드가 같은 색으로 칠해..

설명을 이해하기 어려운 문제였다… 거울에 반사되면서 방향이 바뀐다.거울의 각도가 45도 이므로 다음과 같이 반사된다. 방향이 →, ←인 경우 ↑, ↓로 반사된다.방향이 ↑, ↓인 경우 →, ←로 반사된다.// dir// ↑ → ↓ ←pair dirs[dirSize] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };pair changeDir(int dir){ pair newDir; if (dir == 0 || dir == 2) { newDir.first = 1; newDir.second = 3; } else if(dir == 1 || dir == 3) { newDir.first = 0; newDir.second = 2; } return newDir;}위와 같이 진입하는 방향에 ..

A번 섬에서 B번 섬으로 갈 수 있는 물품의 중량 중 최대값을 구하는 문제다.도달 가능 여부는 bfs를 통해 구별할 수 있다. 그러나 C(1 ≤ C ≤ 1,000,000,000) 범위 내의 모든 중량을 탐색하여 가능한 최대 중량을 구해야 하기 때문에 완전 탐색의 경우 O((n + m) * c)의 시간 복잡도가 된다. 이때 (10,000 + 100,000) * 1,000,000,000 = 1.1e+14의 경우의 수가 존재하므로 시간 초과 난다. 따라서 이분 탐색을 적용하여 시간 복잡도를 낮춰야 한다. O((n + m) * logc)의 시간 복잡도 풀이C(1 ≤ C ≤ 1,000,000,000) 범위 내에서 이분 탐색을 적용하여 한 번의 이동에서 옮길 수 있는 물품들의 최대 중량을 구하면 된다. 코드#inc..