KPU CE

문제 해결 일반적으로 사용하는 bfs 케이스(상하좌우)에 체스 말 케이스를 추가해서 12가지의 케이스를 고려해서 bfs 코드르 작성하렸다. 여기서 주위해야될 점은 체스말로 이동한 곳은 따로 visit를 해야된다. visit을 할때 그곳이 k가 0~30번까지 올 수 있기 때문이다. 코드 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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include #..

너비 우선 탐색이란? -큐를 이용한 탐색 방법으로 한 노드로부터 이동할 수 있는 노드들을 큐에 넣어서 탐색하는 방법이다. -DFS와 달리 깊이 들어가지 않음으로 구하려는 해가 깊이 들어있지 않을 때 효율적이다. -DFS와 달리 반복문을 통해서 구현한다. 개념 설명 위와 같은 루트가 1인 트리가 있다. 이 트리를 큐의 변화와 탐색 순서를 보면서 이해해보자. -처음 루트 1을 방문했을 때 큐 2 3 트리 -큐에 있는 노드인 노드 2와 노드 3을 방문하고 노드 2와 노드 3에 연결된 노드들을 큐에 넣는다. 큐 5 4 9 6 트리 -큐에 있는 노드들 방문 후 자식 노드들을 똑같이 큐에 넣는다. 큐 7 8 10 트리 -큐에 있는 나머지 노드들 방문 큐 트리 탐색 완료! 탐색 순서 1-2-3-5-4-9-6-7-8-..

문제 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..

문제 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 1. BFS를 이용해서 탐색을 할 때 방문할 노드가 개방 가능 조건에 있다면 border배열을 true로 해준다 2. true로 되어 있는 노드를 하나 방문 후 연결되어 있는 모든 true노드를 방문한다. 3. 방문할 때마다 cnt++ 을 해줘서 몇 개의 노드를 방문해 줬는지와 sum+=map [y][x]를 해줌으로써 방문한 노드들의 평균값을 구할 수 있다. 4. 방문을 마친 노드..