푸으름

✏️ 문제 링크https://www.acmicpc.net/problem/2589  ✏️ 문제 설명  ✏️ 문제 풀이그냥 단순히 모든 육지인 지점은 찾아서 그 지점에서 가장 먼 거리를 BFS를 탐색해서 구해준 후거리들의 최댓값을 구해주면 됩니다처음에는 트리의 지름을 구하는 방식으로 접근을 해봤는데 계속 2%에서 틀려서...포기  ✏️ 문제 코드#include #include #include using namespace std;struct Node{ int y, x, depth;};const int dy[4] = { -1,1,0,0 };const int dx[4] = { 0,0,-1,1 };int N, M, ret;char adj[50][50];bool visited[50][50];vector> v;void..

✏️ 문제 링크https://www.acmicpc.net/problem/24444  ✏️ 문제 설명  ✏️ 문제 풀이bfs를 구현하는 문제입니다. visited배열을 만들어서 각 정점의 방문 여부를 체크해주고, order배열을 만들어서정점들의 방문 순서들을 저장해 주면 됩니다. 오름차순으로 인접 정점을 방문해줘야 하므로 sort 정렬을 해줍니다.  ✏️ 문제 코드#include#include#include#includeusing namespace std;int N, M, R;vector>mlist;bool visit[100001];int order[100001];int cnt = 1;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NU..

✏️ 문제 링크 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net ✏️ 문제 설명 ✏️ 문제 풀이 먼저 주어진 좌표들을 이용해서 bfs를 돌려서 각 섬의 영역들을 정해줍니다. 그러면 예제입력의 경우에는 총 섬이 3덩어리로 나눠지게 됩니다. 그 다음, 각 섬들의 영역에서 bfs로 돌려서 다른 섬으로 갈 수 있는 다리들의 최솟값을 구해줍니다. 자세한 bfs조건들은 아래 코드를 봐주세요 ✏️ 문제 코드 #include #include #include usi..

Algorithm 공부 #13 - 그래프(그래프의 표현) 에지 리스트(edge list) ● 에지를 중심으로 그래프를 표현 ● 배열에 출발 노드, 도착 노드를 저장하여 에지를 표현 ● 배열에 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지를 표현 인접 행렬(adjacency matrix) ● 2차원 배열을 자료구조를 이용하여 그래프를 표현 ● 노드를 중심으로 그래프를 표현 ● 노드와 관련되어 있는 에지를 탐색하기 위해서는 N번 접근해야 하므로 시간복잡도가 인접 리스트에 비해 느림 ● 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐 인접 리스트(adjacency list) ● 2차원 벡터로 그래프를 표현 ● 구현은 복잡하나 노드와 연결된 에지를 탐색하는 시간이 뛰어나며, 노드 개수가..