AtraFelis's Develop Diary

99클럽 코테스터디 6일차 TILKeyWord : BFS, DFS, graph문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수..

문제정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다.A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.입력첫째 줄에 A, B ($1 ≤ A 출력A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.풀이BFS를 이용하여 최소 연산 횟수를 찾는 문제이다. 주의할 것은 B의 최댓값이 $10^9$이므로, 오버플로우가 일어날 수 있다는 것이다.첫 번째 연산인 $num \times 2$일 때는 int의 최댓값인 $2^{31}-1$을 초과하지 않지만, 두 번째 연산에서는 오버플로우가 일어날 수 있으므로 64bit 자료형인 long을 사용하거나, unsigned int를 사용해야 한다. 하지만..

SILVER II문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.출력첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.풀이난이도 보고 쉽게 풀 수 있겠거니 했다가, 통수에 통수를 맞은 문제였다.일단 문제의 풀이 방향은 이렇다.주어지는 입력값을 그래프로 만든다.1번 노드부터(1번은 무조건 root이므로) 차례대로 그래프를 탐색한다. BFS든 DFS든 상관없으나 나는 BFS를 사용하였다.1번 노드와 연결된 노드는 무조건 1번 노드를 부모로 갖는다.이미 부모..