bfs + union_find를 배우고 풀면서 이 문제를 풀어봤다 각 칸들을 하나의 집합이라보고 문명을 bfs를 통해 넓혀가면서 4방향으로 합쳐주면 된다 합치면서 0이였던 칸은 1로 바꿔주며 큐에 넣어준다 문명이 커지다가 문명끼리 인접해도 합쳐지기 때문에 한번씩 더 봐줬다 근데 문제는 마지막에 다 합쳐졌는지 확인하는 과정에서 완탐을 버리지못하고 하나하나 다 확인해줬다~~! 시간이 덕분에 쭉~쭉 증가했다 내일 이것좀 수정해봐야겠다 추가로 이분탐색+bfs를 통해서도 많이 해결하던데 한번 공부해봐야겠다! 소스코드 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 ..
아주 쉬운 기하문제다 우선 옛날에 틀렸었는데 이유는 무조건 직사각형으로 만들어야하는데 그걸 안지켰다 근데 막상 하려니 혼자 어렵게 생각해서 직선끼리 만나고 그런경우 따지고있었다 도움을 좀 받고 보니 내가 전광판을 직사각형 모양이 나오도록 가려야만 효과가 있는걸 알았다 결국 오른쪽 왼쪽 위 아래 이렇게 가릴때만 비교하면 된다! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 #include using namespace std; int x1,x2,x3,x4,y1,y2,y3,y4; int main(){ scanf(" %d %d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4); if(y3
유니온 파인드를 이용하는 기본문제다 친구면 비용이 작은 사람들에게 합쳐준다! 마지막으로 내가 0이라고 생각하고 1~n까지 merge해주면서 비용을 합쳐주면 된다! 소스코드 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 #include #include using namespace std; int n, m, k; int arr[10010]; int p[10010]; int find(int x) { if (p[x] == x) return x; return p[x] = find(p[x]); } void merge(int x, int y) { x = find(x); y..
옛날에 이상하게 풀고 틀렸던 문제다 오늘 다시보니 다익스트라가 먼저 떠올라서 풀었다 N의 크기가 작아서 덕분에 풀었다 다익스트라를 모든 소에서 돌리면서 다리가 있다면 비용을 1 없다면 0으로 탐색하면된다 그리고 소의 위치를 돌며 가는데 비용이 든다면 set에 저장해주자 그럼 set의 사이즈가 정답이 된다! 풀고나서 사람들을보니 다들 시간도 메모리도 적게쓰고 bfs 혹은 유니온파인드로 풀었다 유니온파인드 공부 부수러가야겠다 소스코드 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..
BFS를 이용해 풀 수 있는 문제다 2년전에 풀다가 직접 누구나 풀 수있는 방법인 매번 bfs하고 얼음녹이기를 했다가 시간초과나서 틀렸었다 ㅎㅎ 시간을 어떻게 줄일까 고민하다가 실패했는데 오늘 질문을 보다가 얼음을 매번녹이지말고 다음에 녹을것을 큐에 넣으라는 말을 봤다 그제서야 떠올랐다..!! 이런 생각은 어케하는걸까 문제를 푸는 방법은 bfs를 2개 돌린다고 생각하면 된다 백조 1마리가 도는 bfs와 땅(== '.') 이 도는 bfs 먼저 백조가 갈 수 있는 땅은 모두 다 가야한다 그리고 녹아야 할 땅을 bfs를 통해 모두 녹여준다 이걸 반복하는데 백조가 갈 수 있는 땅에 인접한 얼어있는 땅은 백조 bfs에서 check를 true로 바꿔주고 얼음 bfs에서 큐에 넣어준다 이 작업이 백조가 다음날부터 갈..