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

그래프의 탐색이란 루트부터 아래 노드들 까지 모든 정점을 방문하는 것이다. 깊이 우선 탐색(DFS)이란? 깊이 우선 탐색은 트리나 그래프에서 한 루트로 최대한 깊숙이 들어가서 탐색한 후 다시 돌아와 다음 루트도 깊이 탐색하는 방법이다. 일반적으로 재귀 호출을 사용하여 구현한다. 단순 검색 속도는 BFS보다 느리다. 장점 1. 목표 노드가 깊이 있으면 빨리 구할 수 있다. 2. 매번 기억하는 노드가 하나이므로 저장 공간의 수요가 적다. 단점 1. 목표노드가 없는 경로의 깊이 빠질 수 있다.-> 시간이 많이 걸릴 수도 있다. 알고리즘 설명 그림과 같이 루트가 1인 트리가 있다. 루트가 1이므로 루트 1에 대하여 DFS를 하면 최대 노드 3까지 내려가게 된다. 다음 루트는 이제 노드 2가 되어서 노드 2에 대..

문제 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. 방문을 마친 노드..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 문제해결 1. DFS를 이용해서 가장 경로가 큰 노드를 찾는다. 2. 가장 큰 노드를 루트로 하고 다시 DFS를 해준다. 코드 ide.goorm.io/shared_files/sksj0111_9c7f680ec5975ba4aae255f776fdbd4c1605924147580 1167.cpp - goorm 구름IDE에서 공유된 소스코드를 볼 수 있는 페이지입니다. ide.goorm.io..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제해결 1. 2차원 배열에 데이터 입력받음 2. 가장 모서리는 항상 빈공간이므로 (0,0) 에서 BFS를 이용하여 치즈 바깥쪽을 9라고 해놓은다. 3. 치즈를 차례차례 하나씩 방문하면서 2개 이상 9하고 인접하면 1에서 0으로 바꾼다. 4. 위 방법을 치즈가 완전히 다 없어 질때 까지 반복한다. 코드 ide.goorm.io/shared_files/sksj0111_91856d3b48581..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제해결 1. 데이터를 2차원배열에 입력받는다. 2. 재귀를 이용하여 모든 경우의 수의 놓일 수 있는 벽을 세운다. 3. 벽을 3개 세우면 bfs을 통해 바이러스를 퍼뜨린다. 4. 바이러스를 퍼뜨린 후 남아있는 안전구역을 센다. 5. 2~4번을 반복하면서 안전구역이 가장 많은 경우를 찾는다. 이 문제는 벽을 세우는게 가장 핵심 포인트다. 나도 처음에는 백트래킹을 잘 몰라서 못풀었는데 백준 문제 중에 N과M이라..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 1.루트노드르르 찾는다. 2.벡터를 이용해서 트리를 만들어준다. 3.dfs를 이용해서 탐색을 한다 3-1. 자식 노드가 0개, 1개, 2개이상일때의 경우를 나눈다음 구현한다. 코드 #include #include #include #include #define max 52 using namespace std; vector tree[max]; int visit[max] = {0,}; int..