야생가오리

https://www.acmicpc.net/problem/1043 거짓말쟁이가 되기시러각 파티의 참여자를 서로 연결하고, 타고타고 올라갔을때 진실을 아는 사람을 만나는지 안 만나는지를 확인해야 한다. 연결하고 찾는데는 유니온파인드를 사용한다.보자마자 이거다 하고 생각이 안 났다.. 사실 지금도 잘은 모르겠다 첨엔 걍 단순히 진실을 아는 사람이 파티에 섞여있는가를 따지는 문제인가 싶었는데, 같은 사람이 다른 파티에 참여해 다른 사실을 듣는 것 역시 안 된다는 조건 때문에 유니온파인드를 사용해줘야 했다. 우선 유니온파인드 구현은 언제나와 같다.vectorparent;int findParent(int node) { if (parent[node]  입력으로 진실을 아는 사람들이 주어진다. 이 사람들을 kn..

https://www.acmicpc.net/problem/1260 클래스 3 승급 필수문제가 하나 남았길래... 근데 이걸 안 풀었길래... ㅋㅋ3 에센셜에 그래프 탐색문제가 참 많은듯?? DFS는 이제 잘 쓴다void dfs(int idx, vector&ans_dfs){ visited_dfs[idx] = true; ans_dfs.push_back(idx); for(int i=1;i BFS큐!! 를 쓴다는 것을 꼭 기억할 것시작정점을 큐에 넣고, 그걸 빼면서 그 자식이 되는 정점들을 반복문으로 큐에 넣고... 반복void bfs(vector&ans_bfs){ queue q; q.push(v); visited_bfs[v] = true; while(!q.empty()){..

https://www.acmicpc.net/problem/10026 그래프에서 구역을 찾는 문제 = DFS. 이제 바로바로 튀어나온다적록색약인 사람과 아닌 사람의 차이는 R과 G를 똑같이 처리하냐 아니냐밖에 없으므로, 그냥 보드를 따로따로 만들고 함수도 (귀찮아서) 따로따로 만들어 각자 실행해줬다.visited 배열도 두 개 만들어도 될 테지만 이건 그냥 memset(visited, 0, sizeof(visited)) 로 초기화해서 재사용 반복문으로 상하좌우를 탐색.순환호출의 조건은 다음 좌표가 보드 안에 있을 것, 그리고 같은 색깔 즉 같은 char값을 가질 것이다. (visited가 방문되지 않았음은 당연하고)void dfs(int x, int y){ char color = board[x][y]..

https://www.acmicpc.net/problem/1389 결국 그래프에서 한 정점으로부터 다른 정점까지의 최단거리를 모두 구해서 더해주겠다는 뜻= 최단경로 알고리즘= 그중에서도 모든 정점간 최단거리를 구할 수 있는 플로이드워셜을 쓰면 된다. 플로이드-워셜은 가능한 모든 두 정점 간 조합에 대한 최단경로를 구하는 ASP(All-Pairs) 알고리즘으로, 두 정점 사이의 최단경로에 포함될 수 있는 모든 정점을 고려한다.정점 V개 간선 E개에서 O(V^3)의 복잡도를 가진다.모든 정점 사이의 최단경로를 구해야할 때는 다익스트라보다 효율적인 부분이 있다. 각 정점을 중간 정점으로 하여, 시작과 끝점에서 해당 정점을 지나는 것과 지나지 않는 것 중 더 짧은 거리를 선택해 그것을 최단경로로 한다. 중간/시..

https://www.acmicpc.net/problem/1012  가로길이 3, 세로길이 2인 표가 있다고 치자.아보카도고래가오리소방차고슴도치송전탑일반적으로 좌표 표기는 (행, 열)로 한다. 고래의 좌표는 0행 1열이므로 (0, 1) 처럼 표기할 수 있다.행과 열의 뜻이 그러하듯 0은 세로길이 기준이고 1은 가로길이 기준이다.송전탑의 좌표 역시 1행 2열이므로 (1, 2)이다. 순서대로 세로길이, 가로길이 기준이다.그러니까 가로길이 M, 세로길이 N을 주고 좌표를 x(m 기준), y(n 기준) 으로 줬다면 표기할 때는 둘을 뒤집어서 board[y][x] = 1과 같이 표기해줘야 하는 것이다. 상하좌우로 이웃한 배추들은 하나로 쳐도 된다.주어진 보드에서 상하좌우 이웃한 배추들의 덩어리가 몇 갠지 세는 문..

https://www.acmicpc.net/problem/16236 그래프 탐색. 조건이 길게 적혀있는데더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.탐색 시 우선순위는 거리가 가까움 / 가장 위에 있음(y좌표가 최소) / 가장 왼쪽에 있음(x좌표가 최소) 에 따라 정해진다.우선순위 큐를 사용한 BFS..

https://www.acmicpc.net/problem/21924  전체코드/****************************************************************************** Online C++ Compiler. Code, Compile, Run and Debug C++ program online.Write your code in this editor and press "Run" button to compile and execute it.*******************************************************************************/#in..

https://www.acmicpc.net/problem/1774문제황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다.하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다.우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들 끼리 이어진 정신적인 통로를 통해 이루어 진다. 하지만 우주신들과 교감하는 것은 힘든 일이기 때문에 황선자씨는 이런 통로들이 긴 것을 좋아하지 않는다. 왜냐하면 통로..

https://www.acmicpc.net/problem/1766문제민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.N개의 문제는 모두 풀어야 한다.먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.가능하면 쉬운 문제부터 풀어야 한다.예를 들어..

https://www.acmicpc.net/problem/1005 문제서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다.이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자.이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할수 있..