주소 : https://www.acmicpc.net/problem/2606 [ 너비우선탐색(BFS) VS 깊이우선탐색(DFS) ]이 문제는 너비우선탐색(이하 BFS) 또는 깊이우선탐색(이하 DFS)로 문제를 해결할 수 있다. 두 가지 탐색방법은 그래프를 탐색할 때 사용하는 알고리즘 기법이다. 여기서 그래프는 간선과 노드로 이루어진 자료구조를 말한다. 이 말은 위 문제의 그림1에 대입해 볼 수 있다. 그림 1은 그래프 자료구조 형태이다. 숫자 1, 2, 3..을 노드라고 부른다. 그리고 각 노드를 연결하는 선을 간선이라고 한다. 그럼 그래프를 탐색하는 두 가지방법(BFS, DFS)를 설명하겠다. 첫번째 BFS는 시작 노드에서 사방으로 퍼지는 형태로 탐색하는 알고리즘이다. BFS를 그림1에 적용하면 아래와 ..
[ 해결 방법 ]단순 BFS 문제이다. 현재 수빈이의 위치에서 갈 수 있는 방향(X+1, X-1, 2*X)을 큐에 넣고 K가 나올 때까지 계속 반복하면 된다. [ 코드 ]#include #include using namespace std;struct pos{int x, t;};int N, K, Max;queue q;bool visit[200001];int dir[3] = { -1,1,1 };int main(){cin >> N >> K;if (N == K){cout
[ 해결 방법 ]기본적인 BFS문제인 것 같다. 현재 위치에서 위또는 아래 방향으로 BFS돌리면 된다. [ 내 코드 ]#include #include using namespace std; struct info{ int floor, cnt;};int F, S, G, U, D;int visit[1000002];int dir[2] = { 1, -1 };queue q; int main(){ cin >> F >> S >> G >> U >> D; dir[0] *= U; dir[1] *= D; q.push(info{ S, 1 }); visit[S] = 1; info cur, next; while (!q.empty()) { cur = q.front(); q.pop(); for (int i = 0; i F || next..
[ 풀이 방법 ]토큰이란걸 만들었다. 모든 토큰의 시작점은 트리의 단말노드이다. 토큰에는 현재 위치, 이전 위치, 총 이동거리의 정보를 포함하고 있다. 이 토큰을 큐에 넣고 하나씩 빼면서 현재 위치에서 이동할 수 있는 모든 방향으로 퍼지게 만들었다(BFS 방법). 이 때, 왔던 길로 다시 못가게 하기 위해서 토큰에 이전 위치를 저장했다. 이제 가려고하는 위치와 이전 위치가 같다면? 왔던길로 다시 돌아가는 거니까 못가게 막았다. 그리고 예외 상황이 문제를 짜증나게 만들었는데, 첫번째는 지름이 단말-단말 뿐만 아니라 단말-루트도 가능하다. 루트가 자식노드를 하나만 갖고 있으면 이런 경우가 가능하다. 두번째는 단말노드를 큐에 넣으면 안된다. 1만개쯤의 노드가 있다면 단말노드는 수천개쯤 된다. 메모리가 뻑날 수..
https://www.acmicpc.net/problem/2146 [ 나의 문제 풀이 ]1. 각 섬에 번호 부여 : 이중for문으로 map돌면서 섬 만날 때마다 BFS하면, 각 섬에 번호가 부여됨.2. 거리 측정 후보 선택 : BFS돌면서, 바다와 인접해 있는 지역 좌표를 candidate라는 vector에 저장. 3. 거리 측정 : candidate에 있는 좌표들 끼리 거리측정함. 단, 당연히 다른 섬번호끼리만 좌표를 측정. 거리측정은 ABS(y2-y1) + ABS(x2-x1)으로 구하면 됨. 이 때, 거리 측정할 섬들 사이에, 다른 섬이 있을지 모름. 하지만 괜찮음. 생각해보면, 이 경우는 어차피 최단거리가 될리가 없기 때문임. [ 나의 코드 ]1234567891011121314151617181920..
https://www.acmicpc.net/problem/1707 [ 그림1. 이분 그래프 설명 ][ 나의 해결법 ]그림1처럼 각 집합(파랑색과 빨강색)안에 노드들끼리 간선이 없으면 이분그래프가 된다. 그럼 어떻게 이분그래프인지 알 수 있을까? 주어진 그래프가 이분 그래프인지 확인하는 것은 어렵지 않다. 꼭짓점 하나를 빨강으로 칠한 후 이웃 꼭짓점들은 녹색으로 칠하고 그 이웃들은 빨강으로 칠하는 것들을 반복하면서, 같은 색깔의 꼭짓점이 서로 연결되어 있는 모순이 발생하는지 아닌지 확인만 하면 된다. 예를 들어, 크기가 3인 순환 그래프는 이분 그래프가 아니다. [ 출처 : 위키백과 ] 이 문제에서 주의해야할 점은 다른 노드들과는 아예 분리된 노드가 존재할 수 있다는 것이다. 그림1과 같은 그래프 두 개가..