Algorithm/Beakjoon

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 1. Logic 최소 스패닝 트리 기본 문제 2. Code Kruskal #include using namespace std; int v, e; int parent[1001]; vector graph; int find(int x) { if(parent[x] == x) return x; return parent[x] = find(parent[x]); } int solve() { int weight = 0; for(int i = 0; i < e; i++) { int cost = graph[..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. Logic 최소 스패닝 트리 기본 문제. 문제를 읽어보면 분리된 두 마을의 길들은 없앤다고 했기 때문에 1. 모든 마을을 연결하는 최소 스패닝 트리를 구하고 2. 스패닝 트리를 구성하는 원소값 중 최댓값을 원소의 합에서 빼서 정답을 도출한다. 2. Code Kruskal #include using namespace std; int v, e; vector ..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 1. Logic 최소 스패닝 트리 기본문제 오늘 MST(Minimum Spanning Tree) 최소스패닝 트리를 공부해서 풀이 방법인 크루스칼, 프림 두방식 모두 풀이해봤다. 2. Code Kruskal #include using namespace std; int v, e; vector graph; int parent[10001]; int find(..

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 1. Logic 5X5배열에 cnt도 6이기 때문에 브루트포싱 돌려도 시간 복잡도를 넘지 않는다! DFS로 해결했다 2. Code #include using namespace std; char graph[5][5]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; unordered_sets; void sol..

https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 1. Logic 기본 DFS문제. 간단하게 T를 피해서 DFS 돌려주고 이동 거리가 맞는것만 count해주면 된다. 2. Code #include using namespace std; int r, c, k; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; char graph[6][6]; bool vis[6][6..

https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 1. Logic 처음에 DP로 될거같아서 시도했는데 DP는 vis배열을 찍고 나오기 때문에 최단거리 계산이 안된다. 그리고 vis배열을 기록을 안하게 되면 루프를 계속 들어가기 때문에 힙이 터진다..ㅋㅋㅋㅋ 결국 BFS 느낌으로 해결 이 문제에서 " 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다."는 배수만큼 앞으로 이동 + 배수만큼 뒤로 이동할 수 있다. 2...

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 1. Logic 입력을 인덱스로도 받지만 string으로 받은 후 0의 위치를 찾고 그 상태에서 옮길 수 있는 좌표를 찾아 BFS 브루트포싱한다. 방문처리를 어떻게 해야 할 지 고민이었는데 map / set을 활용하여 중복이 되지 않도록 처리해줬다. map을 활용한 풀이, set을 활용한 풀이 둘 다 해봤다 2. Code map을 활용한 풀이 #include using namespace std; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 1. Logic 정사각형이 같은 섬에 잇는 조건은 가로, 세로, 대각선으로 걸어서 갈 수 있는 경로가 있어야 한다. 즉 8방향 탐색을 해서 섬의 갯수를 구해주면 된다. 2. Code #include using namespace std; int graph[51][51]; bool vis[51][51]; int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int dy[8] ..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, www.acmicpc.net 1. Logic 여기서 주의해야 할 점은 바이러스가 퍼지면서 비활성 바이러스에 닿게 되면 그 부분은 시간으로 처리를 안해준다. 문제에 따로 명시는 되어있지 않지만 테스트 케이스를 설명해주는 그림을 잘 보면 그렇게 되어있다... 1. 문제를 푸는 로직은 먼저 입력받으면서 바이러스가 있는 좌표를 저장해놓는다. 2. 바이러스를 활성화 할 수 있는 갯수가 정해져있기 때문에 조합을 활용해서 m개만큼 활성화 할 바..

https://www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 1. Logic 다른 분들의 풀이를 본 결과 내가 푼 방식인 위치마다 주위의 쓰레기 여부를 판단하는 방법이 있고 먼저 쓰레기 여부를 판단하여 배열에 넣은 후 다익스트라를 돌리는 방법 이렇게 2가지가 가장 대표적인 풀이인 것 같다. 내가 푼 방식인 위치를 옮길 때 마다 쓰레기 여부를 판단하는 방법은 1. 입력을 받고 시작, 도착 위치를 기록 후 2. 다익스트라를 실행 하..