소근소근

백준 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 기본적인 dfs 만 구현할 줄 안다면 풀 수 있는 문제이다. 1년씩 지나면서 빙산이 녹을 때, 처음으로 덩어리가 두개 이상이 되는 최초의 시간을 출력한다. 상하좌우 4방향 중에서 비어있는 경우(0인 경우)의 개수만큼 빼준다. 여기서 주의해야 할 점은, 현재 상태를 기준으로 보고 빼줘야 한다. (동시에 녹는다고 본다) 표시한 부분에서 2-2 = 0 이 되어도, 4부분을 볼 때는 왼쪽은 0..

백준 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 어떤 칸에서 출발하여 계속 대나무가 더 많은 쪽으로만 이동할 때, 최대로 움직일 수 있는 칸의 개수를 구하는 문제이다. 처음에 단순 DFS인줄 알고 이중 for문을 돌며 모든 칸에 대해 dfs를 돌려 최대 칸의 개수를 구했더니 시간초과가 났다. 이 문제는 재귀로 dp를 구현해서 풀면 되는 문제였다. 풀이 해법은 https://yabmoons.tistory.com/15..

level3 지만 bfs로 간단하게 해결할 수 있는 문제였다. 오히려 level2보다 더 쉬운거 같기도 하고 ,.? dog -> dot 처럼 한 char만 바꿀 수 있다. 주어진 words의 문자들의 길이는 모두 동일하다고 조건이 주어졌기 때문에 단순히 두 문자열을 앞에서부터 비교하여 다른 char가 하나만 있을때 변환이 가능하도록 한다. #include #include #include #include #include #include #include using namespace std; bool able = false; queue q; map visit; int compchar(string a, string b){ int len = a.length(); int cnt =0; for(int i=0;i

BFS/DFS 분류에 있는 문제였지만, 분리집합으로 풀었다. 컴퓨터 두대가 연결 되면 같은 네트워크(같은 집합)으로 분류되기 때문이다. 연결된 컴퓨터 두대는 union해서 같은 집합으로 보고, 마지막에 집합의 개수를 출력하면 된다. #include #include #include #include #include using namespace std; int parent[200]; map m; int Find(int x){ if(x==parent[x]) return x; return parent[x] = Find(parent[x]); } void Union(int x, int y){ int px = Find(x); int py = Find(y); if(px != py){ parent[px] = py; } }..

bfs를 이용하면 쉽게 해결할 수 있는 문제이다. queue에 -num , num 을 더해주고 큐에 push하면서 반복문을 돌고, target 에 도달하면 answer를 증가시켜서 카운트한다. #include #include #include #include #include #include #include using namespace std; queue q; int solution(vector nums, int target) { int ans = 0; q.push({0,-nums[0]}); q.push({0,nums[0]}); while(!q.empty()){ int now_idx = q.front().first; int total = q.front().second; q.pop(); if(now_idx =..

#include #include #include #include #include #include #include using namespace std; map genKey; map getCount; vector genNum; vector v[100]; bool comp(const pair&a , const pair&b){ if(a.first == b.first) return a.second > b.second; return a.first < b.first; } vector solution(vector gen, vector plays) { vector answer; int tmp = 0; for(int i=0;i

백준 4195 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 친구 관계 정보를 받아 친구 네트워크에 속하는 친구 수를 출력하는 문제로, 분리 집합(disjoint set)을 이용하여 풀었다. 숫자가 아니라 문자열을 입력 받으므로 자료구조 map을 이용하여 로 저장하여 정수로 처리했다. union find 설명 글 https://steptoprogrammer.tistory.com/64 [알고리즘/자료구조] 분리 집합( ..

분리 집합이란 교집합이 존재하지 않는 두개 이상의 집합을 뜻한다. 구분해야 하는 데이터 집합들을 다루는 알고리즘에서 사용할 수 있다. 분리집합에서는 자식 노드가 부모 노드를 가리키게 되어 있다. 보통 특정 집합의 대표 노드(루트)를 자식 노드들이 가리키고 있는 형태이다. 분리집합 연산에는 두 가지가 있다. 1. Union(x,y) 합집합 연산이다. 두개의 집합을 합치기 위해서 각 두 집합의 대표(루트)노드를 찾고, A의 대표노드의 부모를 B의 대표 노드로 설정한다. void Union(int x, int y) { int px = Find(x); int py = Find(y); if (px != py) { parent[px] = py; set_size[py] += set_size[px]; } } 합치려고 ..