문제 a. 문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다. 무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다. 구슬이 3g인 경우 아래 과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다. 와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다. 추들의 무게와 확인할 구슬들의 ..
두 노드간의 거리를 계산하는 문제이므로 BFS를 사용하는 것이 더 적합하나, DFS로도 풀어 보았다. BFS 풀이 #include #include #include #include using namespace std; int N, M, A, B; vector a[101]; bool visited[101]={false, }; void BFS() { queue q; q.push({A, 0}); int now = A; int len = 0; visited[A]=true; while(!q.empty()) { now = q.front().first; len = q.front().second; if(now==B) { cout > A >> B; cin >> M; for(int i=0; i> x >> y; a[x].pu..
DFS와 BFS의 구현을 요구하는 간단한 문제다. #include #include #include #include #include using namespace std; int N, M, V; vector graph[1001]; bool visit[1001]; void BFS(int idx) { memset(visit, false, sizeof(visit)); queue q; q.push(idx); visit[idx]=true; while(!q.empty()){ int now = q.front(); q.pop(); cout V; for(int i=0; i> x >> y; graph[x].push_back(y); graph[y].push_back(x); } for(int i=1; i
DFS와 BFS는 모두 그래프를 탐색하는 알고리즘이다. 그래프란 노드(Node)과 간선(Edge)로 이루어진 자료구조로, 그래프를 탐색한다는 것은 모든 정점을 방문하는 과정을 의미한다. DFS와 BFS는 이러한 정점을 방문하는 과정에서의 차이로 구분된다. 이 글에서는 DFS와 BFS에 대해 이야기 해볼것이다. 깊이 우선 탐색 (DFS) 이름에서 알 수 있는 DFS는 깊이를 우선한다. 즉, 분기를 만나면 현재 진행 중인 분기를 완전히 깊게 탐색을 마친 후 다음 분기를 탐색한다. DFS는 다음과 같은 특징을 갖는다. 모든 노드를 방문할 때 주로 사용한다. 구현이 BFS보다 간단하다. 검색속도 자체는 BFS보다 느리다. a. 구현 (1) 인접 행렬을 이용한 구현 #include using namespace s..
