KPU CE

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제해결 1. 기존 BFS 문제에서 조금 변형된 문제이다. 나이트의 이동 방향를 ck함수에 추가한다. 2. 각 방향에 대해서 이동 가능/불가 여부를 판단한 후 큐에 넣어서 BFS알고리즘을 돌린다 3. 도착지의 x, y값이 나오면 BFS를 끝내고 다음 입력값에 BFS를 돌려주는 간단한 문제이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21..

문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 해결 1. 인접 리스트로 정점들을 저장한다. 2. 1~N까지 방문하지 않은 노드들을 DFS 한다. 3. 방문할 때 마다 cnt를 해준다. 코드 1234567891011121314151617181920212223242526272829303132333435#include #include #define Max 1001using n..

문제 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 1. DFS를 이용하여 1~N까지의 숫자를 탐색한다. 2. ex) 1에 대하여 탐색한다면 1에 대하여 깊이 탐색한 후 지나는 모든 노드들을 visit 한다. 3. visit이 true이면 map [1][j] = 1로 인접 행렬을 만든다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 ..

최소 공통조상이란? 두 노드의 조상이 처음으로 같은 경우를 최소 공통 조상이라고 한다. 지금부터 최소 공통 조상을 구하는 알고리즘을 알아보도록 하겠다. 위와 같이 트리가 하나 있다. 여기서 1이 루트라 하고 각 깊이를 구하면 다음과 같다. 여기서 노드 3과 노드 8의 최소 공통 조상은 그림과 같이 노드 2인 것을 알 수 있다. 하나 더 예시를 보자면 노드 8과 노드 10의 최소 공통 조상은 노드 10인 것을 알 수 있다. 바로 본론으로 들어가자면 최소 공통 조상 알고리즘은 1. 두 노드의 깊이를 확인한다. 2. 만약 하나가 다른 노드보다 작다면 깊이-1을 해준다. 3. 만약 깊이가 같다면 두 노드 모드 깊이 -1를 해준다. 4. 깊이-1 해주면서 만약 노드가 같아지는 지점을 찾는다. 5. 같아지는 지점이..

인접 행렬 위와 같이 무방향으로 노드들이 이어져 있다. 이제 이 그래프를 저장하는 2차원배열 ary[6][6]를 만들어준다. 그리고 노드a과 노드b가 이어져있다는 것을 배열로 표현해준다면 ary[a][b] = true, ary[b][a] = true 로 표현해줄 수 있다. 하지만 여기서 단방향 그래프로 만들고 싶으면 예를 들어 a->b인 노드이면 ary[a][b] = true 라고만 해주면 된다. 이렇게 표현하게 된다면 위의 그림은 ary[6][6]의 크기의 배열이 필요하다(ex. ary[5][4] = 1) 이걸 배열로 나타낸다면 아래와 같다. [0] [1] [2] [3] [4] [5] [1] 0 1 0 0 0 [2] 1 0 1 0 0 [3] 0 1 0 0 1 [4] 0 0 0 0 1 [5] 0 0 1 ..